Timing-driven routing for FPGAs based on Lagrangian relaxation

Seokjin Lee, D. F. Wong

Research output: Contribution to conferencePaperpeer-review


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 (US)
Number of pages6
StatePublished - 2002
Externally publishedYes
EventISPD-2002: International Symposium on Physical Design - Del Mar, CA, United States
Duration: Apr 7 2002Apr 10 2002


OtherISPD-2002: International Symposium on Physical Design
Country/TerritoryUnited States
CityDel Mar, CA


  • FPGA
  • Lagrangian relaxation
  • Timing-driven routing

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


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

Cite this