Timing-driven routing for FPGAs based on Lagrangian relaxation

Seokjin Lee, D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

7 Citations (Scopus)


As interconnection delay plays an important role in determining circuit performance in FPGAs, timing-driven FPGA routing has received much attention recently. In this paper, we present a new timing-driven routing algorithm for FPGAs. The algorithm finds a routing with minimum critical path delay for a given placed circuit using the Lagrangian relaxation technique. Lagrangian multipliers used to relax timing constraints are updated by subgradient method over iterations. Incorporated into the cost function, these multipliers guide the router to construct routing tree for each net. During routing, the exclusivity constraints on each routing resources are also taken care of to route circuits successfully. Experimental results on benchmark circuits show that our approach outperforms the state-of-the-art VPR router.

Original languageEnglish
Title of host publicationISPD '02
Subtitle of host publicationProceedings of the 2002 international symposium on Physical design
Place of PublicationUnited States
PublisherAssociation for Computing Machinery (ACM)
Number of pages6
ISBN (Print)9781581134605
Publication statusPublished - Apr 2002
Event11th International Symposium on Physical Design, ISPD 2002 - Hilton Hotel San Diego, Del Mar, United States
Duration: 7 Apr 200210 Apr 2002
https://ispd.cc/ispd2024/slides/ispd2002.html (Conference website)
https://dl.acm.org/doi/proceedings/10.1145/505388 (Conference proceedings)

Publication series

NameProceedings of The ACM International Symposium on Physical Design, ISPD


Symposium11th International Symposium on Physical Design, ISPD 2002
Country/TerritoryUnited States
CityDel Mar
Internet address

Scopus Subject Areas

  • Electrical and Electronic Engineering

User-Defined Keywords

  • FPGA
  • Lagrangian relaxation
  • Timing-driven routing


Dive into the research topics of 'Timing-driven routing for FPGAs based on Lagrangian relaxation'. Together they form a unique fingerprint.

Cite this