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.