Algorithmic study of single-layer bus routing for high-speed boards

Muhammet Mustafa Ozdal*, M. D. F. Wong

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

39 Citations (Scopus)


As the clock frequencies used in industrial applications increase, the timing requirements on routing problems become tighter, and current routing tools cannot successfully handle these constraints anymore. In this paper, the authors focus on the high-performance single-layer bus routing problem, where the objective is to match the lengths of all nets belonging to each bus. An effective approach to solve this problem is to allocate extra routing resources around short nets during routing, and use those resources for length extension afterwards. First, a provably optimal algorithm for routing nets with minimum-area maximum-length constraints is proposed. Then, this algorithm is extended to the case where minimum constraints are given as exact length bounds, and it is also proven that this algorithm is near-optimal. Both algorithms proposed are shown to be scalable for large circuits, since the respective time complexities are O(A) and O(A log A), where A is the area of the intermediate region between chips.

Original languageEnglish
Pages (from-to)490-503
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number3
Early online date21 Feb 2006
Publication statusPublished - Mar 2006

Scopus Subject Areas

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

User-Defined Keywords

  • Algorithms
  • Design automation
  • Physical design
  • Routing


Dive into the research topics of 'Algorithmic study of single-layer bus routing for high-speed boards'. Together they form a unique fingerprint.

Cite this