VLSI Physical Design: From Graph Partitioning to Timing Closure

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