Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3626202.3637572acmconferencesArticle/Chapter ViewAbstractPublication PagesfpgaConference Proceedingsconference-collections
research-article

From Topology to Realization in FPGA/VPR Routing

Published: 02 April 2024 Publication History

Abstract

Versatile Place and Route (VPR) enabled the exploration of diverse FPGA architectures. OpenFPGA extended VPR through bitstream generation and added silicon compilation. Our work is one of several efforts to use this combination to build commercial devices, which, to achieve competitiveness, has necessitated several improvements to routing and elsewhere for area, power, and performance. Fitting to the MCNC and VTR benchmarks using this work, our first improved routing pattern yields a 22% reduction in metal loading, a 14% reduction in routing multiplexer input pin count per function tile, and a 10% reduction in source to farthest sink paths. For this, routed length increased 5%, the proportion of net detours increased 11%, router heap operations increased 16%, and router iterations increased 42%, as the unmodified VPR router worked harder on routing with fewer switches but without introducing any routing failures. This work provides the first steps to a routing compiler for OpenFPGA/VPR, much as ASIC/SoC flows use a memory compiler.

References

[1]
Benjamin L.C. Barzen, Arya Reais-Parsi, Eddie Hung, Minwoo Kang, Alan Mishchenko, Jonathan W. Greene, and John Wawrzynek. 2023. Narrowing the Synthesis Gap: Academic FPGA Synthesis is Catching Up With the Industry. In 2023 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE Press, Westminster, CO, USA, 1--6. https://doi.org/10.23919/DATE56975.2023. 10137310
[2]
Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Daniel Rehfeldt, Steffan Schlein, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Boro Sofranac, Mark Turner, Stefan Vigerske, Fabian Wegscheider, Philipp Wellner, Dieter Weninger, and Jakob Witzig. 2021. The SCIP Optimization Suite 8.0. Technical Report. Optimization Online. http://www.optimizationonline. org/DB_HTML/2021/12/8728.html
[3]
V. Betz and J. Rose. 1996. Directional bias and non-uniformity in FPGA global routing architectures. In Proceedings of International Conference on Computer Aided Design. IEEE Press, Westminster, CO, USA, 652--659. https://doi.org/10. 1109/ICCAD.1996.571342
[4]
Vaughn Betz and Jonathan Rose. 1997. VPR: A New Packing, Placement and Routing Tool for FPGA Research. In Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications (FPL '97). Springer-Verlag, Berlin, Heidelberg, 213--222.
[5]
Vaughn Betz and Jonathan Rose. 1999. FPGA Routing Architecture: Segmentation and Buffering to Optimize Speed and Density. In Proceedings of the 1999 ACM/SIGDA Seventh International Symposium on Field Programmable Gate Arrays (Monterey, California, USA) (FPGA '99). Association for Computing Machinery, New York, NY, USA, 59--68. https://doi.org/10.1145/296399.296428
[6]
Vaughn Betz and Jonathan Rose. 2000. Automatic Generation of FPGA Routing Architectures from High-Level Descriptions. In Proceedings of the 2000 ACM/SIGDA Eighth International Symposium on Field Programmable Gate Arrays (Monterey, California, USA) (FPGA '00). Association for Computing Machinery, New York, NY, USA, 175--184. https://doi.org/10.1145/329166.329203
[7]
Andrew Boutros and Vaughn Betz. 2021. FPGA Architecture: Principles and Progression. IEEE Circuits and Systems Magazine 21, 2 (2021), 4--29. https: //doi.org/10.1109/MCAS.2021.3071607
[8]
Shant Chandrakar, Dinesh Gaitonde, and Trevor Bauer. 2015. Enhancements in UltraScale CLB Architecture. In Proceedings of the 2015 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (Monterey, California, USA) (FPGA '15). Association for Computing Machinery, New York, NY, USA, 108--116. https://doi.org/10.1145/2684746.2689077
[9]
Yao-Wen Chang, D. F. Wong, and C. K. Wong. 1996. Universal Switch Modules for FPGA Design. ACM Trans. Des. Autom. Electron. Syst. 1, 1 (jan 1996), 80--101. https://doi.org/10.1145/225871.225886
[10]
Gengjie Chen, Chak-Wa Pui, Wing-Kai Chow, Ka-Chun Lam, Jian Kuang, Evangeline F. Y. Young, and Bei Yu. 2018. RippleFPGA: Routability-Driven Simultaneous Packing and Placement for Modern FPGAs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 37, 10 (2018), 2022--2035. https://doi.org/10.1109/TCAD.2017.2778058
[11]
Jeffrey Chromczak, Mark Wheeler, Charles Chiasson, Dana How, Martin Langhammer, Tim Vanderhoek, Grace Zgheib, and Ilya Ganusov. 2020. Architectural Enhancements in Intel® Agilex? FPGAs. In Proceedings of the 2020 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (Seaside, CA, USA) (FPGA '20). Association for Computing Machinery, New York, NY, USA, 140--149. https://doi.org/10.1145/3373087.3375308
[12]
Chris Chu and Yiu-Chung Wong. 2008. FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27, 1 (2008), 70--83. https://doi.org/10.1109/TCAD.2007.907068
[13]
Marshall L. Fisher, R. Jaikumar, and Luk N. Van Wassenhove. 1986. A Multiplier Adjustment Method for the Generalized Assignment Problem. Management Science 32, 9 (1986), 1095--1103. http://www.jstor.org/stable/2631537
[14]
Brian Gaide, Dinesh Gaitonde, Chirag Ravishankar, and Trevor Bauer. 2019. Xilinx Adaptive Compute Acceleration Platform: VersalTM Architecture. In Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (Seaside, CA, USA) (FPGA '19). Association for Computing Machinery, New York, NY, USA, 84--93. https://doi.org/10.1145/3289602.3293906
[15]
A. E. Gamal. 1981. Two-dimensional stochastic model for interconnections in master slice integrated circuits. IEEE Transactions on Circuits and Systems 28, 2 (1981), 127--138. https://doi.org/10.1109/TCS.1981.1084958
[16]
Robert Garfinkel and George Nemhauser. 1972. Integer Programming. John Wiley & Sons, New York, NY.
[17]
gnu.org. 2023. GLPK (GNU Linear Programming Kit). Retrieved September 28, 2023 from https://www.gnu.org/software/glpk/
[18]
Jonathan W. Greene. 2023. FPGA Mux Usage and Routability Estimates without Explicit Routing. In Proceedings of the 2023 ACM/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, CA, USA) (FPGA '23). Association for Computing Machinery, New York, NY, USA, 141--147. https://doi.org/10. 1145/3543622.3573045
[19]
ibm.com. 2023. LP file format: algebraic representation. Retrieved September 28, 2023 from https://www.ibm.com/docs/en/icos/20.1.0?topic=cplex-lp-file-formatalgebraic- representation
[20]
David L. Johannsen. 1981. Silicon Compilation. Ph.D. Dissertation. California Institute of Technology, Pasadena, CA. https://doi.org/10.7907/32ha-8453
[21]
Jin Hee Kim and Jason H. Anderson. 2015. Synthesizable FPGA fabrics targetable by the Verilog-to-Routing (VTR) CAD flow. In 2015 25th International Conference on Field Programmable Logic and Applications (FPL). IEEE Press,Westminster, CO, USA, 1--8. https://doi.org/10.1109/FPL.2015.7293955
[22]
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. 1983. Optimization by Simulated Annealing. Science 220, 4598 (1983), 671--680. https://doi.org/10.1126/science.220. 4598.671 arXiv:https://www.science.org/doi/pdf/10.1126/science.220.4598.671
[23]
Dirk Koch, Nguyen Dao, Bea Healy, Jing Yu, and Andrew Attwood. 2021. FABulous: An Embedded FPGA Framework. In The 2021 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (Virtual Event, USA) (FPGA '21). Association for Computing Machinery, New York, NY, USA, 45--56. https://doi.org/10.1145/3431920.3439302
[24]
Irving Langmuir and R. N. Hall. 1968. Pathological Science, December 18, 1953 Colloquium. Technical Report 68-C-035. The Knolls Research Laboratory, General Electric. Retrieved September 28, 2023 from https://www.cs.princeton.edu/~ken/ Langmuir/langmuir.htm
[25]
Guy Lemieux and Stephen Brown. 1993. A detailed routing algorithm for allocating wire segments in field-programmable gate arrays. In Proceedings of the 1993 ACM/SIGDA Physical Design Workshop (Lake Arrowhead, CA). Association for Computing Machinery, New York, NY, USA, 215--226.
[26]
Ang Li and David Wentzlaff. 2021. PRGA: An Open-Source FPGA Research and Prototyping Framework. In The 2021 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (Virtual Event, USA) (FPGA '21). Association for Computing Machinery, New York, NY, USA, 127--137. https://doi.org/10.1145/ 3431920.3439294
[27]
Wuxi Li, Yibo Lin, and David Z. Pan. 2019. elfPlace: Electrostatics-based Placement for Large-Scale Heterogeneous FPGAs. In Proceedings of the 2019 IEEE/ACM International Conference on Computer-Aided Design (Westminster, CO, USA) (ICCAD '19). IEEE Press, Westminster, CO, USA, 1--8. https://doi.org/10.1109/ ICCAD45719.2019.8942075
[28]
Mingjie Lin, John Wawrzynek, and Abbas El Gamal. 2010. Exploring FPGA Routing Architecture Stochastically. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 29, 10 (2010), 1509--1522. https://doi.org/10. 1109/TCAD.2010.2061530
[29]
Jason Luu, Jeffrey Goeders, Michael Wainberg, Andrew Somerville, Thien Yu, Konstantin Nasartschuk, Miad Nasr, Sen Wang, Tim Liu, Nooruddin Ahmed, Kenneth B. Kent, Jason Anderson, Jonathan Rose, and Vaughn Betz. 2014. VTR 7.0: Next Generation Architecture and CAD System for FPGAs. ACM Trans. Reconfigurable Technol. Syst. 7, 2, Article 6 (jul 2014), 30 pages. https://doi.org/ 10.1145/2617593
[30]
Jason Luu, Ian Kuon, Peter Jamieson, Ted Campbell, Andy Ye, Wei Mark Fang, Kenneth Kent, and Jonathan Rose. 2011. VPR 5.0: FPGA CAD and Architecture Exploration Tools with Single-Driver Routing, Heterogeneity and Process Scaling. ACM Trans. Reconfigurable Technol. Syst. 4, 4, Article 32 (dec 2011), 23 pages. https://doi.org/10.1145/2068716.2068718
[31]
Jason Luu, Jonathan Rose, and Jason Anderson. 2014. Towards Interconnect- Adaptive Packing for FPGAs. In Proceedings of the 2014 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (Monterey, California, USA) (FPGA '14). Association for Computing Machinery, New York, NY, USA, 21--30. https://doi.org/10.1145/2554688.2554783
[32]
M. Imran Masud and Steven J. E. Wilton. 1999. A NewSwitch Block for Segmented FPGAs. In Proceedings of the 9th International Workshop on Field-Programmable Logic and Applications (FPL '99). Springer-Verlag, Berlin, Heidelberg, 274--281.
[33]
L. McMurchie and C. Ebeling. 1995. PathFinder: A Negotiation-Based Performance-Driven Router for FPGAs. In Third International ACM Symposium on Field-Programmable Gate Arrays. IEEE Press, Westminster, CO, USA, 111--117. https://doi.org/10.1109/FPGA.1995.242049
[34]
Carver Mead and Lynn Conway. 1980. Introduction to VLSI Systems. Addison- Wesley, Reading, MA.
[35]
Amin Mohaghegh and Vaughn Betz. 2023. Tear Down The Wall: Unified and Efficient Intra- and Inter-Cluster Routing for FPGAs. In 2023 33rd International Conference on Field-Programmable Logic and Applications (FPL). IEEE Press, Westminster, CO, USA, 130--136. https://doi.org/10.1109/FPL60245.2023.00026
[36]
Prashanth Mohan, Oguz Atli, Onur Kibar, Mohammed Zackriya, Larry Pileggi, and Ken Mai. 2021. Top-down Physical Design of Soft Embedded FPGA Fabrics. In The 2021 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (Virtual Event, USA) (FPGA '21). Association for Computing Machinery, New York, NY, USA, 1--10. https://doi.org/10.1145/3431920.3439297
[37]
Kevin E. Murray, Oleg Petelin, Sheng Zhong, Jia MinWang, Mohamed Eldafrawy, Jean-Philippe Legault, Eugene Sha, Aaron G. Graham, Jean Wu, Matthew J. P. Walker, Hanqing Zeng, Panagiotis Patros, Jason Luu, Kenneth B. Kent, and Vaughn Betz. 2020. VTR 8: High-Performance CAD and Customizable FPGA Architecture Modelling. ACM Trans. Reconfigurable Technol. Syst. 13, 2, Article 9 (jun 2020), 55 pages. https://doi.org/10.1145/3388617
[38]
Kevin E. Murray, Sheng Zhong, and Vaughn Betz. 2020. AIR: A Fast but Lazy Timing-Driven FPGA Router. In 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC). IEEE Press, Westminster, CO, USA, 338--344. https://doi.org/10.1109/ASP-DAC47756.2020.9045175
[39]
Stefan Nikolic and Paolo Ienne. 2023. Regularity Matters: Designing Practical FPGA Switch-Blocks. In Proceedings of the 2023 ACM/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, CA, USA) (FPGA '23). Association for Computing Machinery, New York, NY, USA, 99--109. https: //doi.org/10.1145/3543622.3573192
[40]
Stefan Nikolic and Paolo Ienne. 2021. Turning PathFinder Upside-Down: Exploring FPGA Switch-Blocks by Negotiating Switch Presence. In 2021 31st International Conference on Field-Programmable Logic and Applications (FPL). IEEE Press, Westminster, CO, USA, 225--233. https://doi.org/10.1109/FPL53798.2021.00044
[41]
June S. Park, Byung Ha Lim, and Youngho Lee. 1998. A Lagrangian Dual-Based Branch-and-Bound Algorithm for the Generalized Multi-Assignment Problem. Management Science 44, 12 (1998), S271--S282. http://www.jstor.org/stable/779730
[42]
Morten B. Petersen, Stefan Nikolic, and Mirjana Stojilovic. 2021. NetCracker: A Peek into the Routing Architecture of Xilinx 7-Series FPGAs. In The 2021 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (Virtual Event, USA) (FPGA '21). Association for Computing Machinery, New York, NY, USA, 11--22. https://doi.org/10.1145/3431920.3439285
[43]
Jiadong Qian, Yuhang Shen, Kaichuang Shi, Hao Zhou, and Lingli Wang. 2021. General routing architecture modelling and exploration for modern FPGAs. In 2021 International Conference on Field-Programmable Technology (ICFPT). IEEE Press, Westminster, CO, USA, 1--9. https://doi.org/10.1109/ICFPT52863.2021. 9609935
[44]
J. Rose and S. Brown. 1990. The effect of switch box flexibility on routability of field programmable gate arrays. In IEEE Proceedings of the Custom Integrated Circuits Conference (Boston, MA). IEEE Press, Westminster, CO, USA, 27.5/1-- 27.5/4. https://doi.org/10.1109/CICC.1990.124814
[45]
Jonathan Rose, Zvenko Vranesic, and Steven J. E. Wilton. 1997. Architectures and algorithms for field-programmable gate arrays with embedded memory. Ph.D. Dissertation. University of Toronto, Toronto, ON M5S 1A1, Canada. https: //api.semanticscholar.org/CorpusID:60687366
[46]
Raphael Y. Rubin and André M. DeHon. 2011. Timing-Driven Pathfinder Pathology and Remediation: Quantifying and Reducing Delay Noise in VPR-Pathfinder. In Proceedings of the 19th ACM/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, CA, USA) (FPGA '11). Association for Computing Machinery, New York, NY, USA, 173--176. https://doi.org/10.1145/1950413. 1950447
[47]
Herman Schmit and Vikas Chandra. 2002. FPGA Switch Block Layout and Evaluation. In Proceedings of the 2002 ACM/SIGDA Tenth International Symposium on Field-Programmable Gate Arrays (Monterey, California, USA) (FPGA '02). Association for Computing Machinery, New York, NY, USA, 11--18. https: //doi.org/10.1145/503048.503051
[48]
Kaichuang Shi, Hao Zhou, Xuegong Zhou, and Lingli Wang. 2020. GIB: A Novel Unidirectional Interconnection Architecture for FPGA. In 2020 International Conference on Field-Programmable Technology (ICFPT). IEEE Press, Westminster, CO, USA, 174--181. https://doi.org/10.1109/ICFPT51103.2020.00032
[49]
Kaichuang Shi, Xuegong Zhou, Hao Zhou, and Lingli Wang. 2022. An Optimized GIB Routing Architecture with Bent Wires for FPGA. ACM Trans. Reconfigurable Technol. Syst. 16, 1, Article 2 (dec 2022), 28 pages. https://doi.org/10.1145/3519599
[50]
Xifan Tang. 2020. Additional Syntax to Original VPR XML. University of Utah. Retrieved September 28, 2023 from https://openfpga.readthedocs.io/en/master/ manual/arch_lang/addon_vpr_syntax/#cmdoption-arg-tileable
[51]
Xifan Tang, Edouard Giacomin, Aurélien Alacchi, Baudouin Chauviere, and Pierre-Emmanuel Gaillardon. 2019. OpenFPGA: An Opensource Framework Enabling Rapid Prototyping of Customizable FPGAs. In 2019 29th International Conference on Field Programmable Logic and Applications (FPL) (Barcelona, Spain). ACM, New York, NY, 367--374. https://doi.org/10.1109/FPL.2019.00065
[52]
Xifan Tang, Edouard Giacomin, Aurélien Alacchi, and Pierre-Emmanuel Gaillardon. 2019. A Study on Switch Block Patterns for Tileable FPGA Routing Architectures. In 2019 International Conference on Field-Programmable Technology (ICFPT) (Tianjin, China). IEEE Press, Westminster, CO, USA, 247--250. https://doi.org/10.1109/ICFPT47387.2019.00039
[53]
OpenFPGA team. 2023. OpenFPGA Version v1.2.1214. University of Utah. Retrieved July 20, 2023 from https://github.com/lnis-uofu/OpenFPGA/commit/ ae9190f0518383a3d58e103a76cfeef067580f12
[54]
VTR team. 2023. vtr-verilog-to-routing (VTR) Version 8.0.0. University of Toronto. Retrieved June 7, 2023 from https://github.com/verilog-to-routing/vtr-verilogto- routing/commit/0963c20472e178d6562e40d90727870342035f67
[55]
Stephen Trimberger. 2015. Three Ages of FPGAs: A Retrospective on the First Thirty Years of FPGA Technology. Proc. IEEE 103, 3 (March 2015), 318--331. https://doi.org/10.1109/JPROC.2015.2392104
[56]
Jeffrey Tyhach, Mike Hutton, Sean Atsatt, Arifur Rahman, Brad Vest, David Lewis, Martin Langhammer, Sergey Shumarayev, Tim Hoang, Allen Chan, Dong-Myung Choi, Dan Oh, Hae-Chang Lee, Jack Chui, Ket Chiew Sia, Edwin Kok, Wei-Yee Koay, and Boon-Jin Ang. 2015. Arria?10 device architecture. In 2015 IEEE Custom Integrated Circuits Conference (CICC). IEEE Press, Westminster, CO, USA, 1--8. https://doi.org/10.1109/CICC.2015.7338368
[57]
Takao Uehara and William M. vanCleemput. 1979. Optimal Layout of CMOS Functional Arrays. In Proceedings of the 16th Design Automation Conference (San Diego, CA, USA) (DAC '79). IEEE Press, Westminster, CO, USA, 287--289.
[58]
Elias Vansteenkiste, Alireza Kaviani, and Henri Fraisse. 2015. Analyzing the divide between FPGA academic and commercial results. In 2015 International Conference on Field Programmable Technology (FPT). IEEE Press, Westminster, CO, USA, 96--103. https://doi.org/10.1109/FPT.2015.7393137
[59]
Andy Yan, Rebecca Cheng, and Steven J. E. Wilton. 2002. On the Sensitivity of FPGA Architectural Conclusions to Experimental Assumptions, Tools, and Techniques. In Proceedings of the 2002 ACM/SIGDA Tenth International Symposium on Field-Programmable Gate Arrays (Monterey, California, USA) (FPGA '02). Association for Computing Machinery, New York, NY, USA, 147--156. https://doi.org/10.1145/503048.503071
[60]
Saeyang Yang. 1991. Logic Synthesis and Optimization Benchmarks User Guide: Version 3.0. Technical Report. Microelectronics Center of North Carolina (MCNC). 96

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
FPGA '24: Proceedings of the 2024 ACM/SIGDA International Symposium on Field Programmable Gate Arrays
April 2024
300 pages
ISBN:9798400704185
DOI:10.1145/3626202
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 the author(s) 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 April 2024

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. constraint
  2. ilp
  3. interconnect
  4. layout
  5. multiplexer
  6. optimization
  7. regularity
  8. routability

Qualifiers

  • Research-article

Conference

FPGA '24
Sponsor:

Acceptance Rates

Overall Acceptance Rate 125 of 627 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 149
    Total Downloads
  • Downloads (Last 12 months)149
  • Downloads (Last 6 weeks)23
Reflects downloads up to 20 Nov 2024

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media