Efficient multi-layer obstacle-avoiding preferred direction rectilinear Steiner tree construction

Jia Ru Chuang, Jai Ming Lin

研究成果: Conference contribution

5 引文 斯高帕斯(Scopus)

摘要

Constructing rectilinear Steiner trees for signal nets is a very important procedure for placement and routing because we can use it to find topologies of nets and measure the design quality. However, in modern VLSI designs, pins are located in multiple routing layers, each routing layer has its own preferred direction, and there exist numerous routing obstacles incurred from IP blocks, power networks, pre-routed nets, etc, which make us need to consider multilayer obstacle-avoiding preferred direction rectilinear Steiner minimal tree (ML-OAPDRSMT) problem. This significantly increases the complexity of the problem, and an efficient and effective algorithm to deal with the problem is desired. In this paper, we propose a very simple and effective approach to deal with ML-OAPDRSMT problem. Unlike previous works usually build a spanning graph and find a spanning tree to deal with this problem, which takes a lot of time, we first determine a connection ordering for all pins, and then iteratively connect every two neighboring pins by a greedy heuristic algorithm. The experimental results show that our method has average 5.78% improvement over [7] and at least five times speed up comparing with their approach.

原文English
主出版物標題2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
頁面527-532
頁數6
DOIs
出版狀態Published - 2011 3月 28
事件2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011 - Yokohama, Japan
持續時間: 2011 1月 252011 1月 28

出版系列

名字Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Other

Other2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
國家/地區Japan
城市Yokohama
期間11-01-2511-01-28

All Science Journal Classification (ASJC) codes

  • 電腦科學應用
  • 電腦繪圖與電腦輔助設計
  • 電氣與電子工程

指紋

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

引用此