More Web Proxy on the site http://driver.im/

research-article

An Optimized GIB Routing Architecture with Bent Wires for FPGA

Authors:

Lingli WangAuthors Info & Claims

ACM Transactions on Reconfigurable Technology and Systems, Volume 16, Issue 1

Article No.: 2, Pages 1 - 28

https://doi.org/10.1145/3519599

Published: 22 December 2022 Publication History

Abstract

Field-programmable gate arrays (FGPAs) are widely used because of the superiority in flexibility and lower non-recurring engineering cost. How to optimize the routing architecture is a key problem for FPGA architects because it has a large impact on FPGA area, delay, and routability. In academia, the routing architecture is mainly based on the connection blocks (CBs) and switch blocks (SBs), whereas most research has focused on SB architectures, such as Wilton, Universal, and Disjoint SB patterns. In this article, we propose a novel unidirectional routing architecture—general interconnection block (GIB)—to improve FPGA performance. With the GIB architecture, logic block (LB) pins can directly connect with the adjacent GIBs without programmable switches. Inside a GIB, LB pins can connect to the routing channel tracks on the four sides of a GIB. In particular, the logic pins from different neighboring LBs that connect to the same GIB can connect with each other with only one programmable switch. In addition, we enhance VTR to support the GIB with bent wires and develop a searching framework based on the simulated annealing algorithm to search for a near-optimal distribution of wire types. We evaluate the GIB architecture on VTR 8 with the provided benchmark circuits. The experimental results show that the GIB architecture with length-4 wires can achieve 9.5% improvement on the critical path delay and 11.1% improvement on the area-delay product compared to the VTR CB-SB architecture with length-4 wires. After exploring mixed wire types, the optimized GIB architecture can further improve the delay by 16.4% and area-delay product by 17.1% compared to the CB-SB architecture with length-4 wires.

References

[1]

Vaughn Betz and Jonathan Rose. 1999. FPGA routing architecture: Segmentation and buffering to optimize speed and density. In Proceedings of the ACM/SIGDA 7th International Symposium on Field-Programmable Gate Arrays. 59–68.

Digital Library

[2]

Vaughn Betz, Jonathan Rose, and Alexander Marquardt. 1999. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic.

[3]

Alexander Brant and Guy G. F. Lemieux. 2012. ZUMA: An open FPGA overlay architecture. In Proceedings of the 2012 IEEE 20th International Symposium on Field-Programmable Custom Computing Machines. IEEE, Los Alamitos, CA, 93–96.

Digital Library

[4]

Yao-Wen Chang, D. F. Wong, and Chak-Kuen Wong. 1996. Universal switch modules for FPGA design. ACM Transactions on Design Automation of Electronic Systems 1, 1 (1996), 80–101.

Digital Library

[5]

Yao-Wen Chang, Kai Zhu, and D. F. Wong. 2000. Timing-driven routing for symmetrical array-based FPGAs. ACM Transactions on Design Automation of Electronic Systems 5, 3 (2000), 433–450.

Digital Library

[6]

Sumanta Chaudhuri. 2009. Diagonal tracks in FPGAs: A performance evaluation. In Proceedings of the ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 245–248.

Digital Library

[7]

Charles Chiasson. 2013. Optimization and Modeling of FPGA Circuitry in Advanced Process Technology. Master’s Thesis. Graduate Department of Electrical and Computer Engineering, University of Toronto.

[8]

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. 140–149.

Digital Library

[9]

Altera Corporation. 2011. Stratix IV Device Handbook, Vol. 1. Altera Corporation.

[10]

Soumya Eachempati, Arthur Nieuwoudt, Aman Gayasen, Narayanan Vijaykrishnan, and Yehia Massoud. 2007. Assessing carbon nanotube bundle interconnect for future FPGA architectures. In Proceedings of the 2007 Design, Automation, and Test in Europe Conference and Exhibition. IEEE, Los Alamitos, CA, 1–6.

[11]

Wenyi Feng and Sinan Kaptanoglu. 2008. Designing efficient input interconnect blocks for LUT clusters using counting and entropy. ACM Transactions on Reconfigurable Technology and Systems 1, 1 (2008), 1–28.

Digital Library

[12]

Brian Gaide, Dinesh Gaitonde, Chirag Ravishankar, and Trevor Bauer. 2019. Xilinx adaptive compute acceleration platform: Versal™ architecture. In Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 84–93.

Digital Library

[13]

Chengyu Hu, Qinghua Duan, Peng Lu, Wei Liu, Jian Wang, and Jinmei Lai. 2020. A tile-based interconnect model for FPGA architecture exploration. In Proceedings of the 2020 Great Lakes Symposium on VLSI. 113–118.

Digital Library

[14]

Peter Jamieson, Wayne Luk, Steve J. E. Wilton, and George A. Constantinides. 2009. An energy and power consumption analysis of FPGA routing architectures. In Proceedings of the 2009 International Conference on Field-Programmable Technology. IEEE, Los Alamitos, CA, 324–327.

[15]

Tanay Karnik and Sung-Mo Kang. 1995. An empirical model for accurate estimation of routing delay in FPGAs. In Proceedings of the IEEE International Conference on Computer Aided Design (ICCAD’95). IEEE, Los Alamitos, CA, 328–331.

[16]

Muhammad Khellah, Stephen Brown, and Zvonko Vranesic. 1993. Modelling routing delays in SRAM-based FPGAs. In Proceedings of the Canadian Conference on VLSI. 6B.

[17]

Scott Kirkpatrick, C. Daniel Gelatt, and Mario P. Vecchi. 1983. Optimization by simulated annealing. Science 220, 4598 (1983), 671–680.

[18]

Ian Kuon and Jonathan Rose. 2007. Measuring the gap between FPGAs and ASICs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 26, 2 (2007), 203–215.

Digital Library

[19]

Guy Lemieux, Edmund Lee, Marvin Tom, and Anthony Yu. 2004. Directional and single-driver wires in FPGA interconnect. In Proceedings of the 2004 IEEE International Conference on Field-Programmable Technology (IEEE Cat. No. 04EX921). IEEE, Los Alamitos, CA, 41–48.

[20]

Guy Lemieux and David Lewis. 2001. Using sparse crossbars within LUT. In Proceedings of the 2001 ACM/SIGDA 9th International Symposium on Field-Programmable Gate Arrays. 59–68.

Digital Library

[21]

Guy G. Lemieux, Stephen D. Brown, and Daniel Vranesic. 1997. On two-step routing for FPGAs. In Proceedings of the 1997 International Symposium on Physical Design. 60–66.

Digital Library

[22]

Guy G. Lemieux and David M. Lewis. 2002. Analytical framework for switch block design. In Proceedings of the International Conference on Field-Programmable Logic and Applications. 122–131.

[23]

David Lewis, Elias Ahmed, Gregg Baeckler, Vaughn Betz, Mark Bourgeault, David Cashman, David Galloway, et al. 2005. The Stratix II logic and routing architecture. In Proceedings of the 2005 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 14–20.

Digital Library

[24]

David Lewis, Elias Ahmed, David Cashman, Tim Vanderhoek, Chris Lane, Andy Lee, and Philip Pan. 2009. Architectural enhancements in Stratix-III™ and Stratix-IV™. In Proceedings of the ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 33–42.

Digital Library

[25]

David Lewis, Vaughn Betz, David Jefferson, Andy Lee, Chris Lane, Paul Leventis, Sandy Marquardt, et al. 2003. The Stratix™ routing and logic architecture. In Proceedings of the 2003 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 12–20.

Digital Library

[26]

David Lewis, David Cashman, Mark Chan, Jeffery Chromczak, Gary Lai, Andy Lee, Tim Vanderhoek, and Haiming Yu. 2013. Architectural enhancements in Stratix V™. In Proceedings of the ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 147–156.

Digital Library

[27]

David Lewis, Gordon Chiu, Jeffrey Chromczak, David Galloway, Ben Gamsa, Valavan Manohararajah, Ian Milton, Tim Vanderhoek, and John Van Dyken. 2016. The Stratix™ 10 highly pipelined FPGA architecture. In Proceedings of the 2016 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 159–168.

Digital Library

[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.

Digital Library

[29]

Lee-Chung Lu. 2017. Physical design challenges and innovations to meet power, speed, and area scaling trend. In Proceedings of the 2017 ACM International Symposium on Physical Design. 63–63.

Digital Library

[30]

Jason Luu, Jeffrey Goeders, Michael Wainberg, Andrew Somerville, Thien Yu, Konstantin Nasartschuk, Miad Nasr, et al. 2014. VTR 7.0: Next generation architecture and CAD system for FPGAs. ACM Transactions on Reconfigurable Technology and Systems 7, 2 (2014), 1–30.

Digital Library

[31]

Kejie Ma, Lingli Wang, Xuegong Zhou, Sheldon X.-D. Tan, and Jiarong Tong. 2010. General switch box modeling and optimization for FPGA routing architectures. In Proceedings of the 2010 International Conference on Field-Programmable Technology. IEEE, Los Alamitos, CA, 320–323.

[32]

Alexander Marquardt, Vaughn Betz, and Jonathan Rose. 2000. Timing-driven placement for FPGAs. In Proceedings of the 2000 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 203–213.

Digital Library

[33]

M. Imran Masud and Steven J. E. Wilton. 1999. A new switch block for segmented FPGAs. In Proceedings of the International Workshop on Field-Programmable Logic and Applications. 274–281.

[34]

Larry McMurchie and Carl Ebeling. 2008. Pathfinder: A negotiation-based performance-driven router for FPGAs. In Reconfigurable Computing. Elsevier, 365–381.

[35]

Petar Borisov Minev and Valentina Stoianova Kukenska. 2009. The Virtex-5 routing and logic architecture. Annual Journal of Electronics 3 (2009), 107–110.

[36]

Kevin E. Murray, Oleg Petelin, Sheng Zhong, Jia Min Wang, Mohamed Eldafrawy, Jean-Philippe Legault, Eugene Sha, et al. 2020. VTR 8: High-performance cad and customizable FPGA architecture modelling. ACM Transactions on Reconfigurable Technology and Systems 13, 2 (2020), 1–55.

Digital Library

[37]

Kevin E. Murray, Sheng Zhong, and Vaughn Betz. 2020. AIR: A fast but lazy timing-driven FPGA router. In Proceedings of the 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC’20). IEEE, Los Alamitos, CA, 338–344.

Digital Library

[38]

Omesh Mutukuda, Andy Ye, and Gul Khan. 2010. The effect of multi-bit based connections on the area efficiency of FPGAs utilizing unidirectional routing resources. In Proceedings of the 2010 International Conference on Field-Programmable Technology. IEEE, Los Alamitos, CA, 216–223.

[39]

Stefan Nikolić, Grace Zgheib, and Paolo Ienne. 2020. Straight to the point: Intra-and intercluster LUT connections to mitigate the delay of programmable routing. In Proceedings of the 2020 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 150–160.

Digital Library

[40]

Oleg Petelin and Vaughn Betz. 2016. The speed of diversity: Exploring complex FPGA routing topologies for the global metal layer. In Proceedings of the 2016 26th International Conference on Field-Programmable Logic and Applications (FPL’16). 1–10.

[41]

Morten B. Petersen, Stefan Nikolić, and Mirjana Stojilović. 2021. NetCracker: A peek into the routing architecture of Xilinx 7-Series FPGAs. In Proceedings of the 2021 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 11–22.

Digital Library

[42]

A. Roopchansingh and J. Rose. 2002. Nearest neighbour interconnect architecture in deep submicron FPGAs. In Proceedings of the IEEE 2002 Custom Integrated Circuits Conference (Cat. No. 02CH37285). 59–62.

[43]

Kaichuang Shi, Hao Zhou, Xuegong Zhou, and Lingli Wang. 2020. GIB: A novel unidirectional interconnection architecture for FPGA. In Proceedings of the 2020 International Conference on Field-Programmable Technology (ICFPT’20). 174–181.

[44]

Satish Sivaswamy, Gang Wang, Cristinel Ababei, Kia Bazargan, Ryan Kastner, and Eli Bozorgzadeh. 2005. HARP: Hard-wired routing pattern FPGAs. In Proceedings of the 2005 ACM/SIGDA 13th International Symposium on Field-Programmable Gate Arrays. 21–29.

Digital Library

[45]

Xibo Sun, Hao Zhou, and Lingli Wang. 2019. Bent routing pattern for FPGA. In Proceedings of the 2019 29th International Conference on Field-Programmable Logic and Applications (FPL’19). 9–16.

[46]

Xifan Tang, Edouard Giacomin, Aurélien Alacchi, and Pierre-Emmanuel Gaillardon. 2019. A study on switch block patterns for tileable FPGA routing architectures. In Proceedings of the 2019 International Conference on Field-Programmable Technology (ICFPT’19). IEEE, Los Alamitos, CA, 247–250.

[47]

Jeffrey Tyhach, Mike Hutton, Sean Atsatt, Arifur Rahman, Brad Vest, David Lewis, Martin Langhammer, et al. 2015. Arria™ 10 device architecture. In Proceedings of the 2015 IEEE Custom Integrated Circuits Conference (CICC’15). IEEE, Los Alamitos, CA, 1–8.

[48]

G. Wang, S. Sivaswamy, C. Ababei, K. Bazargan, R. Kastner, and E. Bozorgzadeh. 2006. Statistical analysis and design of HARP FPGAs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 10 (2006), 2088–2102.

Digital Library

[49]

Steven J. E. Wilton. 1997. Architectures and Algorithms for Field-Programmable Gate Arrays with Embedded Memory. Ph.D. Thesis, Department of Electrical and Computer Engineering, University of Toronto.

[50]

Sadegh Yazdanshenas and Vaughn Betz. 2019. COFFE 2: Automatic modelling and optimization of complex and heterogeneous FPGA architectures. ACM Transactions on Reconfigurable Technology and Systems 12, 1 (2019), 1–27.

Digital Library

[51]

Catherine L. Zhou, Ray C. C. Cheung, and Yu-Liang Wu. 2004. What if merging connection and switch boxes—An experimental revisit on FPGA architectures. In Proceedings of the 2004 International Conference on Communications, Circuits, and Systems (IEEE Cat. No. 04EX914), Vol. 2. IEEE, Los Alamitos, CA, 1295–1299.

Cited By

Chen SCai CZheng SLi JZhu GLi JYan YDai YYin WWang L(2024)HierCGRA: A Novel Framework for Large-scale CGRA with Hierarchical Modeling and Automated Design Space ExplorationACM Transactions on Reconfigurable Technology and Systems10.1145/365617617:2(1-31)Online publication date: 10-May-2024
https://dl.acm.org/doi/10.1145/3656176
Nikolić SIenne P(2024)Exploring FPGA Switch-Blocks without Explicitly Listing Connectivity PatternsACM Transactions on Reconfigurable Technology and Systems10.1145/359741717:1(1-39)Online publication date: 12-Feb-2024
https://dl.acm.org/doi/10.1145/3597417
Chen SDai YZhang JKuang HGao XLuk WYin WWang L(2024)CDE: A Novel CGRA Development Environment with Fast Design Space Exploration Framework2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10618029(772-772)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10618029
Show More Cited By

Index Terms

An Optimized GIB Routing Architecture with Bent Wires for FPGA
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
  2. Integrated circuits
    1. Reconfigurable logic and FPGAs
      1. Programmable interconnect

Recommendations

Exploring FPGA routing architecture stochastically
Special section on the ACM IEEE international conference on formal methods and models for codesign (MEMOCODE) 2009

This paper proposes a systematic strategy to efficiently explore the design space of field-programmable gate array (FPGA) routing architectures. The key idea is to use stochastic methods to quickly locate near-optimal solutions in designing FPGA routing ...
FPGA global routing based on a new congestion metric
ICCD '95: Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors

Unlike traditional ASIC routing, the feasibility of routing in FPGAs is constrained not only by the available space within a routing region, but also by the routing capacity of a switch block. Recent work has established the switch-block capacity as a ...
Improvement of cluster-based Mesh FPGA architecture using novel hierarchical interconnect topology and long routing wires

This paper presents an improved interconnect network for Mesh of Clusters (MoC) Field-Programmable Gate Array (FPGA) architecture. Proposed architecture has a depopulated intra-cluster interconnect with flexible Rent's parameter. It presents new multi-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Reconfigurable Technology and Systems

ACM Transactions on Reconfigurable Technology and Systems Volume 16, Issue 1

March 2023

403 pages

ISSN:1936-7406

EISSN:1936-7414

DOI:10.1145/35733111

Editor:
Deming Chen
University of Illinois, Urbana-Champaign Urbana, USA

Issue’s Table of Contents

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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 December 2022

Online AM: 05 March 2022

Accepted: 17 February 2022

Revised: 29 December 2021

Received: 30 August 2021

Published in TRETS Volume 16, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

National Science Foundation of China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
521
Total Downloads

Downloads (Last 12 months)131
Downloads (Last 6 weeks)7

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen SCai CZheng SLi JZhu GLi JYan YDai YYin WWang L(2024)HierCGRA: A Novel Framework for Large-scale CGRA with Hierarchical Modeling and Automated Design Space ExplorationACM Transactions on Reconfigurable Technology and Systems10.1145/365617617:2(1-31)Online publication date: 10-May-2024
https://dl.acm.org/doi/10.1145/3656176
Nikolić SIenne P(2024)Exploring FPGA Switch-Blocks without Explicitly Listing Connectivity PatternsACM Transactions on Reconfigurable Technology and Systems10.1145/359741717:1(1-39)Online publication date: 12-Feb-2024
https://dl.acm.org/doi/10.1145/3597417
Chen SDai YZhang JKuang HGao XLuk WYin WWang L(2024)CDE: A Novel CGRA Development Environment with Fast Design Space Exploration Framework2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10618029(772-772)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10618029
Shi KWang L(2024)An Open-Source Tool to Model and Explore Complex Routing Architecture for FPGA2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617494(734-739)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617494
Chen SMao YDai YGao XLuk WYin WWang L(2024)FCE: A Fast CGRA Architecture Exploration Framework2024 IEEE 17th International Conference on Solid-State & Integrated Circuit Technology (ICSICT)10.1109/ICSICT62049.2024.10832017(1-3)Online publication date: 22-Oct-2024
https://doi.org/10.1109/ICSICT62049.2024.10832017
Siddiqi USait S(2024)A Deterministic Concurrent-Routing Algorithm to Improve Wire Selection in FPGA Routing2024 9th International Conference on Integrated Circuits, Design, and Verification (ICDV)10.1109/ICDV61346.2024.10616485(160-165)Online publication date: 6-Jun-2024
https://doi.org/10.1109/ICDV61346.2024.10616485
Zhu KZhou HLuk WTao JWang L(2023)Iterative and Verifiable Retiming for FPGA Performance Optimization2023 International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA59274.2023.10218458(269-273)Online publication date: 8-May-2023
https://doi.org/10.1109/ISEDA59274.2023.10218458
Siddiqi USait S(2023)On improving the critical path delay of PathFinder at smaller channel widths2023 22nd International Symposium on Communications and Information Technologies (ISCIT)10.1109/ISCIT57293.2023.10376068(127-132)Online publication date: 16-Oct-2023
https://doi.org/10.1109/ISCIT57293.2023.10376068
Shi KZhou HWang L(2023)Explore the Feedback Interconnects in Intra-Cluster Routing for FPGAs2023 International Conference on Field Programmable Technology (ICFPT)10.1109/ICFPT59805.2023.00034(250-253)Online publication date: 12-Dec-2023
https://doi.org/10.1109/ICFPT59805.2023.00034
Shi KZhou HWang L(2023)VIB: A Versatile Interconnection Block for FPGA Routing Architecture2023 International Conference on Field Programmable Technology (ICFPT)10.1109/ICFPT59805.2023.00014(79-87)Online publication date: 12-Dec-2023
https://doi.org/10.1109/ICFPT59805.2023.00014
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents