Research On VLSI Obstacle-Avoiding Routing Algorithm Based On Steiner Tree

The SMT(Steiner Minimum Tree)problem is a basic research problem in the physical design of VLSI(Very Large-Scale Integration).Many problems in VLSI routing can be converted to Steiner tree constructing problem.At present,the wiring in the traditional routing is horizontal or vertical,so the RSMT(Rectilinear Steiner Minimum Tree)problem is an important research problem as an extension of the SMT problem.With the development of integrated circuit industry technology,it is necessary to take into account more and more obstacles during the placing and routing stage of the chip,such as IP blocks,power supply networks,pre-routed networks,and some obstacles to ensure manufacturability.These obstacles hinder the construction of some edges when constructing RSMT.Therefore,it is particularly important to study the problem of quickly and efficiently constructing an OARSMT(Obstacle Avoiding Rectilinear Steiner Minimum Tree)in consideration of obstacles.The deterministic algorithm can ensure that the constructed RSMT has the minimum wire-length,but its time complexity is often exponential,which is not suitable for practical engineering applications.The approximate algorithm cannot guarantee the optimality of the solution,but they usually have higher computational efficiency.Therefore,the approximate algorithm is the current research hotspot.At present,there are many efficient RSMT algorithms that do not consider obstacles in academia.This thesis draws on some mainstream methods to study the OARSMT approximation algorithm considering obstacles based on the RSMT algorithm without considering obstacles.For the SL-OARSMT(single-layer OARSMT)problem,the direct legalization scheme is simple and fast,but the quality of the solution is poor.The partition scheme has better solution when there are fewer obstacles.This thesis combines partition and legalization to study the construction algorithm of SL-OARSMT.In the SL-OARSMT problem,all the end points of nets and obstacles are on the same routing layer.In order to partition the original network,first construct an OASG,and then extract the spanning tree from the OASG and convert it into a pin spanning tree,and the original network is partitioned based on the pin spanning tree.Then the RSMT algorithm is used for each sub-network and legalized to generate a legal initial solution.At last,this thesis proposes a two-stage coarse-grained and fine-grained optimization based on "edge chain".In the coarse-grained optimization stage,optimization is considered globally;in the fine-grained optimization stage,optimization is considered locally.The two-stage optimization will further introduce Steiner points on the basis of the initial solution to reduce the wire-length.Based on the research of the SL-OARSMT,this thesis studies the ML-OARSMT(multi-layer OARSMT)algorithm.In the ML-OARSMT problem,the end points of nets and obstacles can be distributed on different routing layers.Firstly,by inserting the relay points in the layer and the vias between the layers,construct the ML-OASG(multi-layer OASG),and then extract the ML-OASMT(Multi-Layer Obstacle-Avoiding Steiner Minimum Tree).Then,ML-OARSMT can construct by turning the edges in ML-OASMT into horizontal and vertical edges.Three sets of test cases IND1?IND5,RT01?RT05 and RC01?RC12 are used to test the SL-OARSMT algorithm,and the results show that our SL-OARSMT algorithm has 1%?5%reduction in wire-length compared with connection graph based method,maze routing based method and steiner point based method.At the meanwhile,each test case is completed within 1s.For ML-OARSMT testing,we tested three self-built cases ML01?ML03 and the results show that ML-OARSMT algorithm is effective.