VLSI Physical Design (Layout Compaction, Placement & Partitioning)
1. Layout Compaction
1.1 Design Rules in Compaction
• Purpose: Ensure manufacturability while minimizing area
• Key Rules:
o Minimum width/spacing (poly, metal, diffusion)
o Via enclosure rules
o Antenna rules
• DRC Violation Types:
o Width errors
o Spacing errors
o Enclosure errors
1.2 Problem Formulation
• Input: Symbolic layout with design rule constraints
• Objective: Minimize chip area while satisfying:
• x_j - x_i ≥ d_{ij} \quad \forall \text{constraints} Constraints:
o Linear inequalities (spacing rules)
o Nonlinear (corner cases)
1.3 Constraint Graph Algorithms
1.3.1 Graph Construction
• Nodes: Layout edges (left/right, bottom/top)
• Edges: Design rule constraints with weights
• Example: Metal1 spacing → edge with weight = min spacing
1.3.2 Compaction Algorithms
Algorithm Approach Complexity Best For
Longest Path Solves critical path O(V+E) 1D compaction
Bellman-Ford Handles negative cycles O(VE) Multi-layer
LP Relaxation Formulates as linear program Polynomial Advanced nodes
Key Steps:
1. Build constraint graph
2. Solve for coordinates (x,y)
3. Iterate for multi-directional compaction
2. Placement & Partitioning
2.1 Circuit Representation
2.1.1 Netlist Models
Model Representation Usage
Hypergraph Nets connect ≥2 cells Global routing
Graph 2-pin net approximations Placement
Grid Cells mapped to bins Detailed placement
2.1.2 Common Formats
• LEF/DEF (Cadence)
• Bookshelf (ISPD contests)
2.2 Placement Algorithms
2.2.1 Global Placement
Algorithm Type Key Feature
Min-cut Partitioning-based Recursive bisection
Analytical Force-directed Quadratic programming
Simulated Annealing Stochastic Good for macros
2.2.2 Detailed Placement
• Legalization: Snap to placement sites
• Optimization: Wirelength/timing driven
• Algorithms:
o Abacus (optimal row-based)
o Diffusion-based spreading
Metrics:
• HPWL (Half-Perimeter Wirelength)
HPWL = \sum_{nets} (x_{max} - x_{min} + y_{max} - y_{min})
• Congestion: Routing demand vs supply
2.3 Partitioning
2.3.1 Problem Definition
• Input: Netlist with K partitions
• Objectives:
o Minimize cut size
o Balance partition sizes (±10%)
o Optimize timing paths
2.3.2 Algorithms
Algorithm Approach Complexity Cut Quality
Iterative improvement O(n²) Good
Kernighan-Lin
Fiduccia-Mattheyses KL with buckets O(n) Better
Multilevel Coarsening-refinement Near-linear Best
Example: FM Algorithm Steps
1. Compute initial partition
2. Calculate cell gains
3. Move highest-gain cell
4. Lock moved cell
5. Repeat until no improvement
3. Key Equations & Examples
3.1 Constraint Graph Example
Metal1 shapes A & B with min spacing=3λ
→ Edge A→B with weight=3 in x-direction graph
3.2 FM Partitioning Gain Calculation
Gain = #cuts_removed - #cuts_created
3.3 Quadratic Placement Cost
\Phi(x,y) = \sum_{nets} \frac{1}{2}(x_i - x_j)^2
*Exam Focus Areas
1 Layout Compaction
• Derive constraint graphs from layout
• Solve longest path problems
• Handle multi-layer compaction
2 Placement
• Compare algorithm tradeoffs
• Calculate HPWL improvements
• Legalization challenges
3 Partitioning
• FM algorithm steps
• Multilevel partitioning phases
• Balance vs cut size tradeoffs
Recommended Practice Problems:
1. Given a layout with 3 metal shapes, construct the constraint graph
2. Perform 2-way partitioning on a 6-cell netlist using FM
3. Compute HPWL for a 4-pin net at coordinates (1,2), (4,5), (2,7), (5,3)
