Combinatorial Algorithms for Integrated Circuit Layout

The last decade has brought explosive growth in the technology for manufac- turing integrated circuits. Integrated circuits with several hundred thousand transistors are now commonplace. This manufacturing capability, combined with the economic benefits of large electronic systems, is forcing a revolution in the design of these systems and providing a challenge to those people in- terested in integrated system design. Modern circuits are too complex for an individual to comprehend completely. Managing tremendous complexity and automating the design process have become crucial issues. Two groups are interested in dealing with complexity and in developing algorithms to automate the design process. One group is composed of practi- tioners in computer-aided design (CAD) who develop computer programs to aid the circuit-design process. The second group is made up of computer scientists and mathemati'::~l\ns who are interested in the design and analysis of efficient combinatorial aJ::,orithms. These two groups have developed separate bodies of literature and, until recently, have had relatively little interaction. An obstacle to bringing these two groups together is the lack of books that discuss issues of importance to both groups in the same context. There are many instances when a familiarity with the literature of the other group would be beneficial. Some practitioners could use known theoretical results to improve their "cut and try" heuristics. In other cases, theoreticians have published impractical or highly abstracted toy formulations, thinking that the latter are important for circuit layout.

Table of Contents:
I Background.- 1 Introduction to Circuit Layout.- 1.1 Combinatorial Aspects of Circuit Layout.- 1.2 Layout Methodologies.- 1.2.1 Semicustom Versus Full-Custom Layout.- 1.2.2 Input to the Layout Problem.- 1.2.2.1 Hierarchical Circuit Description.- 1.2.2.2 Complex Cells and Cell Generators.- 1.2.3 Output of the Layout Process.- 1.2.3.1 Geometric Layouts, Mask Data.- 1.2.3.2 Topological Layouts.- 1.2.4 Layout Strategies and Styles.- 1.2.4.1 Placement and Routing of General Cells.- 1.2.4.2 Standard Cells.- 1.2.4.3 Gate Arrays.- 1.2.4.4 Sea of Gates.- 1.2.4.5 Printed Circuit Boards.- 1.2.4.6 Floorplanning.- 1.3 Summary.- 2 Optimization Problems.- 2.1 Basic Definitions.- 2.1.1 Algorithmic Problems.- 2.1.2 Deterministic Algorithms.- 2.1.3 Randomized Algorithms.- 2.1.4 Asymptotic Analysis.- 2.1.5 An Example: Quicksort.- 2.1.6 Optimization Problems.- 2.2 NP-Hardness.- 2.2.1 Feasible and Infeasible Algorithms.- 2.2.2 Nondeterministic Algorithms.- 2.2.3 NP-Completeness and NP-Hardness.- 2.3 Solving NP-Hard Problems.- 2.3.1 Restriction.- 2.3.2 Pseudopolynomial Algorithms.- 2.3.3 Approximation Algorithms.- 2.3.4 Upper and Lower Bounds.- 2.3.5 Randomization.- 2.3.6 Heuristics.- 2.4 Summary.- 2.5 Exercises.- 3 Graph Algorithms.- 3.1 Basic Definitions.- 3.2 Graph Search.- 3.3 Depth-First Search.- 3.4 Strong Components.- 3.5 k-Connectivity.- 3.6 Topological Search.- 3.7 Breadth-First Search.- 3.8 Shortest Paths.- 3.8.1 Basic Properties.- 3.8.2 Ford's Method.- 3.8.3 The Bellman-Ford Algorithm.- 3.8.4 Dijkstra's Algorithm.- 3.8.5 The Single-Pair Shortest-Path Problem.- 3.8.5.1 Goal-Directed Unidirectional Search.- 3.8.5.2 Bidirectional Search.- 3.8.6 The All-Pairs Shortest-Path Problem.- 3.8.7 Other Cost Functions.- 3.9 Minimum Spanning Trees.- 3.9.1 A Greedy Method.- 3.9.2 Prim's Algorithm.- 3.9.3 Kruskal's Algorithm.- 3.9.4 Faster Minimum-Spanning-Tree Algorithms.- 3.10 Steiner Trees.- 3.10.1 A Class of Approximation Algorithms.- 3.10.2 Using Prim's Algorithm.- 3.10.3 Using Kruskal's Algorithm.- 3.10.4 The Fastest Method.- 3.10.5 Improving Steiner Trees.- 3.11 Network Flow.- 3.11.1 Maximum Network Flow.- 3.11.2 Mincost Flow.- 3.11.3 Multicommodity Flow.- 3.12 Matching.- 3.13 Hierarchical Graph Processing.- 3.13.1 Hierarchical Graph Definitions.- 3.13.2 The Bottom-Up Method.- 3.13.3 Modifying the Input Hierarchy.- 3.13.4 The Hierarchical Analysis of Graph Families.- 3.14 Planar Graphs.- 3.14.1 Structural Properties.- 3.14.2 Planar Duality.- 3.14.3 Series-Parallel Graphs.- 3.15 Exercises.- 4 Operations Research and Statistics.- 4.1 Configuration Graphs, Local Search.- 4.2 Markov Chains.- 4.2.1 Time-Homogeneous Markov Chains.- 4.2.2 Time-Reversibility.- 4.2.3 Time-Inhomogeneous Markov Chains.- 4.3 Simulated Annealing.- 4.3.1 Convergence of Simulated Annealing.- 4.3.1.1 Analysis with Time-Homogeneous Markov Chains.- 4.3.1.2 Analysis with Time-Inhomogeneous Markov Chains.- 4.3.2 Cooling Schedules.- 4.3.2.1 Elements of a Cooling Schedule.- 4.3.2.1.1 Generating Chain.- 4.3.2.1.2 Initial Temperature.- 4.3.2.1.3 Stopping Criterion.- 4.3.2.1.4 Chain Length.- 4.3.2.1.5 Temperature Decrement.- 4.3.2.1.6 Starting Solution.- 4.3.2.2 Experimental Experience.- 4.3.3 Finite-Time Behavior of Simulated Annealing.- 4.3.4 Probabilistic Hill-Climbing Without Rejected Moves.- 4.4 Geometric Configuration Spaces and Polytopes.- 4.4.1 Convex Sets and Functions.- 4.5 Linear Programming.- 4.6 Integer Programming.- 4.6.1 Polytopes of Integer Programs.- 4.6.2 Branch and Bound.- 4.6.2.1 A Tree-Structured Formulation of Integer Programming.- 4.6.2.2 A Tree-Structured Formulation of the Minimum-Steiner-Tree Problem.- 4.6.2.3 Details of the Branch-and-Bound Algorithm.- 4.6.3 Lagrangian Relaxation.- 4.6.3.1 An Example: Steiner Trees.- 4.6.3.2 The Lagrangian Dual and its Optimization.- 4.6.3.2.1 Subgradient Optimization.- 4.6.3.2.2 Solving the Lagrangian Dual with Linear Programming.- 4.6.4 Simple Integer Programs.- 4.7 Dynamic Programming.- 4.7.1 Decomposing Optimization Problems.- 4.7.2 An Example: Minimum Steiner Trees.- 4.7.3 The Dynamic-Programming Algorithm.- 4.7.4 Application to Minimum Steiner Trees.- 4.7.5 Dynamic Programming on Hierarchical Graphs.- 4.7.5.1 Relation to the Bottom-Up Method.- 4.8 Nonlinear Optimization.- 4.8.1 The Gradient-Projection Method.- 4.8.2 Penalty-Function Methods.- 4.8.3 Quadratic Optimization.- 4.8.4 Quadratic Forms and Eigenvalues.- 4.8.5 Minimizing Quadratic Programs.- 4.9 Exercises.- II Combinatorial Layout Problems.- 5 The Layout Problem.- 5.1 Requirements.- 5.2 Definition of the Layout Problem.- 5.3 The Mincut Heuristic.- 5.4 Graph Bifurcation.- 5.5 An Approximation Algorithm.- 5.6 Balancing Bifurcators.- 5.7 Improving Secondary Cost Functions.- 5.7.1 Lower Bounds.- 5.7.2 Embedding Graphs in the Tree of Meshes.- 5.7.3 Efficient Embeddings of the Tree of Meshes.- 5.8 Discussion.- 5.9 Exercises.- 6 Circuit Partitioning.- 6.1 Definitions and Complexities.- 6.1.1 Multiway Partitions.- 6.1.2 Bipartitions.- 6.1.3 Separators.- 6.1.4 Free Partitions.- 6.1.5 Modeling Hypergraphs with Graphs.- 6.2 Heuristics for Bipartitioning Hypergraphs.- 6.2.1 The Kernighan-Lin Heuristic.- 6.2.2 The Fiduccia-Mattheyses Heuristic.- 6.2.2.1 Choosing A Vertex To Be Moved.- 6.2.2.2 Initializing the Data Structure.- 6.2.2.3 Updating the Data Structure.- 6.2.3 Higher-Order Gains.- 6.2.4* Improving Bipartitions.- 6.2.5* Extension to Multiway Partitioning.- 6.2.6 Summary.- 6.3 Simulated Annealing.- 6.4 Partitioning Planar Graphs.- 6.4.1 Separating Trees.- 6.4.2 Partitioning Partial Grid Graphs.- 6.4.3* Separating General Planar Graphs.- 6.5 Graph Partition and Network Flow.- 6.5.1* Maxflow Techniques.- 6.5.2 Multicommodity-Flow Techniques.- 6.6 Partitioning as a Nonlinear Optimization Problem.- 6.6.1 Partitioning by Quadratic Assignment.- 6.6.2 Lower Bounds.- 6.6.2.1 Bounds Based on the Hoffman-Wielandt Inequality.- 6.6.2.2 The Bound by Boppana.- 6.6.3 Heuristic Algorithms.- 6.6.3.1 The Algorithm by Barnes.- 6.6.3.2 The Algorithm by Boppana.- 6.7 Clustering Methods.- 6.8 Summary.- 6.9 Exercises.- 7 Placement, Assignment, and Floorplanning.- 7.1 Gate Arrays: Regular Placement.- 7.1.1 Definitions and Complexity.- 7.1.1.1 Cost Functions Based on Wire Length.- 7.1.1.2 Cut-Based Cost Functions.- 7.1.1.3 Remarks on Estimates of Connection Cost.- 7.1.2 Linear Arrangement.- 7.1.3 Mincut-Based Placement of Gate Arrays.- 7.1.4 Wire-Length Minimization.- 7.1.4.1 Linear Wire Length.- 7.1.4.2 Quadratic Wire Length.- 7.1.4.3 Incorporating Timing Optimization in Placement.- 7.1.5 Elimination of Overlap.- 7.1.5.1 Linear Assignment.- 7.1.5.2 Mincut.- 7.1.5.3 Quadratic Optimization.- 7.1.5.4 Nets as Points.- 7.1.6 The Linear Probe Technique.- 7.1.7* Placement Improvement and Placement Heuristics.- 7.2 General Cells: Floorplanning.- 7.2.1 Floorplanning Based on Mincut.- 7.2.1.1 Floorplanning Based on Oriented Mincut.- 7.2.1.1.1 Similarity Relation for Oriented Mincut.- 7.2.1.1.2 Slicing Floorplans.- 7.2.1.2 Floorplan Sizing.- 7.2.1.2.1 Sizing of Fixed Cells.- 7.2.1.2.2 Sizing of Variable Cells.- 7.2.1.2.3 Sizing Nonslicing Floorplans.- 7.2.1.3 Floorplanning Based on Unoriented Mincut.- 7.2.1.3.1 Sizing Based on Unoriented Mincut.- 7.2.1.3.2 Ordering Mincut Floorplans.- 7.2.2* Floorplanning Based on Multiway Mincut and Clustering.- 7.2.2.1* Floorplanning by Clustering.- 7.2.2.2* Floorplanning by Multiway Mincut.- 7.2.2.3* Combining the Methods.- 7.2.3* Combination of Mincut and Wire-Length Minimization in Floorplanning.- 7.2.4* Floorplanning Based on Rectangular Dualization.- 7.2.4.1* Planarization of the Circuit.- 7.2.4.2* Floorplan Sizing.- 7.2.5* Nonlinear Methods for General-Cell Placement.- 7.2.6* Estimation of Wiring Area in Floorplan Sizing.- 7.2.7* Other Issues in Floorplanning.- 7.2.7.1* Rectagonal Blocks.- 7.2.7.2* Information Flow in Floorplanning.- 7.2.7.3* Other Constraints and Cost Functions.- 7.3 Assignment Problems.- 7.3.1 Gate Assignment.- 7.3.1.1 Gate-Array Design.- 7.3.1.2 Layout of Printed Circuit Boards and Design of Standard Cells.- 7.3.2* Pin Assignment.- 7.4 Simulated Annealing.- 7.4.1 Arithmetic Expressions for Slicing Floorplans.- 7.4.2 The Configuration Graph.- 7.4.3 The Cost Function.- 7.4.4 Randomization.- 7.4.5 Experimental Results.- 7.4.6 Extensions.- 7.5 Summary.- 7.6 Exercises.- 8 Global Routing and Area Routing.- 8.1 Definitions and Complexity.- 8.1.1 Routing in Floorplans.- 8.1.2 Area Routing.- 8.1.3 Complexity of Global Routing Problems.- 8.2 Global Routing and Integer Programming.- 8.2.1 The Integer Program for the Constrained Global Routing Problem.- 8.2.2 The Integer Program for the Unconstrained Global Routing Problem.- 8.2.3 Special Cases.- 8.2.4 The Integer Program for the Area-Routing Problem.- 8.2.5 Solution of the Integer Programs.- 8.2.6 Extensions of the Problem Formulation.- 8.3 Overview of Global Routing Methods.- 8.4 Sequential Routing Algorithms.- 8.4.1 Maze-Running Algorithms.- 8.4.1.1 Coding Techniques.- 8.4.1.2 Goal-Directed Search Techniques.- 8.4.1.3 Finding Suboptimal Paths.- 8.4.2 Line-Searching Algorithms.- 8.4.2.1 Heuristic Techniques.- 8.4.2.2 An Algorithmic Framework for Line Searching.- 8.4.2.3 The Track Graph.- 8.4.2.3.1 Construction of the Track Graph.- 8.4.2.4 Summary.- 8.4.3 Steiner Tree Heuristics in Sequential Routing.- 8.4.3.1 Steiner Tree Heuristics for Maze Running.- 8.4.3.2 Steiner Tree Heuristics for Line Searching.- 8.4.4 Incorporating Other Cost Measures.- 8.4.4.1 Applications of Dijkstra's Algorithm.- 8.4.4.2* Beyond Dijkstra's Algorithm.- 8.5 Hierarchical Global Routing Algorithms.- 8.5.1 Definition of the Routing Hierarchy.- 8.5.2 The Primitive Global Routing Problems.- 8.5.3 Top-Down Methods.- 8.5.3.1 Sequential Routing Refinement.- 8.5.3.2 Refinement with Integer Programming.- 8.5.3.3* A Method Based on Linear Assignment.- 8.5.4* Bottom-Up Methods.- 8.6 Routing by Relaxation.- 8.6.1 Routing by Randomized Rounding.- 8.6.1.1 Gate Arrays, Two-Terminal Nets, Few Routes per Net.- 8.6.1.2 Gate Arrays, Two-Terminal Nets, Many Routes per Net.- 8.6.1.3 Multiterminal Nets.- 8.6.1.4 Other Routing Variants.- 8.6.1.4.1 Nonuniform Edge Capacities.- 8.6.1.4.2 Constrained Global Routing Problems.- 8.6.1.5 Experimental Results.- 8.6.1.6 Prerequisites for the Applicability of Randomized Rounding.- 8.6.2 Making the Method Deterministic.- 8.6.2.1 Estimating the Conditional Probabilities.- 8.6.2.1.1 Defining the Pessimistic Estimator at the Root.- 8.6.2.1.2 Propagating the Estimate Through the Decision Tree.- 8.6.2.2 Run Time.- 8.7* Determining the Locations of the Pins.- 8.8* Integration of Global Routing and Floorplanning.- 8.8.1* The Algorithmic Approach.- 8.8.2* The Data-Structure Approach.- 8.9* Simulated Annealing.- 8.10 Summary.- 8.11 Exercises.- 9 Detailed Routing.- 9.1 Basic Definitions.- 9.1.1 Homotopic Routing.- 9.1.2 Detailed Routing Graphs.- 9.1.2.1 Channel Routing.- 9.1.2.2 Switchbox Routing.- 9.1.2.3 Other Detailed-Routing Graphs.- 9.1.3 Detailed Routing Models.- 9.1.3.1 Planar Routing.- 9.1.3.2 Knock-Knee Routing.- 9.1.3.3 Manhattan Routing.- 9.1.3.4 Gridless Routing.- 9.1.3.5 Multilayer Models.- 9.2 Theories of Detailed Routing.- 9.3 Planar Routing.- 9.3.1 Planar Channel Routing.- 9.3.1.1 Basic Theory.- 9.3.1.2 The Channel-Placement Problem.- 9.3.1.2.1 A Solution via Shortest Paths.- 9.3.1.2.2 A Linear-Time Algorithm.- 9.3.1.2.3* Minimizing Total Wire Length.- 9.3.1.3 Channel-Width Minimization.- 9.3.1.4* Irregular Channels and Multiterminal Nets.- 9.3.1.5* Stacks of Channels.- 9.3.2 General Planar Routing.- 9.4 Nonplanar Channel Routing.- 9.5 Detailed Routing in the Knock-Knee Model.- 9.5.1 Channel Routing in the Knock-Knee Model.- 9.5.2 Other Detailed-Routing Graphs.- 9.5.2.1 The General Method.- 9.5.2.2 An Example: Routing in Switch Graphs.- 9.5.2.2.1 Relaxing the Evenness Condition.- 9.5.2.2.2 Multiterminal Nets.- 9.5.2.3* Other Results on Knock-Knee Routing.- 9.5.2.3.1* Switchboxes.- 9.5.2.3.2* Switch Graphs.- 9.5.2.3.3* Homotopic Routing in General Detailed-Routing Graphs.- 9.5.2.3.4* The Evenness Condition.- 9.5.3 Layer Assignment.- 9.5.3.1 The Layer-Assignment Algorithm by Tollis.- 9.5.3.2 Net Orderings and Layer Graphs.- 9.5.3.3 Constructing Layer Graphs.- 9.5.3.4 Via Minimization.- 9.5.3.4.1 Via Minimization with Two Wiring Layers.- 9.5.3.4.2 Incorporation of Multiterminal Nets.- 9.5.3.4.3* Other Results.- 9.5.4 Summary.- 9.6 Detailed Routing in the Manhattan Model.- 9.6.1 Channel Routing in the Manhattan Model.- 9.6.1.1 Lower Bounds on the Channel Width.- 9.6.1.2 Application of the General Channel-Routing Method.- 9.6.1.3 Routing Based on the Jog-Free Model.- 9.6.1.4 Routing with Jogs and Other Generalizations.- 9.6.2* Manhattan Routing in Other Detailed-Routing Graphs.- 9.7 Channel-Placement Problems in Nonplanar Routing Models.- 9.7.1 Channel-Offset Problems.- 9.7.2 Channel-Placement Problems.- 9.8* Detailed Routing Without Homotopies.- 9.9 Detailed Routing in Gridless Routing Models.- 9.9.1* Gridless Planar Routing.- 9.9.2 Gridless Manhattan Channel Routing.- 9.10 Channel Routing in Multilayer Models.- 9.10.1 Derivatives of the Knock-Knee Model.- 9.10.1.1 The Two-Layer Knock-Knee Model.- 9.10.1.2* The Three-Layer Knock-Knee Model.- 9.10.1.3 The Unit-Vertical Overlap Model.- 9.10.1.4 Multilayer Models with Unrestricted Overlap.- 9.10.2 Channel Routing in Sparse Multilayer Models.- 9.10.3 Practical Multilayer Channel Routing.- 9.11 Summary.- 9.12 Exercises.- 10 Compaction.- 10.1 Basic Definitions.- 10.1.1 Geometric Layouts.- 10.1.2 One-Dimensional Mask-Layout Compaction.- 10.1.3 Two-Dimensional Compaction.- 10.1.4 Topological Compaction.- 10.2 One-Dimensional Compaction Algorithms.- 10.2.1 Compression-Ridge Method.- 10.2.2 Graph-Based Compaction.- 10.2.2.1 Generating Small Layout Graphs.- 10.2.2.1.1 The One-Layer Case.- 10.2.2.1.2 Multiple Layers.- 10.2.2.2 Finding Shortest Paths Quickly.- 10.2.2.2.1 Grouping Constraints.- 10.2.2.2.2 Diverse Constraints.- 10.2.2.2.3 Negative Circuits.- 10.2.2.2.4 Use of Dijkstra's Algorithm.- 10.2.2.3 Wire Balancing.- 10.2.3* Incremental Compaction.- 10.3 Two-Dimensional Compaction.- 10.3.1 Two-Dimensional Packing.- 10.3.2 Extension of the Method.- 10.3.3* 11/2-Dimensional Compaction.- 10.4 Hierarchical Compaction.- 10.4.1 Hierarchical One-Dimensional Packing.- 10.4.2 Hierarchical One-Dimensional Compaction.- 10.4.3 Maintaining the Layout Hierarchy.- 10.4.4 Hierarchical Compaction with Identical Cells.- 10.4.4.1 Toroidal Compaction of Two-Dimensional Cell Arrays.- 10.4.4.2 The General Case.- 10.5* Topological Compaction.- 10.6 Summary.- 10.7 Exercises.- Author Index.