Article

Free access

A new global routing algorithm for FPGAs

Authors:

Yao-Wen Chang,

Shashidhar Thakur,

Kai Zhu,

D. F. WongAuthors Info & Claims

ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

Pages 356 - 361

Published: 06 November 1994 Publication History

PDF eReader

Abstract

As in traditional ASIC technologies, FPGA routing usually consists of two steps: global routing and detailed routing. Unlike existing FPGA detailed routers, which can take full advantage of the special structures of the programmable routing resources, FPGA global routing algorithms still greatly resemble their counterparts in the traditional ASIC technologies. In particular, the routing congestion information of a switch block essentially is still measured by the numbers of available rows and columns in the switch block. Since the internal architecture of a switch block decides what can route through the block, the traditional measure of routing capacity is no longer accurate. In this paper, we present an accurate measure of switch block routing capacity. Our new measure considers the exact positions of the switches inside a switch block. Experiments with a global router based on these ideas show an average improvement of 38% in the channel width required to route some benchmark circuits using a popular switch block, compared with an algorithm based on the traditional methods for congestion control.

References

[1]

N. Bhat and D. Hill, "Routable Technology Mapping for LUT FPGA's," Proc. Intl. Conf. Computer-Aided Design, pp. 95-98, 1992.

Digital Library

Google Scholar

[2]

S. Brown, J. Ross, and Z.G. Vranesic, "A Detailed Router for Field-Programmable Gate Arrays," IEEE Trans. Computer-Aided Design, vol. 11, pp. 620-627, 1992.

Digital Library

Google Scholar

[3]

W. Carter et al., "A User Programmable Reconfigurable Gate Array," Proc. 1986 Custom Integrated Circuits Conference, May 1986, pp. 233-235, 1986.

Google Scholar

[4]

E. Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik, 1:269- 271, 1959.

Digital Library

Google Scholar

[5]

S. Thakur, D.F. Wong, and S. Muthukrishnan, "Algorithms for FPGA Switch Module Routing," Proc. EuroDAC, to appear, 1994.

Digital Library

Google Scholar

[6]

S. Trimberger, ed., Field-Programmable Gate Atray Technology, Kluwer Academic Publishers, 1994.

Digital Library

Google Scholar

[7]

S. Trimberger and M. Chene, "Placement-Based Partitioning for Lookup-Table-Based FPGA's," Proc. Intl. Conf. Computer-Aided Design, pp. 91- 94, 1992.

Digital Library

Google Scholar

[8]

Xilinx Inc., The Programmable Logic Data Book, 1994.

Google Scholar

[9]

K. Zhu, D.F. Wong, and Y.-W. Chang, "Switch Module Design with Application to Two- Dimensional Segmentation Design," Proc. Intl. Conf. Computer-Aided Design, pp. 481-486, 1993.

Digital Library

Google Scholar

Cited By

View all

Chen SChang YParameswaran S(2017)FPGA placement and routingProceedings of the 36th International Conference on Computer-Aided Design10.5555/3199700.3199826(914-921)Online publication date: 13-Nov-2017
https://dl.acm.org/doi/10.5555/3199700.3199826
Kim YPark SChang NXie QWang YPedram MGroeneveld PSciuto DHassoun S(2012)Networked architecture for hybrid electrical energy storage systemsProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228453(522-528)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228453
Rautela DKatti R(2005)Design and Implementation of FPGA Router for Efficient Utilization of Heterogeneous Routing ResourcesProceedings of the IEEE Computer Society Annual Symposium on VLSI: New Frontiers in VLSI Design10.1109/ISVLSI.2005.26(232-237)Online publication date: 11-May-2005
https://dl.acm.org/doi/10.1109/ISVLSI.2005.26
Show More Cited By

Index Terms

A new global routing algorithm for FPGAs
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

The Impact of Global Routing on the Performance of NoCs in FPGAs
RECONFIG '11: Proceedings of the 2011 International Conference on Reconfigurable Computing and FPGAs

With the over-provisioned routing resource on FPGA, the topology choice for NoC implementation on FPGA is more flexible than on ASIC. However, it is well understood that the global wire routing impacts the performance of NoC on FPGA because the topology ...
Stable internet routing without global coordination

The Border Gateway Protocol (BGP) allows an autonomous system (AS) to apply diverse local policies for selecting routes and propagating reachability information to other domains. However, BGP permits ASs to have conflicting policies that can lead to ...
Performance driven routing for modern FPGAs invited paper
2016 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)
FPGA routing is a well studied problem. Basic point-to-point routing of nets on FPGA fabrics can be done optimally using well known shortest path algorithms like Dijkstra's and A-star. Practical rip-up and reroute algorithms like PathFinder have been very ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

November 1994

771 pages

ISBN:0897916905

Chairmen:
Jochen A. G. Jess
Eindhoven Univ. of Technology, Eindhoven, The Netherlands
,
Richard Rudell
Synopsys, Inc., Mountain View, CA

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 06 November 1994

Check for updates

Qualifiers

Article

Conference

ICCAD '94

Sponsor:

SIGDA
IEEE-CS

ICCAD '94: International Conference on Computer Aided Design

November 6 - 10, 1994

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
431
Total Downloads

Downloads (Last 12 months)65
Downloads (Last 6 weeks)24

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chen SChang YParameswaran S(2017)FPGA placement and routingProceedings of the 36th International Conference on Computer-Aided Design10.5555/3199700.3199826(914-921)Online publication date: 13-Nov-2017
https://dl.acm.org/doi/10.5555/3199700.3199826
Kim YPark SChang NXie QWang YPedram MGroeneveld PSciuto DHassoun S(2012)Networked architecture for hybrid electrical energy storage systemsProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228453(522-528)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228453
Rautela DKatti R(2005)Design and Implementation of FPGA Router for Efficient Utilization of Heterogeneous Routing ResourcesProceedings of the IEEE Computer Society Annual Symposium on VLSI: New Frontiers in VLSI Design10.1109/ISVLSI.2005.26(232-237)Online publication date: 11-May-2005
https://dl.acm.org/doi/10.1109/ISVLSI.2005.26
Lin JPan SChang YYasuura H(2003)Graph matching-based algorithms for array-based FPGA segmentation design and routingProceedings of the 2003 Asia and South Pacific Design Automation Conference10.1145/1119772.1119959(851-854)Online publication date: 21-Jan-2003
https://dl.acm.org/doi/10.1145/1119772.1119959
Chang YZhu KWong D(2000)Timing-driven routing for symmetrical array-based FPGAsACM Transactions on Design Automation of Electronic Systems10.1145/348019.3481015:3(433-450)Online publication date: 1-Jul-2000
https://dl.acm.org/doi/10.1145/348019.348101
Chang YChang YDe Micheli G(2000)An architecture-driven metric for simultaneous placement and global routing for FPGAsProceedings of the 37th Annual Design Automation Conference10.1145/337292.337582(567-572)Online publication date: 1-Jun-2000
https://dl.acm.org/doi/10.1145/337292.337582
Chen TCengiz ASarrafzadeh MBanerjee PRoy K(2000)Measuring routing congestion for multi-layer global routingProceedings of the 10th Great Lakes symposium on VLSI10.1145/330855.330968(59-62)Online publication date: 2-Mar-2000
https://dl.acm.org/doi/10.1145/330855.330968
Wood RRutenbar REbeling C(1997)FPGA routing and routability estimation via Boolean satisfiabilityProceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays10.1145/258305.258322(119-125)Online publication date: 9-Feb-1997
https://dl.acm.org/doi/10.1145/258305.258322
Nag SRutenbar RRudell R(1995)Performance-driven simultaneous place and route for island-style FPGAsProceedings of the 1995 IEEE/ACM international conference on Computer-aided design10.5555/224841.225060(332-338)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/224841.225060
Alexander MRobins GPreas B(1995)New performance-driven FPGA routing algorithmsProceedings of the 32nd annual ACM/IEEE Design Automation Conference10.1145/217474.217589(562-567)Online publication date: 1-Jan-1995
https://dl.acm.org/doi/10.1145/217474.217589

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

The Impact of Global Routing on the Performance of NoCs in FPGAs

Stable internet routing without global coordination

Performance driven routing for modern FPGAs invited paper