VLSI Placement and Global Routing Using Simulated Annealing

3.6.3 The effectiveness of stage 3 of TimberWolfSC.- 3.6.4 TimberWolfSC comparisons including stage 3.- 4 Macro/Custom Cell Chip-Planning, Placement, and Global Routing.- 4.1 Introduction.- 4.2 The General TimberWolfMC Methodology.- 4.2.1 Algorithms for handling rectilinear ceils.- 4.2.1.1 The bust() algorithm.- 4.2.1.2 The unbust() algorithm.- 4.2.2 Generating the initial placement configuration.- 4.2.3 Custom-cell pin placement.- 4.2.3.1 Introduction to the TimberWolfMC pin site methodology.- 4.3 The Algorithm for Stage 1 of TimberWolfMC.- 4.3.1 The cost function.- 4.3.1.1 The first term in the cost function.- 4.3.1.2 The second term in the cost function.- 4.3.1.3 The third term in the cost function.- 4.3.2 The generate() function.- 4.3.2.1 Introduction.- 4.3.2.2 The Range Limiter.- 4.3.2.3 Single-cell displacement-point selection.- 4.3.3 Additional stage 1 simulated annealing algorithmic details.- 4.4 The Algorithms for Stage 2 of TimberWolfMC.- 4.4.1 Channel generation.- 4.4.2 Global routing.- 4.4.3 Placement refinement.- 4.5 TimberWolfMC Results.- 4.6 Conclusion.- 5 Average Interconnection Length Estimation.- 5.1 Introduction.- 5.2 The Placement Model.- 5.3 Previous Approaches.- 5.4 Average Interconnection Length for Random Placements under the Assumption of Two-Pin Nets.- 5.4.1 Practical considerations.- 5.5 Average Interconnection Length for Random Placements Having Nets of Arbitrary Pin Counts.- 5.5.1 Results.- 5.6 A Model for Optimized Placement.- 5.6.1 The average number of other cells connected to a cell.- 5.6.1.1 The new method.- 5.6.1.2 Practical considerations.- 5.6.1.3 Results.- 5.6.2 A notion of optimized placement.- 5.6.3 The enclosing Cm × Cs rectangles.- 5.7 Results.- 6 Interconnect-Area Estimation for Macro Cell Placements.- 6.1 Introduction.- 6.2 Interconnect-Area Estimation Based on Average Net Traffic.- 6.3 Baseline Channel Width Modulation Based on Channel Position.- 6.4 Associating the Estimated Interconnect Area with the Cell Edges.- 6.5 Interconnect-Area Estimation as a Function of Relative Pin Density.- 6.6 The Implementation of the Dynamic Interconnect-Area Estimator.- 6.7 Results.- 7 An Edge-Based Channel Definition Algorithm for Rectilinear Cells.- 7.1 Introduction.- 7.2 The Basic Channel Definition Algorithm.- 7.2.1 Identifying critical cell-edge pairs.- 7.2.2 Characterization of fixed cell edges.- 7.2.3 An algorithm for finding critical regions.- 7.3 The Generation of the Channel Graph.- 7.4 The Generation of the Channel Routing Order.- 8 A Graph-Based Global Router Algorithm.- 8.1 Introduction.- 8.2 Basic Graph Algorithms Used by the Global Router.- 8.2.1 Prim's algorithm for the minimum spanning tree problem.- 8.2.2 Dijkstra's algorithm for the shortest path problem.- 8.2.3 Lawler's algorithm for finding the M-shortest paths.- 8.3 The Algorithm for Generating M-Shortest Routes for a Net.- 8.4 The Second Phase of the Global Router Algorithm.- 8.5 Results.- 9 Conclusion.- 9.1 Summary.- 9.2 Future Work.- 9.2.1 Simulated annealing.- 9.2.2 Row-based cell placement.- 9.2.3 Row-based global routing.- 9.2.4 Macro/custom cell placement.- 9.2.5 Interconnection length estimation.- 9.2.6 Channel definition.- 9.2.7 Graph-based global routing.- Appendix Island-Style Gate Array Placement.- A.1 Introduction.- A.2 The Implementation of the Simulated Annealing Functions.- A.2.1 The generation of new states.- A.2.2 The cost function.- A.2.2.1 The first cost function.- A.2.2.2 The second cost function.- A.2.3 The inner loop criterion.- A.2.5 The stopping criterion.- A.3 Results.- A.3.1 Performance comparison of the two cost functions.- A.3.2 Performance comparison on benchmark problems.