Combinatorial Algorithms for Integrated Circuit Layout

'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 Programmi