Timing-driven routing for FPGAs based on Lagrangian relaxation

Seokjin Lee, Martin D. F. Wong

Research output: Contribution to journalJournal articlepeer-review

23 Citations (Scopus)


As interconnection delay plays an important role in determining circuit performance in field programmable gate arrays (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 minimizes 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 a routing tree for each net. During routing, the congestion constraints on each routing resource are also handled to route circuits successfully. Experimental results on benchmark circuits show that our approach outperforms the state-of-the-art versatile place and route router.

Original languageEnglish
Pages (from-to)506-511
Number of pages6
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number4
Publication statusPublished - Apr 2003

Scopus Subject Areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Field programmable gate arrays
  • 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