Abstract: Routing is a phase in the physical design of Electronic Circuits. The main aim of routing in VLSI design is to interconnect the cells that have been assigned positions as a solution of the placement problem. The problem of finding Rectilinear SteinerMinimal Tree (RSMT) is one of the fundamental problems in the field of Electronic Design Automation. The obstacle avoiding rectilinear Steiner minimal tree problem becomes more important for modern nanometer IC designs which considers numerous routing obstacles incurred from power networks, pre-routed nets, IP blocks, feature patterns for manufacturability improvement, antenna jumpers for reliability enhancement etc. But at present the Multilayer Obstacle Avoiding Rectilinear SteinerMinimal Tree (ML-OARSMT) has gained much importance for modern nanometer IC designs which considers multilayers for routing, obstacles incurred from power networks etc., and preferred direction for routing layer. A ML-OARSMT connects a set of pins and set of obstacles incurred from IP blocks, power networks, pre-routed nets etc., on routing layers by rectilinear edges within layers and vias between layers such that no tree or via intersect an obstacle and the total cost of the tree is minimized. This paper provides a survey of various multilayer obstacles avoiding rectilinear Steiner minimal tree algorithms proposed and thus there is a need for an algorithm to produce better solution quality (reduced wire length) in less running time.
Keywords: Multilayer, obstacle Avoiding, Rectilinear Steiner Tree
[1]. Sherwani Naveed A. Algorithms forVLSI Physical Design Automation. Kluwer Academic Publishers, 1998.
[2]. Garey, Michael R., andDavid S. Johnson, "Therectilinear Steiner tree problem is NP-complete, SIAM Journal ofApplied Mathematics, pp. 826-834, 1977.
[3]. Chung-Wei Lin, Shih-Lun Huang, Kai-Chi Hsu, Meng-Xiang Lee, and Yao-Wen Chang," Multilayer obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs", IEEE Transactions On Computer –Aided Design, Vol.27, No. 11, pp.2007-2016,November2008.
[4]. Chung-Wei Lin, Shih-Lun Huang, Kai-Chi Hsu, Meng-Xiang Lee, and Yao-Wen Chang," Efficient Multi-Layer obstacle-avoiding rectilinear Steiner tree construction", in Proc.ICCAD.pp 380-385,2007.
[5]. Yao-Wen Chang C-W.Lin, S-Y. Chen "Obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs,"IEEE Transactions, Computer-Aided Design,vol.27,no4,pp.643-653,2008.
