1、CDCTree: Novel Obstacle-Avoiding Routing Tree Construction based on Current Driven Circuit Model,Speaker: Lei He,Outline,IntroductionCircuit Model and Tree ConstructionExperimental ResultsConclusion,Motivation,Constructing a rectilinear Steiner minimal tree (RSMT) is a fundamental problem For CAD an
2、d algorithm developmentMacro cells, IP blocks, and pre-routed nets are often regarded as obstaclesObstacle-avoiding RSMT (OARSMT) construction is often used to estimate wire length and delay for global routingOARSMT is NP-hard, and there exists a large room to improve existing heuristics,OARSMT Form
3、ulation,Given: terminal set N and obstacle set O in the Manhattan planar.Find: rectilinear Steiner trees ST to connect all terminals in N while avoiding all obstacles in O.objective: minimize total wire length L,Existing Algorithms,Algorithms (complexity depends on the size of routing area) Maze rou
4、ting C.Y. Lee, 1961 Line search routing K. Mikami and K. Tabuchi, 1968; D.W. Hightower, 1969Algorithms (complexity depends on the size of cases) G3S, B3S, and G4S heuristics J. L. Ganley and J. P. Cohoon,1994 Exact OAESMT M. Zachariasen and P. Winter, 1999 Based on generalized connection graph Z. Zh
5、ou, C. D. Jiang, L. S. Huang, et al, 2003 2-step heuristic Y. Yang, Q. Zhu, T. Jing, X. L. Hong, et al, 2003 FORst Y. Hu, Z. Feng, T. Jing et al, 2004 An-OARSMan Y. Hu, Z. Feng, T. Jing et al, 2005,Primary Contribution of this Paper,All existing algorithms are based on combinatorial optimizationWe p
6、ropose to simulate routing problem by current-driven circuit, and called our algorithm as CDCtree A new addition to simulated algorithms such as simulated annealing, genetic algorithm, and force-based placement Similar idea used in Y. Shi et al, 2004 for traffic flow distribution problem.Experiments
7、 show that we reduce wire length by up to 11.4% Compared to the best existing algorithm,Outline,IntroductionCircuit Model and Tree ConstructionExperimental ResultsConclusion,CDCTree: Overview (Two-step procedure),Input Terminal and Obstacle Location and Shape,correlation between current distribution
8、 and OARSMT,Circuit Model,Build escape graph by vertical and horizontal lines from terminals and obstacle edges Place a resistor at each edge of the graph Add a current source at each terminal Connect the circuit to the ground by Either infinite grid (accurate but expensive) Or connecting periphery
9、nodes to GND via resistors (approximation)Mapping from (a) routing graph to (b) circuit model,Values of Resistors,GND Resistor Constant R = 1ohmEDGE Resistor Longer edge smaller current Set R = 10 log(L), where 10 is used to guarantee R 0 Obstacle Resistor usually have larger current (current flow c
10、ongestion effect) Set R = 20 log (L) to offset the effect,Circuit Simulation,The current through each edge can be solved by using nodal analysis (NA) method .The equations can be written in matrix form as Ax=b, where A is a positive definite diagonally dominant sparse matrix.The equations can be sol
11、ved efficiently.,Current versus Routing (Key of this work),Edges with smaller currents construct the tree.In general, short-cuts between terminals have stronger compelling forces from current sources at terminals, and therefore have smaller current.,Tree Construction,Simultaneously start from each t
12、erminal and always try to select the edge with the minimum currentTo compensate for the effect that GND resistors draw large current May not move to the periphery node,Tree Construction,When a neighbor is already visited by the same track, perform U-reduction,Tree Construction,When a neighbor is alr
13、eady visited by other tracks, merge them,Outline,IntroductionCircuit Model Construction and Tree Algorithm Experimental ResultsConclusion,Experiment Setting,Experiment platform Hardware: sun V880 fire workstation Software: gcc2.9.1, solaris5.8Benchmark data Randomly generate terminals with several k
14、inds of rectilinear polygon obstacles rectangle, L-shaped, cross-shaped, etc. Compare to the best existing algorithm: An-OARSMan Hu et al, 2005,Comparison with An-OARSMan,.,CDCtree reduces the wire length by up to 11.4%,Comparison with An-OARSMan,Runtime I : solve linear equations (dominance); Runti
15、me II: construct RSMT Gaussian-Sediel iteration is currently used and over 1000x speedup can be achieved to make runtime in Part I negligible.,Routing with Convex Obstacles,Examples from Hu et al, 2005,Routing with Concave Obstacles,Examples from Hu et al, 2005,Outline,IntroductionCircuit Model Cons
16、truction and Tree Algorithm Experimental ResultsConclusion,Conclusion,A new simulation based CAD algorithm to simulate routing by current-driven circuit (CDCtree)CDCtree reduces wire length by up to 11.4% compared to best existing algorithmOur newest results able to reduce runtime by 100x and with up to 15% more reduction of wire length,
