VLSI Placement and Global Routing Using Simulated Annealing

VLSI Placement and Global Routing Using Simulated Annealing [electronic resource] / by Carl Sechen.

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...

Full description

Saved in:
Bibliographic Details
Online Access: Full Text (via Springer)
Main Author: Sechen, Carl
Format: Electronic eBook
Language:English
Published: Boston, MA : Springer US, 1988.
Series:Kluwer international series in engineering and computer science. VLSI, computer architecture, and digital signal processing ; 54.
Subjects:
Engineering.
Computer engineering.
Systems engineering.
Computer organization.
Table of Contents:
  • 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.

Similar Items