A new algorithm for routing tree construction with buffer insertion and wire sizing under obstacle constraints

X. Tang, R. Tian, H. Xiang, D. F. Wong

Research output: Contribution to journalConference articlepeer-review


Buffer insertion and wire sizing are critical in deep submicron VLSI deign. This paper studies the problem of constructing routing trees with simultaneous buffer insertion and wire sizing in the presence of routing and buffer obstacles. No previous algorithms consider all these factors simultaneously. Previous dynamic programming based algorithm is first extended to solve the problem. However, with the size of routing graph increasing and with wire sizing taken into account, the time and space requirement increases enormously. Then a new approach is proposed to formulate the problem as a series of graph problems. The routing tree solution is obtained by finding shortest paths in a series of graphs. In the new approach, wire sizing can be handled almost without any additional time and space requirement. Moreover, the time and space requirement is only polynomial in terms of the size of routing graph. Our algorithm differs from traditional dynamic programming, and is capable of addressing the problem of inverter insertion and sink polarity. Both theoretical and experimental results show that the graph-based algorithm outperforms the DP-based algorithm by a large margin. We also propose a hierarchical approach to construct routing tree for a large number of sinks.

Original languageEnglish (US)
Pages (from-to)49-56
Number of pages8
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
StatePublished - 2001
Externally publishedYes
EventInternational Conference on Computer-Aided Design 2001 - San Jose, CA, United States
Duration: Nov 4 2001Nov 8 2001

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'A new algorithm for routing tree construction with buffer insertion and wire sizing under obstacle constraints'. Together they form a unique fingerprint.

Cite this