skip to main content
10.5555/996070.1009920acmconferencesArticle/Chapter ViewAbstractPublication PagesiccadConference Proceedingsconference-collections
Article

A Min-Cost Flow Based Detailed Router for FPGAs

Published: 09 November 2003 Publication History

Abstract

Routing for FPGAs has been a very challenging problem dueto the limitation of routing resources. Although the FPGArouting problem has been researched extensively, most algorithms route one net at a time, and it can cause the net-ordering problem.In this paper, we present a detailed routing algorithm forFPGAs based on min-cost flow computations. Using themin-cost flow approach, our algorithm routes all the netsconnected to a common logic module simultaneously. Ateach stage of the network flow computation, we guaranteeoptimal result in terms of routability and delay cost. For further improvement, we adopt an iterative re nement scheme based on the Lagrangian relaxation technique. The Lagrangian relaxation approach transforms the routing problem into a sequence of Lagrangian subproblems. At each iteration of the algorithm, Lagrangian subproblems are solvedby our min-cost flow based routing algorithm. Any violationof congestion constraints is reflected in the value of corresponding Lagrangian multiplier. The Lagrangian multipliers are incorporated into the cost of each routing rosource nodeand guide the router.Because our min-cost flow based algorithm minimizes costfunction while it maximizes the flow, our algorithm findscongestion-free routing solutions with minimum total delay.Comparison with VPR router shows that our router usesless or equal number of routing tracks with smaller criticalpath delay as well as total routing delay.

References

[1]
{1} R. K. Ahuja, A. V. Goldberg, J. B. Orlin, and R. E. Tarjan, "Finding minimum-cost flows by double scaling," Mathematical Programming 53, pp. 243-266, 1992.
[2]
{2} R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
[3]
{3} C. Albrecht, "Provably good global routing by a new approximation algorithm for multicommodity flow," Proceedings of ACM ISPD-00, pp. 19-35, 2000
[4]
{4} M. Alexander, G. Robins, "New performance-driven FPGA routing algorithms," Proc. ACM/IEEE Design Automation Conference, pp. 562-567, 1995.
[5]
{5} M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, 2nd ed. New York: Wiley, 1993.
[6]
{6} S. Brown, M. Khellah, G. Lemieux, "Segmented Routing for Speed-Performance and Routability in Field-Programmable Gate Arrays," in Journal of VLSI Design, 1996.
[7]
{7} R. C. Carden, C. K. Cheng, "A global router using an efficient approximate multicommodity multiterminal flow algorithm," ACM/IEEE DAC-91, pp. 316-321, 1991.
[8]
{8} Yao-Wen Chang, D. F. Wong, Kai Zhu, and C. K. Wong, "On a New Timing-Driven Tree Problem," in Proc. Intl. Conf. on Computer-Aided Design, 1994, pp. 380-385.
[9]
{9} Yao-Wen Chang, D. F. Wong, C. K. Wong, "FPGA Global Routing Based on a New Congestion Metric," in Proc. Intl. Conf. on Circuit Design, 1995, pp. 372-378.
[10]
{10} J. S. Swartz, V. Betz, J. Rose, "A Fast Routability-Driven Router for FPGAs," Proc. ACM/SIGDA International Symposium on Field Programmable Gate Arrays, 1998, pp. 140-149.
[11]
{11} J. Huang, X. L. Hong, C. K. Cheng, and E. S. Kuh, "An efficient timing-driven global routing algorithm," ACM/IEEE DAC-93, pp. 596-600, 1993.
[12]
{12} Y.-S. Lee, C.-H. Wu, "A performance and routability driven router for FPGAs considering path delay," in Proc. Design Automation Conference, 1995, pp. 557-561.
[13]
{13} G. G. F. Lemieux, S. D. Brown, D. Vranesic, "On Two-Step Routing For FPGAs," in Proc. International Symposium on Physical Design, 1997, pp. 60-66.
[14]
{14} L. McMurchie, C. Eberling, "Path Finder: A Negotiation-Based Performance-Driven Router for FPGAs," in Proc. ACM/SIGDA International Symposium on Field Programmable Gate Arrays, 1995, pp. 111-117.
[15]
{15} G. Meixner, U. Lauther, "A new global router based on a flow model and linear assignment," Proc. ICCAD-90, pp. 44-47, 1990.
[16]
{16} V. Betz, J. Rose, "VPR: A New Packing, Placement and Routing Tool for FPGA Research," in Proc. the 7th Annual Workshop on Field Programmable Logic and Applications, 1999, pp. 213-222.
[17]
{17} S. Yang, "Logic Synthesis and Optimization Benchmarks, Version 3.0," Tech. Report, Microelectronics Center of North Carolina, 1991.
[18]
{18} K. Zhu, Y.-W. Chang, D. F. Wong, "Timing-Driven Routing for Symmetrical-Array-Based FPGAs," in Proc. Intl. Conf. on Computer Design, 1998, pp. 628-633.

Cited By

View all
  • (2007)Solving hard instances of FPGA routing with a congestion-optimal restrained-norm path search spaceProceedings of the 2007 international symposium on Physical design10.1145/1231996.1232026(151-158)Online publication date: 18-Mar-2007

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ICCAD '03: Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design
November 2003
899 pages
ISBN:1581137621

Sponsors

Publisher

IEEE Computer Society

United States

Publication History

Published: 09 November 2003

Check for updates

Author Tags

  1. FPGA routing
  2. Lagrangian relaxation
  3. min-cost flow algorithm

Qualifiers

  • Article

Conference

ICCAD03
Sponsor:

Acceptance Rates

ICCAD '03 Paper Acceptance Rate 129 of 490 submissions, 26%;
Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 09 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2007)Solving hard instances of FPGA routing with a congestion-optimal restrained-norm path search spaceProceedings of the 2007 international symposium on Physical design10.1145/1231996.1232026(151-158)Online publication date: 18-Mar-2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media