Title :
Efficient multi-layer obstacle-avoiding preferred direction rectilinear Steiner tree construction
Author :
Chuang, Jia-Ru ; Lin, Jai-Ming
Author_Institution :
Dept. of Electr. Eng., Nat. Cheng Kung Univ., Tainan, Taiwan
Abstract :
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 and at least five times speed up comparing with their approach.
Keywords :
VLSI; collision avoidance; computational complexity; greedy algorithms; integrated circuit design; network routing; trees (mathematics); IP blocks; ML-OAPDRSMT problem; VLSI design; design quality; efficient multilayer obstacle avoidance; greedy heuristic algorithm; multilayer obstacle-avoiding preferred direction rectilinear Steiner minimal tree; multiple routing layer; power networks; preferred direction rectilinear Steiner tree construction; prerouted nets; problem complexity; rectilinear Steiner trees; routing obstacles; signal nets; spanning graph; spanning tree; Complexity theory; Integrated circuit modeling; Joining processes; Pins; Routing; Steiner trees; Wire; Multi-Layer; Obstacle-Avoiding; Preferred Direction; Rectilinear Steiner Tree; Routing;
Conference_Titel :
Design Automation Conference (ASP-DAC), 2011 16th Asia and South Pacific
Conference_Location :
Yokohama
Print_ISBN :
978-1-4244-7515-5
DOI :
10.1109/ASPDAC.2011.5722246