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

research-article

A Robust FPGA Router with Concurrent Intra-CLB Rerouting

Authors:

Yibo LinAuthors Info & Claims

ASPDAC '23: Proceedings of the 28th Asia and South Pacific Design Automation Conference

Pages 529 - 534

https://doi.org/10.1145/3566097.3567898

Published: 31 January 2023 Publication History

Abstract

Routing is the most time-consuming step in the FPGA design flow with increasingly complicated FPGA architectures and design scales. The growing complexity of connections between logic pins inside CLBs of FPGAs challenges the efficiency and quality of FPGA routers. Existing negotiation-based rip-up and reroute schemes will result in a large number of iterations when generating paths inside CLBs. In this work, we propose a robust routing framework for FPGAs with complex connections between logic elements and switch boxes. We propose a concurrent intra-CLB rerouting algorithm that can effectively resolve routing congestion inside a CLB tile. Experimental results on modified ISPD 2016 benchmarks demonstrate that our framework can achieve 100% routability in less wirelength and runtime, while the state-of-the-art VTR 8.0 routing algorithm fails at 4 of 12 benchmarks.

References

[1]

Ultrascale architecture clocking resources. [Online]. Available: https://www.xilinx.com/support/documentation/user_guides/ug572-ultrascale-clocking.pdf

[2]

Ultrascale architecture clb slices. [Online]. Available: https://www.xilinx.com/support/documentation/user_guides/ug574-ultrascale-clb.pdf

[3]

K. E. Murray, S. Whitty, S. Liu, J. Luu, and V. Betz, "Timing-driven titan: Enabling large benchmarks and exploring the gap between academic and commercial cad," ACM Trans. Reconfigurable Technol. Syst., vol. 8, no. 2, Mar. 2015.

Digital Library

[4]

L. McMurchie and C. Ebeling, "Pathfinder: A negotiation-based performance-driven router for fpgas," in Third International ACM Symposium on Field-Programmable Gate Arrays, 1995, pp. 111--117.

[5]

G. G. Lemieux and S. D. Brown, "detailed routing algorithm for allocating wire segments in field-programmable gate arrays," in Proc. Physical Design Workshop, 1993, pp. 215--226.

[6]

K. E. Murray, S. Zhong, and V. Betz, "Air: A fast but lazy timing-driven fpga router," in 2020 25th Asia and South Pacific Design Automation Conference (ASPDAC), 2020, pp. 338--344.

[7]

D. Wang, Z. Duan, C. Tian, B. Huang, and N. Zhang, "A runtime optimization approach for fpga routing," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 37, no. 8, pp. 1706--1710, 2018.

[8]

D. Vercruyce, E. Vansteenkiste, and D. Stroobandt, "Croute: A fast high-quality timing-driven connection-based fpga router," in 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2019, pp. 53--60.

[9]

M. Shen and N. Xiao, "Fine-grained parallel routing for fpgas with selective expansion," in 2018 IEEE 36th International Conference on Computer Design (ICCD), 2018, pp. 577--586.

[10]

M. Shen, "Load balance-aware multi-core parallel routing for large-scale fpgas," in 2018 IEEE 36th International Conference on Computer Design (ICCD), 2018, pp. 595--602.

[11]

C. H. Hoo and A. Kumar, "Paradro: A parallel deterministic router based on spatial partitioning and scheduling," in Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, ser. FPGA '18. New York, NY, USA: Association for Computing Machinery, 2018, p. 67--76.

Digital Library

[12]

Y. Zhou, D. Vercruyce, and D. Stroobandt, "Accelerating fpga routing through algorithmic enhancements and connection-aware parallelization," ACM transactions on reconfigurable technology and systems, vol. 13, no. 4, pp. 1--26, 2020.

[13]

M. Shen, G. Luo, and N. Xiao, "Combining static and dynamic load balance in parallel routing for fpgas," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 40, no. 9, pp. 1850--1863, 2021.

[14]

K. E. Murray, O. Petelin, S. Zhong, J. M. Wang, M. ElDafrawy, J.-P. Legault, E. Sha, A. G. Graham, J. Wu, M. J. P. Walker, H. Zeng, P. Patros, J. Luu, K. B. Kent, and V. Betz, "Vtr 8: High performance cad and customizable fpga architecture modelling," ACM Trans. Reconfigurable Technol. Syst., 2020.

Digital Library

[15]

Y. Guo, J. Wang, J. Zhang, and G. Luo, "Formulating data-arrival synchronizers in integer linear programming for cgra mapping," in 2021 58th ACM/IEEE Design Automation Conference (DAC), 2021, pp. 943--948.

[16]

Gurobi Optimization Inc., "Gurobi optimizer reference manual," http://www.gurobi.com, 2022.

[17]

T.-W. Huang, D.-L. Lin, C.-X. Lin, and Y. Lin, "Taskflow: A lightweight parallel and heterogeneous task graph computing system," IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 6, pp. 1303--1320, 2022.

Digital Library

[18]

S. Yang, A. Gayasen, C. Mulpuri, S. Reddy, and R. Aggarwal, "Routability-driven FPGA placement contest," in ACM International Symposium on Physical Design (ISPD), 2016, pp. 139--143.

[19]

Y. Meng, W. Li, Y. Lin, and D. Z. Pan, "elfplace: Electrostatics-based placement for large-scale heterogeneous fpgas," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 2021.

Cited By

Mai JWang JDi ZLin Y(2023)Multielectrostatic FPGA Placement Considering SLICEL–SLICEM Heterogeneity, Clock Feasibility, and Timing OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.331310143:2(641-653)Online publication date: 7-Sep-2023
https://dl.acm.org/doi/10.1109/TCAD.2023.3313101
Goswami PBhatia D(2023)Application of Machine Learning in FPGA EDA Tool DevelopmentIEEE Access10.1109/ACCESS.2023.332235811(109564-109580)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3322358

Index Terms

A Robust FPGA Router with Concurrent Intra-CLB Rerouting
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

Index terms have been assigned to the content through auto-classification.

Recommendations

Acceleration of an FPGA router
FCCM '97: Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines

The authors describe their experience and progress in accelerating an FPGA router. Placement and routing is undoubtedly the most time-consuming process in automatic chip design or configuring programmable logic devices as reconfigurable computing ...
A new global router for modern designs
ASP-DAC '08: Proceedings of the 2008 Asia and South Pacific Design Automation Conference

In this paper, we present a new global router, NTHU-Route, for modern designs. NTHU-Route is based on iterative rip-ups and reroutes, and several techniques are proposed to enhance our global router. These techniques include (1) a history based cost ...
Enhancements in UltraScale CLB Architecture
FPGA '15: Proceedings of the 2015 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

Each generation of FPGA architecture benefits from optimizations around its technology node and target usage. In this paper, we discuss some of the changes made to the CLB for Xilinx's 20nm UltraScale product family. We motivate those changes and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPDAC '23: Proceedings of the 28th Asia and South Pacific Design Automation Conference

January 2023

807 pages

ISBN:9781450397834

DOI:10.1145/3566097

General Chair:
Atsushi Takahashi
Tokyo Institute of Technology

Copyright © 2023 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

In-Cooperation

IPSJ
IEEE CAS
IEEE CEDA
IEICE

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 January 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

ASPDAC '23

Sponsor:

SIGDA

ASPDAC '23: 28th Asia and South Pacific Design Automation Conference

January 16 - 19, 2023

Tokyo, Japan

Acceptance Rates

ASPDAC '23 Paper Acceptance Rate 102 of 328 submissions, 31%;

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Upcoming Conference

ASPDAC '25

Sponsor:
sigda

30th Asia and South Pacific Design Automation Conference

January 20 - 23, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
198
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)9

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mai JWang JDi ZLin Y(2023)Multielectrostatic FPGA Placement Considering SLICEL–SLICEM Heterogeneity, Clock Feasibility, and Timing OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.331310143:2(641-653)Online publication date: 7-Sep-2023
https://dl.acm.org/doi/10.1109/TCAD.2023.3313101
Goswami PBhatia D(2023)Application of Machine Learning in FPGA EDA Tool DevelopmentIEEE Access10.1109/ACCESS.2023.332235811(109564-109580)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3322358

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