Xapplicable Theory in Computer Science

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.