Efficient obstacle-avoiding rectilinear steiner tree construction

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

研究成果: 書貢獻/報告類型會議論文篇章同行評審

37 引文 斯高帕斯(Scopus)


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 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 (OASG), 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 2-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.

主出版物標題Proceedings of ISPD'07
主出版物子標題2007 International Symposium on Physical Design
出版狀態已出版 - 2007
事件ISPD'07: 2007 International Symposium on Physical Design - Austin, TX, United States
持續時間: 18 3月 200721 3月 2007


名字Proceedings of the International Symposium on Physical Design


???event.eventtypes.event.conference???ISPD'07: 2007 International Symposium on Physical Design
國家/地區United States
城市Austin, TX


深入研究「Efficient obstacle-avoiding rectilinear steiner tree construction」主題。共同形成了獨特的指紋。