https://scholars.lib.ntu.edu.tw/handle/123456789/341026
標題: | Multilayer obstacle-avoiding rectilinear steiner tree construction based on spanning graphs | 作者: | Lin, C.-W. Huang, S.-L. Hsu, K.-C. Lee, M.-X. Chang, Y.-W. YAO-WEN CHANG |
關鍵字: | Layout; Physical design; Routing; Steiner tree | 公開日期: | 2008 | 卷: | 27 | 期: | 11 | 起(迄)頁: | 2007-2016 | 來源出版物: | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems | 摘要: | Given a set of pins and a set of obstacles on routing layers, a multilayer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) connects these pins by rectilinear edges within layers and vias between layers and avoids running through any obstacle to construct a Steiner tree with a minimal total cost. The ML-OARSMT problem is very important for many very large scale integration designs with pins being located in multiple routing layers that contain numerous routing obstacles incurred from IP blocks, power networks, prerouted nets, etc. As a fundamental problem with extensive practical applications to routing and wirelength/congestion/timing estimations in early design stages, it is desired to develop an effective algorithm for the ML-OARSMT problem to facilitate the design flow. However, there is no existing work on this ML-OARSMT problem. In this paper, we first formulate the ML-OARSMT problem with rectangular obstacles and then identify key different properties of this problem from its single-layer counterpart. Based on the multilayer obstacle-avoiding spanning graph, we present the first algorithm to solve the ML-OARSMT problem. Our algorithm can guarantee an optimal solution for any two-pin net and many multiple-pin nets. Experiments show that our algorithm results in 33% smaller total costs on average than a construction-by-correction heuristic which is widely used for Steiner-tree construction in the recent literature. © 2008 IEEE. |
URI: | http://www.scopus.com/inward/record.url?eid=2-s2.0-54949086335&partnerID=MN8TOARS http://scholars.lib.ntu.edu.tw/handle/123456789/341026 |
DOI: | 10.1109/TCAD.2008.2006095 | SDG/關鍵字: | Boolean functions; Computer networks; Design; Graph theory; Heuristic algorithms; Marine biology; Multilayers; Network protocols; Routing algorithms; Sensor networks; Set theory; Design flows; Early design stages; Effective algorithms; Fundamental problems; Heuristic; Ip blocks; Layout; Multiple routing; Optimal solutions; Physical design; Power networks; Practical; Rectangular obstacles; Rectilinear Steiner trees; Routing; Routing layers; Single-layer; Steiner minimal trees; Steiner tree; Steiner trees; Total costs; Tree constructions; Very large scale integration designs; Trees (mathematics) |
顯示於: | 電子工程學研究所 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。