Obstacle-avoiding rectilinear steiner tree construction based on spanning graphs

Chung Wei Lin, Szu Yu Chen, Chi Feng Li, Yao Wen Chang, Chia Lin Yang

Research output: Contribution to journalArticlepeer-review

48 Scopus citations

Abstract

Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins, possibly through some additional points (called the Steiner points), and avoids running through any obstacle to construct a tree with a minimal total wirelength. The OARSMT problem becomes more important than ever for modern nanometer IC designs which need to consider numerous routing obstacles incurred from power networks, prerouted nets, IP blocks, feature patterns for manufacturability improvement, antenna jumpers for reliability enhancement, etc. Consequently, the OARSMT problem has received dramatically increasing attention recently. Nevertheless, considering obstacles significantly increases the problem complexity, and thus, most previous works suffer from either poor quality or expensive running time. Based on the obstacle-avoiding spanning graph, this paper presents an efficient algorithm with some theoretical optimality guarantees for the OARSMT construction. Unlike previous heuristics, our algorithm guarantees to find an optimal OARSMT for any two-pin net and many higher pin nets. Extensive experiments show that our algorithm results in significantly shorter wirelengths than all state-of-the-art works.

Original languageEnglish
Article number4475253
Pages (from-to)643-653
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume27
Issue number4
DOIs
StatePublished - Apr 2008

Keywords

  • Physical design
  • Routing
  • Spanning tree
  • Steiner tree

Fingerprint

Dive into the research topics of 'Obstacle-avoiding rectilinear steiner tree construction based on spanning graphs'. Together they form a unique fingerprint.

Cite this