VLSI Physical Design : from Graph Partitioning to Timing Closure.

Intro -- Foreword -- Preface to the 2nd Edition -- Preface to the 1st Edition -- Contents -- About the Authors -- 1: Introduction -- 1.1 Electronic Design Automation (EDA) -- 1.2 VLSI Design Flow -- 1.3 VLSI Design Styles -- 1.4 Layout Layers and Design Rules -- 1.5 Physical Design Optimizations -- 1.6 Algorithms and Complexity -- Example: Exhaustively Enumerating All Placement Possibilities -- 1.7 Graph Theory Terminology -- 1.8 Common EDA Terminology -- References -- 2: Netlist and System Partitioning -- 2.1 Introduction -- 2.2 Terminology -- 2.3 Optimization Goals -- 2.4 Partitioning Algorithms -- 2.4.1 Kernighan-Lin (KL) Algorithm -- Kernighan-Lin Algorithm -- Example: KL Algorithm -- 2.4.2 Extensions of the Kernighan-Lin Algorithm -- 2.4.3 Fiduccia-Mattheyses (FM) Algorithm -- Fiduccia-Mattheyses Algorithm -- Example: FM Algorithm -- 2.5 A Framework for Multilevel Partitioning -- 2.5.1 Clustering -- 2.5.2 Multilevel Partitioning -- 2.5 Exercises -- References -- 3: Chip Planning -- 3.1 Introduction to Floorplanning -- Example: Floorplan Area Minimization -- 3.2 Optimization Goals in Floorplanning -- 3.3 Terminology -- 3.4 Floorplan Representations -- 3.4.1 Floorplan to a Constraint Graph Pair -- Example: Floorplan to a Constraint Graph Pair -- 3.4.2 Floorplan to a Sequence Pair -- Example: Floorplan to a Sequence Pair -- 3.4.3 Sequence Pair to a Floorplan -- Sequence Pair Evaluation Algorithm -- Longest Common Subsequence (LCS) Algorithm -- Example: Sequence Pair to a Floorplan -- 3.5 Floorplanning Algorithms -- 3.5.1 Floorplan Sizing -- Example: Floorplan Sizing -- 3.5.2 Cluster Growth -- Linear Ordering Algorithm -- Example: Linear Ordering Algorithm -- Cluster Growth Algorithm -- Example: Floorplan Construction by Cluster Growth -- 3.5.3 Simulated Annealing -- Simulated Annealing Algorithm -- 3.5.4 Integrated Floorplanning Algorithms.

3.6 Pin Assignment -- Example: Pin Assignment Using Concentric Circles (Including Algorithm) -- 3.7 Power and Ground Routing -- 3.7.1 Design of a Power-Ground Distribution Network -- 3.7.2 Planar Routing -- 3.7.3 Mesh Routing -- 3.7 Exercises -- References -- 4: Global and Detailed Placement -- 4.1 Introduction -- 4.2 Optimization Objectives -- Example: Total Weighted Wirelength of a Placement -- Example: Cut Sizes of a Placement -- Example: Wire Density of a Placement -- 4.3 Global Placement -- 4.3.1 Min-Cut Placement -- Min-Cut Algorithm -- Example: Min-Cut Placement Using the KL Algorithm -- Example: Min-Cut Placement Using the FM Algorithm -- Example: Min-Cut Placement with External Connections -- Example: Min-Cut Placement Considering Pins Outside of the Partitioned Region -- 4.3.2 Analytic Placement -- Example: Quadratic Placement -- Example: ZFT Position -- Force-Directed Placement Algorithm -- Example: Force-Directed Placement -- Force-Directed Placement with Ripple Move Algorithm -- 4.3.3 Simulated Annealing -- Simulated Annealing Algorithm for Placement -- 4.3.4 Modern Placement Algorithms -- 4.4 Legalization and Detailed Placement -- 4.4 Exercises -- References -- 5: Global Routing -- 5.1 Introduction -- 5.2 Terminology and Definitions -- 5.3 Optimization Goals -- 5.4 Representations of Routing Regions -- 5.5 The Global Routing Flow -- 5.6 Single-Net Routing -- 5.6.1 Rectilinear Routing -- Example: RMSTs and RSMTs -- Sequential Steiner Tree Heuristic -- Example: Sequential Steiner Tree Heuristic -- 5.6.2 Global Routing in a Connectivity Graph -- Global Routing in a Connectivity Graph -- Example: Global Routing in a Connectivity Graph -- Example: Determining Routability -- 5.6.3 Finding Shortest Paths with Dijkstra�s Algorithm -- Dijkstra�s Algorithm -- Example: Dijkstra�s Algorithm -- 5.6.4 Finding Shortest Paths with A* Search.

5.7 Full-Netlist Routing -- 5.7.1 Routing by Integer Linear Programming -- Integer Linear Programming (ILP) Global Routing Formulation -- Example: Global Routing Using Integer Linear Programming -- 5.7.2 Rip-Up and Reroute (RRR) -- Global Routing Framework with Rip-Up and Reroute -- 5.8 Modern Global Routing -- 5.8.1 Pattern Routing -- 5.8.2 Negotiated Congestion Routing -- 5.8 Exercises -- References -- 6: Detailed Routing -- 6.1 Terminology -- 6.2 Horizontal and Vertical Constraint Graphs -- 6.2.1 Horizontal Constraint Graphs -- 6.2.2 Vertical Constraint Graphs -- Example: Vertical and Horizontal Constraint Graphs -- 6.3 Channel Routing Algorithms -- 6.3.1 Left-Edge Algorithm -- Left-Edge Algorithm -- Example: Left-Edge Algorithm -- 6.3.2 Dogleg Routing -- Example: Dogleg Left-Edge Algorithm -- 6.4 Switchbox Routing -- 6.4.1 Terminology -- 6.4.2 Switchbox Routing Algorithms -- Example: Switchbox Routing -- 6.5 Over-the-Cell and Gcell Routing Algorithms -- 6.5.1 OTC Routing Methodology -- 6.5.2 OTC and Gcell Routing Algorithms -- 6.6 Modern Challenges in Detailed Routing -- 6.6 Exercises -- References -- 7: Specialized Routing -- 7.1 Area Routing -- 7.1.1 Introduction -- 7.1.2 Net Ordering -- 7.2 Non-Manhattan Routing -- 7.2.1 Octilinear Steiner Trees -- Octilinear Steiner Tree Algorithm -- Example: Octilinear Steiner Tree -- 7.2.2 Octilinear Maze Search -- 7.3 Clock Routing -- 7.3.1 Terminology -- 7.3.2 Problem Formulations for Clock-Tree Routing -- 7.4 Modern Clock Tree Synthesis -- 7.4.1 Constructing Trees with Zero Global Skew -- Basic Method of Means and Medians (BASIC_MMM(S,T)) -- Recursive Geometric Matching Algorithm (RGM(S,T)) -- Build Tree of Segments (DME Bottom-Up Phase) -- Find Exact Locations (DME Top-Down Phase) -- 7.4.2 Clock Tree Buffering in the Presence of Variation -- 7.4 Exercises -- References -- 8: Timing Closure.

8.1 Introduction -- 8.2 Timing Analysis and Performance Constraints -- 8.2.1 Static Timing Analysis -- Longest Paths Algorithm -- 8.2.2 Delay Budgeting with the Zero-Slack Algorithm -- Zero-Slack Algorithm (Late-Mode Analysis) -- Forward Path Search (FORWARD_PATH(vmin,G)) -- Backward Path Search (BACKWARD_PATH(vmin,G)) -- Near-Zero-Slack Algorithm (Early-Mode Analysis) -- 8.3 Timing-Driven Placement -- 8.3.1 Net-Based Techniques -- 8.3.2 Embedding STA into Linear Programs for Placement -- 8.4 Timing-Driven Routing -- 8.4.1 The Bounded-Radius, Bounded-Cost Algorithm -- BRBC Algorithm -- 8.4.2 Prim-Dijkstra Trade-Off -- 8.4.3 Minimization of Source-to-Sink Delay -- 8.5 Physical Synthesis -- 8.5.1 Gate Sizing -- 8.5.2 Buffering -- 8.5.3 Netlist Restructuring -- 8.6 Performance-Driven Design Flow -- 8.7 Conclusions -- 8.7 Exercises -- References -- 9: Appendix -- 9.1 Machine Learning in Physical Design -- 9.1.1 Introduction -- 9.1.2 ML: Promise and Challenges in Physical Design -- 9.1.3 Canonical ML Applications -- 9.1.4 The State of ML for Physical Design -- 9.1.5 Future Developments -- 9.2 Solutions to Chapter Exercises -- 9.2.1 Chapter 2: Netlist and System Partitioning -- 9.2.2 Chapter 3: Chip Planning -- 9.2.3 Chapter 4: Global and Detailed Placement -- 9.2.4 Chapter 5: Global Routing -- 9.2.5 Chapter 6: Detailed Routing -- 9.2.6 Chapter 7: Specialized Routing -- 9.2.7 Chapter 8: Timing Closure -- 9.3 Example CMOS Cell Layouts -- References -- Index.

Description based on publisher supplied metadata and other sources.

Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2025. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.