research-article

ADAM: Automated Design Analysis and Merging for Speeding up FPGA Development

Authors:

Shuanglong Liu,

Wayne LukAuthors Info & Claims

FPGA '18: Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

Pages 189 - 198

https://doi.org/10.1145/3174243.3174247

Published: 15 February 2018 Publication History

Abstract

This paper introduces ADAM, an approach for merging multiple FPGA designs into a single hardware design, so that multiple place-and-route tasks can be replaced by a single task to speed up functional evaluation of designs, especially during the development process. ADAM has three key elements. First, a novel approximate maximum common subgraph detection algorithm with linear time complexity to maximize sharing of resources in the merged design. Second, a prototype tool implementing this common subgraph detection algorithm for dataflow graphs derived from Verilog designs; this tool would also generate the appropriate control circuits to enable selection of the original designs at runtime. Third, a comprehensive analysis of compilation time versus degree of similarity to identify the optimized user parameters for the proposed approach. Experimental results show that ADAM can reduce compilation time by around 5 times when each design is 95% similar to the others, and the compilation time is reduced from 1 hour to 10 minutes in the case of binomial filters.

References

[1]

J. Arram et al. 2013. Reconfigurable Filtered Acceleration of Short Read Alignment. In 2013 International Conference on Field-Programmable Technology (FPT). 438-- 441.

[2]

M. Aubury and W. Luk. 1996. Binomial Filters. Journal of VLSI Signal Processing Systems for Signal, Image and Video Technology 12, 1 (Jan. 1996), 35--50.

[3]

J. Bachrach et al. 2012. Chisel: Constructing Hardware in a Scala Embedded Language. In 2012 Design Automation Conference (DAC). 1212--1221.

Digital Library

[4]

A. Brant and G. G. F. Lemieux. 2012. ZUMA: An Open FPGA Overlay Architecture. In IEEE 20th International Symposium on Field-Programmable Custom Computing Machines (FCCM). 93--96.

Digital Library

[5]

P. Brisk et al. 2004. Area-efficient Instruction Set Synthesis for Reconfigurable System-on-chip Designs. In Proceedings of the 41st Annual Design Automation Conference (DAC). 395--400.

Digital Library

[6]

H. Bunke et al. 2002. A Comparison of Algorithms for Maximum Common Subgraph on Randomly Connected Graphs. In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR). 123--132.

Digital Library

[7]

D. Capalija and T. S. Abdelrahman. 2013. A High-performance Overlay Architecture for Pipelined Execution of Data Flow Graphs. In 23rd International Conference on Field Programmable Logic and Applications (FPL). 1--8.

[8]

J. Coole and G. Stitt. 2010. Intermediate Fabrics: Virtual Architectures for Circuit Portability and Fast Placement and Routing. In IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS). 13--22.

Digital Library

[9]

M. Fazlali et al. 2009. High Speed Merged-datapath Design for Run-time Reconfigurable Systems. In 2009 International Conference on Field-Programmable Technology (FPT). 339--343.

[10]

M. Fazlali et al. 2012. Efficient Datapath Merging for the Overhead Reduction of Run-time Reconfigurable Systems. J. Supercomput. 59, 2 (Feb. 2012), 636--657.

Digital Library

[11]

R. Ferreira et al. 2011. An FPGA-based Heterogeneous Coarse-grained Dynamically Reconfigurable Architecture. In Proceedings of the 14th International Conference on Compilers, Architectures and Synthesis for Embedded Systems (CASES). 195--204.

Digital Library

[12]

T. Frangieh et al. 2010. PATIS: Using Partial Configuration to Improve Static FPGA Design Productivity. In 2010 IEEE International Symposium on Parallel Distributed Processing, Workshops and PhD Forum (IPDPSW). 1--8.

[13]

J. B. Goeders et al. 2011. Deterministic Timing-Driven Parallel Placement by Simulated Annealing Using Half-Box Window Decomposition. In 2011 International Conference on Reconfigurable Computing and FPGAs (ReConFig). 41--48.

Digital Library

[14]

M. Gort and J. Anderson. 2014. Design Re-use for Compile Time Reduction in FPGA High-level Synthesis Flows. In 2014 International Conference on FieldProgrammable Technology (FPT). 4--11.

[15]

D. Grant et al. 2011. A CAD Framework for Malibu: An FPGA with Timemultiplexed Coarse-grained Elements. In Proceedings of the 19th ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA). 123--132.

Digital Library

[16]

J. Gray. 2016. GRVI Phalanx: A Massively Parallel RISC-V FPGA Accelerator Accelerator. In IEEE 24th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). 17--20.

[17]

F. Hannig et al. 2014. Invasive Tightly-Coupled Processor Arrays: A DomainSpecific Architecture/Compiler Co-Design Approach. ACM Trans. Embed. Comput. Syst. 13, 4s, Article 133 (April 2014), 29 pages.

Digital Library

[18]

H. J. Hoover et al. 1984. Bounding Fan-out in Logical Networks. J. ACM 31, 1 (Jan 1984), 13--18.

Digital Library

[19]

A. K. Jain et al. 2015. Efficient Overlay Architecture Based on DSP Blocks. In IEEE 23rd Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). 25--28.

Digital Library

[20]

C. Kachris and D. Soudris. 2016. A Survey on Reconfigurable Accelerators for Cloud Computing. In 26th International Conference on Field Programmable Logic and Applications (FPL). 1--10.

[21]

J. Kingyens and J. G. Steffan. 2011. The Potential for a GPU-Like Overlay Architecture for FPGAs. International Journal of Reconfigurable Computing 2011, Article 514581 (2011), 15 pages.

[22]

D. Koch et al. 2013. An Efficient FPGA Overlay for Portable Custom Instruction Set Extensions. In 23rd International Conference on Field Programmable Logic and Applications (FPL). 1--8.

[23]

D. Koch et al. 2016. FPGAs for Software Programmers. Springer International Publishing.

Digital Library

[24]

S. Korf et al. 2011. Automatic HDL-Based Generation of Homogeneous Hard Macros for FPGAs. In IEEE 19th Annual International Symposium on FieldProgrammable Custom Computing Machines (FCCM). 125--132.

Digital Library

[25]

C. Lavin et al. 2013. Improving Clock-rate of Hard-macro Designs. In 2013 International Conference on Field-Programmable Technology (FPT). 246--253.

[26]

C. Liu et al. 2015. Automatic Nested Loop Acceleration on FPGAs Using Soft CGRA Overlay. In 2nd International Workshop on FPGAs for Software Programmer (FSP). 13--18.

[27]

C. Liu et al. 2015. QuickDough: A Rapid FPGA Loop Accelerator Design Framework Using Soft CGRA Overlay. In 2015 International Conference on Field Programmable Technology (FPT). 56--63.

[28]

J. Luu et al. 2014. VTR 7.0: Next Generation Architecture and CAD System for FPGAs. ACM Trans. Reconfigurable Technol. Syst. 7, 2, Article 6 (July 2014), 30 pages.

Digital Library

[29]

Y. O. M. Moctar and P. Brisk. 2014. Parallel FPGA routing based on the Operator Formulation. In 51st ACM/EDAC/IEEE Design Automation Conference (DAC). 1--6.

Digital Library

[30]

N. Moreano et al. 2005. Efficient Datapath Merging for Partially Reconfigurable Architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 24, 7 (July 2005), 969--980.

Digital Library

[31]

C. Mulpuri and S. Hauck. 2001. Runtime and Quality Tradeoffs in FPGA Placement and Routing. In Proceedings of the ACM/SIGDA Ninth International Symposium on Field Programmable Gate Arrays (FPGA). 29--36.

Digital Library

[32]

H. C. Ng et al. 2016. A Soft Processor Overlay with Tightly-coupled FPGA Accelerator. In 2nd International Workshop on Overlay Architectures for FPGAs (OLAF). 31--36.

[33]

H. C. Ng et al. 2017. Reconfigurable Acceleration of Genetic Sequence Alignment: A Survey of Two Decades of Efforts. In 27th International Conference on Field Programmable Logic and Applications (FPL). 1--8.

[34]

B. O'Sullivan. 2009. Mercurial: The Definitive Guide. O'Reilly Media.

Digital Library

[35]

N. Pothineni et al. 2010. A High-level Synthesis Flow for Custom Instruction Set Extensions for Application-specific Processors. In 15th Asia and South Pacific Design Automation Conference (ASP-DAC). 707--712.

Digital Library

[36]

J. Rose et al. 2012. The VTR Project: Architecture and CAD for FPGAs from Verilog to Routing. In Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA). 77--86.

Digital Library

[37]

J. H. Rutgers et al. 2010. An Approximate Maximum Common Subgraph Algorithm for Large Digital Circuits. In 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools. 699--705.

Digital Library

[38]

N. Shirazi et al. 1998. Automating Production of Run-time Reconfigurable Designs. In Proceedings. IEEE Symposium on FPGAs for Custom Computing Machines (FCCM). 147--156.

Digital Library

[39]

I. Skliarova and A. de Brito Ferrari. 2004. Reconfigurable Hardware SAT Solvers: A Survey of Systems. IEEE Trans. Comput. 53, 11 (Nov 2004), 1449--1461.

Digital Library

[40]

C. C. de Souza et al. 2005. The Datapath Merging Problem in Reconfigurable Systems: Complexity, Dual Bounds and Heuristic Evaluation. J. Exp. Algorithmics 10 (Dec 2005).

Digital Library

[41]

S. Takamaeda-Yamazaki. 2015. Pyverilog: A Python-Based Hardware Design Processing Toolkit for Verilog HDL. In Applied Reconfigurable Computing: 11th International Symposium (ARC). 451--460.

[42]

J. S. Targett et al. 2015. Lower Precision for Higher Accuracy: Precision and Resolution Exploration for Shallow Water Equations. In 2015 International Conference on Field Programmable Technology (FPT). 208--211.

[43]

G. Venkatesh et al. 2010. Conservation Cores: Reducing the Energy of Mature Computations. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). 205--218.

Digital Library

[44]

N. Voss et al. 2016. Automated Dataflow Graph Merging. In 2016 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation (SAMOS). 219--226.

[45]

M. Zuluaga and N. Topham. 2008. Resource Sharing in Custom Instruction Set Extensions. In 2008 Symposium on Application Specific Processors (ASAP). 7--13.

Digital Library

Cited By

Bhargavi MSiddharth Rokkam SParameswaran SJ S(2024)Automated Design and Configuration of RISC-V based NoC-MPSoC Framework on FPGA2024 28th International Symposium on VLSI Design and Test (VDAT)10.1109/VDAT63601.2024.10705744(1-6)Online publication date: 1-Sep-2024
https://doi.org/10.1109/VDAT63601.2024.10705744
Ng HColeman ILiu SLuk WShannon LAdler M(2021)Reconfigurable Acceleration of Short Read Mapping with Biological ConsiderationThe 2021 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/3431920.3439280(229-239)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3431920.3439280
Iqbal MParvez HHussain FRashid M(2020)An Application Specific Reconfigurable Architecture with Reduced Area and Static Memory CellsJournal of Circuits, Systems and Computers10.1142/S0218126621500651(2150065)Online publication date: 2-Sep-2020
https://doi.org/10.1142/S0218126621500651
Show More Cited By

Index Terms

ADAM: Automated Design Analysis and Merging for Speeding up FPGA Development
1. Computer systems organization
  1. Architectures
    1. Other architectures
      1. Heterogeneous (hybrid) systems
      2. Reconfigurable computing
2. Hardware
  1. Electronic design automation
    1. Hardware description languages and compilation
    2. High-level and register-transfer level synthesis
      1. Datapath optimization
      2. Resource binding and sharing

Recommendations

A scalable routability-driven analytical placer with global router integration for FPGAs (abstract only)
FPGA '14: Proceedings of the 2014 ACM/SIGDA international symposium on Field-programmable gate arrays

As the sizes of modern circuits become bigger and bigger, implementing those large circuits into FPGA becomes arduous. The state-of-the-art academic FPGA place-and-route tool, VPR, has good quality but needs around a whole day to complete a placement ...
UTPlaceF 2.0: A High-Performance Clock-Aware FPGA Placement Engine
Special Section on Advances in Physical Design Automation and Regular Papers

Modern field-programmable gate array (FPGA) devices contain complex clock architectures on top of configurable logics. Unlike application specific integrated circuits (ASICs), the physical structure of clock networks in an FPGA is pre-manufactured and ...
An efficient and effective analytical placer for FPGAs
DAC '13: Proceedings of the 50th Annual Design Automation Conference

The increasing design complexity of modern circuits has made traditional FPGA placement techniques not efficient anymore. To improve the scalability, commercial FPGA placement tools have started migrating to analytical placement. In this paper, we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FPGA '18: Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

February 2018

310 pages

ISBN:9781450356145

DOI:10.1145/3174243

General Chair:
Jason H. Anderson
University of Toronto, Canada
,
Program Chair:
Kia Bazargan
University of Minnesota, USA

Copyright © 2018 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: 15 February 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Horizon 2020 Framework Programme
Lee Family Scholarship
Engineering and Physical Sciences Research Council

Conference

FPGA '18

Sponsor:

SIGDA

FPGA '18: The 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

February 25 - 27, 2018

CALIFORNIA, Monterey, USA

Acceptance Rates

FPGA '18 Paper Acceptance Rate 10 of 116 submissions, 9%;

Overall Acceptance Rate 125 of 627 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
400
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)5

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bhargavi MSiddharth Rokkam SParameswaran SJ S(2024)Automated Design and Configuration of RISC-V based NoC-MPSoC Framework on FPGA2024 28th International Symposium on VLSI Design and Test (VDAT)10.1109/VDAT63601.2024.10705744(1-6)Online publication date: 1-Sep-2024
https://doi.org/10.1109/VDAT63601.2024.10705744
Ng HColeman ILiu SLuk WShannon LAdler M(2021)Reconfigurable Acceleration of Short Read Mapping with Biological ConsiderationThe 2021 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/3431920.3439280(229-239)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3431920.3439280
Iqbal MParvez HHussain FRashid M(2020)An Application Specific Reconfigurable Architecture with Reduced Area and Static Memory CellsJournal of Circuits, Systems and Computers10.1142/S0218126621500651(2150065)Online publication date: 2-Sep-2020
https://doi.org/10.1142/S0218126621500651
Ng HLiu SColeman IChu RYue MLuk W(2020)Acceleration of Short Read Alignment with Runtime Reconfiguration2020 International Conference on Field-Programmable Technology (ICFPT)10.1109/ICFPT51103.2020.00044(256-262)Online publication date: Dec-2020
https://doi.org/10.1109/ICFPT51103.2020.00044
Wilson DStitt G(2019)Seiba: An FPGA Overlay-Based Approach to Rapid Application Development2019 International Conference on ReConFigurable Computing and FPGAs (ReConFig)10.1109/ReConFig48160.2019.8994693(1-8)Online publication date: Dec-2019
https://doi.org/10.1109/ReConFig48160.2019.8994693
Mahajan DPatil SShashikant WDangayach MBhanu PSoumya J(2019)Design Automation of Network-on-Chip Prototype on FPGA2019 IEEE International Conference on Distributed Computing, VLSI, Electrical Circuits and Robotics (DISCOVER)10.1109/DISCOVER47552.2019.9008005(1-4)Online publication date: Aug-2019
https://doi.org/10.1109/DISCOVER47552.2019.9008005
Bragança LAlves FPenha JCoimbra GFerreira RNacif JMudge TPnevmatikatos D(2018)Simplifying HW/SW integration to deploy multiple accelerators for CPU-FPGA heterogeneous platformsProceedings of the 18th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation10.1145/3229631.3229651(97-104)Online publication date: 15-Jul-2018
https://dl.acm.org/doi/10.1145/3229631.3229651
Fan HLiu SFerianc MNg HQue ZLiu SNiu XLuk W(2018)A Real-Time Object Detection Accelerator with Compressed SSDLite on FPGA2018 International Conference on Field-Programmable Technology (FPT)10.1109/FPT.2018.00014(14-21)Online publication date: Dec-2018
https://doi.org/10.1109/FPT.2018.00014
Zhao RNg HLuk WNiu X(2018)Towards Efficient Convolutional Neural Network for Domain-Specific Applications on FPGA2018 28th International Conference on Field Programmable Logic and Applications (FPL)10.1109/FPL.2018.00033(147-1477)Online publication date: Aug-2018
https://doi.org/10.1109/FPL.2018.00033

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