A Min-Cost Flow Based Detailed Router for FPGAs

Seokjin Lee, Yongseok Cheon, Martin D.F. Wong

Research output: Contribution to journalConference article

Abstract

Routing for FPGAs has been a very challenging problem due to the limitation of routing resources. Although the FPGA routing 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 for FPGAs based on min-cost flow computations. Using the min-cost flow approach, our algorithm routes all the nets connected to a common logic module simultaneously. At each stage of the network flow computation, we guarantee optimal result in terms of routability and delay cost. For further improvement, we adopt an iterative refinement 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 solved by our min-cost flow based routing algorithm. Any violation of congestion constraints is reflected in the value of corresponding Lagrangian multiplier. The Lagrangian multipliers are incorporated into the cost of each routing rosource node and guide the router. Because our min-cost flow based algorithm minimizes cost function while it maximizes the flow, our algorithm finds congestion-free routing solutions with minimum total delay. Comparison with VPR router shows that our router uses less or equal number of routing tracks with smaller critical path delay as well as total routing delay.

Original languageEnglish (US)
Pages (from-to)388-393
Number of pages6
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
StatePublished - Dec 26 2003
EventIEEE/ACM International Conference on Computer Aided Design ICCAD 2003: IEEE/ACM Digest of Technical Papers - San Jose, CA, United States
Duration: Nov 9 2003Nov 13 2003

Fingerprint

Routers
Field programmable gate arrays (FPGA)
Costs
Routing algorithms
Cost functions

Keywords

  • FPGA routing
  • Lagrangian relaxation
  • Min-cost flow algorithm

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Cite this

A Min-Cost Flow Based Detailed Router for FPGAs. / Lee, Seokjin; Cheon, Yongseok; Wong, Martin D.F.

In: IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, 26.12.2003, p. 388-393.

Research output: Contribution to journalConference article

@article{df5d74df40ea4d8e8d00b1def1ed0402,
title = "A Min-Cost Flow Based Detailed Router for FPGAs",
abstract = "Routing for FPGAs has been a very challenging problem due to the limitation of routing resources. Although the FPGA routing 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 for FPGAs based on min-cost flow computations. Using the min-cost flow approach, our algorithm routes all the nets connected to a common logic module simultaneously. At each stage of the network flow computation, we guarantee optimal result in terms of routability and delay cost. For further improvement, we adopt an iterative refinement 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 solved by our min-cost flow based routing algorithm. Any violation of congestion constraints is reflected in the value of corresponding Lagrangian multiplier. The Lagrangian multipliers are incorporated into the cost of each routing rosource node and guide the router. Because our min-cost flow based algorithm minimizes cost function while it maximizes the flow, our algorithm finds congestion-free routing solutions with minimum total delay. Comparison with VPR router shows that our router uses less or equal number of routing tracks with smaller critical path delay as well as total routing delay.",
keywords = "FPGA routing, Lagrangian relaxation, Min-cost flow algorithm",
author = "Seokjin Lee and Yongseok Cheon and Wong, {Martin D.F.}",
year = "2003",
month = "12",
day = "26",
language = "English (US)",
pages = "388--393",
journal = "IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers",
issn = "1092-3152",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - A Min-Cost Flow Based Detailed Router for FPGAs

AU - Lee, Seokjin

AU - Cheon, Yongseok

AU - Wong, Martin D.F.

PY - 2003/12/26

Y1 - 2003/12/26

N2 - Routing for FPGAs has been a very challenging problem due to the limitation of routing resources. Although the FPGA routing 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 for FPGAs based on min-cost flow computations. Using the min-cost flow approach, our algorithm routes all the nets connected to a common logic module simultaneously. At each stage of the network flow computation, we guarantee optimal result in terms of routability and delay cost. For further improvement, we adopt an iterative refinement 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 solved by our min-cost flow based routing algorithm. Any violation of congestion constraints is reflected in the value of corresponding Lagrangian multiplier. The Lagrangian multipliers are incorporated into the cost of each routing rosource node and guide the router. Because our min-cost flow based algorithm minimizes cost function while it maximizes the flow, our algorithm finds congestion-free routing solutions with minimum total delay. Comparison with VPR router shows that our router uses less or equal number of routing tracks with smaller critical path delay as well as total routing delay.

AB - Routing for FPGAs has been a very challenging problem due to the limitation of routing resources. Although the FPGA routing 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 for FPGAs based on min-cost flow computations. Using the min-cost flow approach, our algorithm routes all the nets connected to a common logic module simultaneously. At each stage of the network flow computation, we guarantee optimal result in terms of routability and delay cost. For further improvement, we adopt an iterative refinement 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 solved by our min-cost flow based routing algorithm. Any violation of congestion constraints is reflected in the value of corresponding Lagrangian multiplier. The Lagrangian multipliers are incorporated into the cost of each routing rosource node and guide the router. Because our min-cost flow based algorithm minimizes cost function while it maximizes the flow, our algorithm finds congestion-free routing solutions with minimum total delay. Comparison with VPR router shows that our router uses less or equal number of routing tracks with smaller critical path delay as well as total routing delay.

KW - FPGA routing

KW - Lagrangian relaxation

KW - Min-cost flow algorithm

UR - http://www.scopus.com/inward/record.url?scp=0346778739&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346778739&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0346778739

SP - 388

EP - 393

JO - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers

JF - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers

SN - 1092-3152

ER -