research-article

Area-efficient pipelining for FPGA-targeted high-level synthesis

Authors:

Zhiru ZhangAuthors Info & Claims

DAC '15: Proceedings of the 52nd Annual Design Automation Conference

Article No.: 157, Pages 1 - 6

https://doi.org/10.1145/2744769.2744801

Published: 07 June 2015 Publication History

Abstract

Traditional techniques for pipeline scheduling in high-level synthesis for FPGAs assume an additive delay model where each operation incurs a pre-characterized delay. While a good approximation for some operation types, this fails to consider technology mapping, where a group of logic operations can be mapped to a single look-up table (LUT) and together incur one LUT worth of delay. We propose an exact formulation of the throughput-constrained, mapping-aware pipeline scheduling problem for FPGA-targeted high-level synthesis with area minimization being a primary objective. By taking this cross-layered approach, our technique is able to mitigate the pessimism inherent in static delay estimates and reduce the usage of LUTs and pipeline registers. Experimental results using our method demonstrate improved resource utilization for a number of logic-intensive, real-life benchmarks compared to a state-of-the-art commercial HLS tool for Xilinx FPGAs.

References

[1]

A. Agarwal, M. C. Ng, and Arvind. A Comparative Evaluation of High-Level Hardware Synthesis Using Reed--Solomon Decoder. IEEE Embedded Systems Letters, 2(3):72--76, 2010.

Digital Library

[2]

Y. Ben-Asher, D. Meisler, and N. Rotem. Reducing Memory Constraints in Modulo Scheduling Synthesis for FPGAs. ACM Trans. on Reconfigurable Technology and Systems (TRETS), 3(3):15, 2010.

Digital Library

[3]

A. Canis, S. D. Brown, and J. H. Anderson. Modulo SDC Scheduling with Recurrence Minimization in High-Level Synthesis. Int'l Conf. on Field Programmable Logic and Applications (FPL), Sep 2014.

[4]

A. Canis, J. Choi, M. Aldham, V. Zhang, A. Kammoona, J. H. Anderson, S. Brown, and T. Czajkowski. LegUp: High-Level Synthesis for FPGA-Based Processor/Accelerator Systems. Int'l Symp. on Field-Programmable Gate Arrays (FPGA), pages 33--36, Feb 2011.

Digital Library

[5]

D. Chen and J. Cong. DAOmap: A Depth-Optimal Area Optimization Mapping Algorithm for FPGA Designs. Int'l Conf. on Computer-Aided Design (ICCAD), pages 752--759, 2004.

Digital Library

[6]

D. Chen, J. Cong, and P. Pan. FPGA Design Automation: A Survey. Foundations and Trends in Electronic Design Automation, 1(3):139--169, 2006.

Digital Library

[7]

A. Chowdhary and J. P. Hayes. Area-Optimal Technology Mapping for Field-Programmable Gate Arrays Based on Lookup Tables. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 24(7):999--1013, 2005.

Digital Library

[8]

J. Cong and Y. Ding. FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 13(1):1--12, 1994.

Digital Library

[9]

J. Cong and Y.-Y. Hwang. Simultaneous Depth and Area Minimization in LUT-based FPGA Mapping. Int'l Symp. on Field-Programmable Gate Arrays (FPGA), pages 68--74, 1995.

Digital Library

[10]

J. Cong, B. Liu, S. Neuendorffer, J. Noguera, K. Vissers, and Z. Zhang. High-Level Synthesis for FPGAs: From Prototyping to Deployment. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 30(4):473--491, Apr 2011.

Digital Library

[11]

J. Cong, C. Wu, and Y. Ding. Cut Ranking and Pruning: Enabling a General and Efficient FPGA Mapping Solution. Int'l Symp. on Field-Programmable Gate Arrays (FPGA), pages 29--35, 1999.

Digital Library

[12]

S. Dai, M. Tan, K. Hao, and Z. Zhang. Flushing-Enabled Loop Pipelining for High-Level Synthesis. Design Automation Conf. (DAC), Jun 2014.

Digital Library

[13]

A. E. Eichenberger, E. S. Davidson, and S. G. Abraham. Author Retrospective for Optimum Modulo Schedules for Minimum Register Requirements. Int'l Conf. on Supercomputing, pages 35--36, 2014.

Digital Library

[14]

A. H. Farrahi and M. Sarrafzadeh. Complexity of the Lookup-Table Minimization Problem for FPGA Technology Mapping. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 13(11):1319--1332, 1994.

Digital Library

[15]

A. Morvan, S. Derrien, and P. Quinton. Polyhedral Bubble Insertion: a Method to Improve Nested Loop Pipelining for High-Level Synthesis. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 32(3):339--352, 2013.

Digital Library

[16]

P. Pan, A. K. Karandikar, and C. Liu. Optimal Clock Period Clustering for Sequential Circuits with Retiming. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 17(6):489--498, 1998.

Digital Library

[17]

P. Pan and C.-C. Lin. A New Retiming-Based Technology Mapping Algorithm for LUT-based FPGAs. Int'l Symp. on Field-Programmable Gate Arrays (FPGA), pages 35--42, 1998.

Digital Library

[18]

B. R. Rau. Iterative Modulo Scheduling: an Algorithm for Software Pipelining Loops. Int'l Symp. on Microarchitecture (MICRO), pages 63--74, Nov 1994.

Digital Library

[19]

M. Tan, S. Dai, U. Gupta, and Z. Zhang. Mapping-Aware Constrained Scheduling for LUT-Based FPGAs. Int'l Symp. on Field-Programmable Gate Arrays (FPGA), Feb 2015.

Digital Library

[20]

M. Tan, B. Liu, S. Dai, and Z. Zhang. Multithreaded Pipeline Synthesis for Data-Parallel Kernels. Int'l Conf. on Computer-Aided Design (ICCAD), pages 718--725, 2014.

Digital Library

[21]

J. Zhang, Z. Zhang, S. Zhou, M. Tan, X. Liu, X. Cheng, and J. Cong. Bit-level Optimization for High-Level Synthesis and FPGA-Based Acceleration. Int'l Symp. on Field-Programmable Gate Arrays (FPGA), pages 59--68, 2010.

Digital Library

[22]

Z. Zhang and B. Liu. SDC-Based Modulo Scheduling for Pipeline Synthesis. Int'l Conf. on Computer-Aided Design (ICCAD), pages 211--218, 2013.

Digital Library

[23]

H. Zheng, S. T. Gurumani, K. Rupnow, and D. Chen. Fast and Effective Placement and Routing Directed High-Level Synthesis for FPGAs. Int'l Symp. on Field-Programmable Gate Arrays (FPGA), pages 1--10, 2014.

Digital Library

Cited By

Guo LMaidee PZhou YLavin CHung ELi WLau JQiao WChi YSong LXiao YKaviani AZhang ZCong J(2023)RapidStream 2.0: Automated Parallel Implementation of Latency–Insensitive FPGA Designs Through Partial ReconfigurationACM Transactions on Reconfigurable Technology and Systems10.1145/359302516:4(1-30)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1145/3593025
Sovietov P(2023)Trubol: Synthesis of Pipelined Circuits from Python-based DSL Specifications2023 5th International Conference on Control Systems, Mathematical Modeling, Automation and Energy Efficiency (SUMMA)10.1109/SUMMA60232.2023.10349644(490-494)Online publication date: 8-Nov-2023
https://doi.org/10.1109/SUMMA60232.2023.10349644
Reddy CAnand K(2022)Sensor Signal Processing using High-Level Synthesis and Internet of Things with a Layered ArchitectureInternational Journal on AdHoc Networking Systems10.5121/ijans.2022.1240312:4(35-43)Online publication date: 31-Oct-2022
https://doi.org/10.5121/ijans.2022.12403
Show More Cited By

Index Terms

Area-efficient pipelining for FPGA-targeted high-level synthesis
1. Hardware

Recommendations

Dynamic Hazard Resolution for Pipelining Irregular Loops in High-Level Synthesis
FPGA '17: Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

Current pipelining approach in high-level synthesis (HLS) achieves high performance for applications with regular and statically analyzable memory access patterns. However, it cannot effectively handle infrequent data-dependent structural and data ...
Bit-level optimization for high-level synthesis and FPGA-based acceleration
FPGA '10: Proceedings of the 18th annual ACM/SIGDA international symposium on Field programmable gate arrays

Automated hardware design from behavior-level abstraction has drawn wide interest in FPGA-based acceleration and configurable computing research field. However, for many high-level programming languages, such as C/C++, the description of bitwise access ...
From software to accelerators with LegUp high-level synthesis
CASES '13: Proceedings of the 2013 International Conference on Compilers, Architectures and Synthesis for Embedded Systems

Embedded system designers can achieve energy and performance benefits by using dedicated hardware accelerators. However, implementing custom hardware accelerators for an application can be difficult and time intensive. LegUp is an open-source high-level ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '15: Proceedings of the 52nd Annual Design Automation Conference

June 2015

1204 pages

ISBN:9781450335201

DOI:10.1145/2744769

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

DAC '15

Sponsor:

SIGDA

DAC '15: The 52nd Annual Design Automation Conference 2015

June 7 - 11, 2015

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
270
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)4

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Guo LMaidee PZhou YLavin CHung ELi WLau JQiao WChi YSong LXiao YKaviani AZhang ZCong J(2023)RapidStream 2.0: Automated Parallel Implementation of Latency–Insensitive FPGA Designs Through Partial ReconfigurationACM Transactions on Reconfigurable Technology and Systems10.1145/359302516:4(1-30)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1145/3593025
Sovietov P(2023)Trubol: Synthesis of Pipelined Circuits from Python-based DSL Specifications2023 5th International Conference on Control Systems, Mathematical Modeling, Automation and Energy Efficiency (SUMMA)10.1109/SUMMA60232.2023.10349644(490-494)Online publication date: 8-Nov-2023
https://doi.org/10.1109/SUMMA60232.2023.10349644
Reddy CAnand K(2022)Sensor Signal Processing using High-Level Synthesis and Internet of Things with a Layered ArchitectureInternational Journal on AdHoc Networking Systems10.5121/ijans.2022.1240312:4(35-43)Online publication date: 31-Oct-2022
https://doi.org/10.5121/ijans.2022.12403
Guo LMaidee PZhou YLavin CWang JChi YQiao WKaviani AZhang ZCong JAdler MIenne P(2022)RapidStreamProceedings of the 2022 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/3490422.3502361(1-12)Online publication date: 13-Feb-2022
https://dl.acm.org/doi/10.1145/3490422.3502361
Srivastava NLiu GLai YZhang Z(2022)FPGA-Specific CompilersHandbook of Computer Architecture10.1007/978-981-15-6401-7_25-1(1-37)Online publication date: 27-Jan-2022
https://doi.org/10.1007/978-981-15-6401-7_25-1
Lai YUstun EXiang SFang ZRong HZhang Z(2021)Programming and Synthesis for Software-defined FPGA Acceleration: Status and Future ProspectsACM Transactions on Reconfigurable Technology and Systems10.1145/346966014:4(1-39)Online publication date: 13-Sep-2021
https://dl.acm.org/doi/10.1145/3469660
Nishikawa HShirane KNozaki RTaniguchi ITomiyama H(2020)Function‐level module sharing techniques in high‐level synthesisETRI Journal10.4218/etrij.2020-0107Online publication date: 7-Aug-2020
https://doi.org/10.4218/etrij.2020-0107
Guo LLau JChi YWang JYu CChen ZZhang ZCong J(2020)Analysis and Optimization of the Implicit Broadcasts in FPGA HLS to Improve Maximum Frequency2020 57th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC18072.2020.9218718(1-6)Online publication date: Jul-2020
https://doi.org/10.1109/DAC18072.2020.9218718
Huang LLi DWang KGao TTavares A(2020)A Survey on Performance Optimization of High-Level Synthesis ToolsJournal of Computer Science and Technology10.1007/s11390-020-9414-835:3(697-720)Online publication date: 29-May-2020
https://doi.org/10.1007/s11390-020-9414-8
Lambert JLee SKim JVetter JMalony A(2018)Directive-Based, High-Level Programming and Optimizations for High-Performance Computing with FPGAsProceedings of the 2018 International Conference on Supercomputing10.1145/3205289.3205324(160-171)Online publication date: 12-Jun-2018
https://dl.acm.org/doi/10.1145/3205289.3205324
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents