VLSI Placement and Global Routing Using Simulated Annealing

From my B.E.E degree at the University of Minnesota and right through my S.M. degree at M.I.T., I had specialized in solid state devices and microelectronics. I made the decision to switch to computer-aided design (CAD) in 1981, only a year or so prior to the introduction of the simulated annealing algorithm by Scott Kirkpatrick, Dan Gelatt, and Mario Vecchi of the IBM Thomas 1. Watson Research Center. Because Prof. Alberto Sangiovanni-Vincentelli, my UC Berkeley advisor, had been a consultant at IBM, I re ceived a copy of the original IBM internal report on simulated annealing approximately the day of its release. Given my background in statistical mechanics and solid state physics, I was immediately impressed by this new combinatorial optimization technique. As Prof. Sangiovanni-Vincentelli had suggested I work in the areas of placement and routing, it was in these realms that I sought to explore this new algorithm. My flJ'St implementation of simulated annealing was for an island-style gate array placement problem. This work is presented in the Appendix of this book. I was quite struck by the effect of a nonzero temperature on what otherwise appears to be a random in terchange algorithm.

Contenu
1 Introduction.- 1.1 Placement and Global Routing of Integrated Circuits.- 1.3 Previous Approaches to Placement and Global Routing.- 1.4 A New Approach to Cell-Based Placement and Global Routing.- 2 The Simulated Annealing Algorithm.- 2.1 Introduction.- 2.2 The Basic Simulated Annealing Algorithm.- 2.3 Theoretical Investigations of the Simulated Annealing Algorithm.- 2.4 Overview of Work on General Annealing Schedules.- 2.5 Implementations of Simulated Annealing for Placement and Global Routing.- 2.6 The Function f().- 2.7 Fast Evaluation of the Exponential Function.- 3 Placement and Global Routing of Standard Cell Integrated Circuits.- 3.1 Introduction.- 3.2 The General TimberWolfSC Methodology.- 3.3 The Algorithm for Stage 1 of TimberWolfSC.- 3.4 The Algorithms for Stage 2 of TimberWolfSC.- 3.5 The Algorithm for Stage 3 of TimberWolfSC.- 3.6 TimberWolfSC Results.- 4 Macro/Custom Cell Chip-Planning, Placement, and Global Routing.- 4.1 Introduction.- 4.2 The General TimberWolfMC Methodology.- 4.3 The Algorithm for Stage 1 of TimberWolfMC.- 4.4 The Algorithms for Stage 2 of TimberWolfMC.- 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.5 Average Interconnection Length for Random Placements Having Nets of Arbitrary Pin Counts.- 5.6 A Model for Optimized Placement.- 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.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.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.- 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.