Timing-driven routing for FPGAs based on Lagrangian relaxation

Seokjin Lee, Martin D.F. Wong

Research output: Contribution to journalArticlepeer-review


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 (US)
Pages (from-to)506-511
Number of pages6
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number4
StatePublished - Apr 2003


  • Field programmable gate arrays
  • Lagrangian relaxation
  • Timing-driven routing

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • 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