placement routing

**Automated Placement and Routing (APR)** is the **algorithmic placement of cells into rows and routing of interconnects on metal layers — minimizing wire length, meeting timing constraints, avoiding DRC violations — completing the physical design and enabling design-to-manufacturing transition**. APR is the core of physical design automation. **Global Placement (Simulated Annealing / Gradient)** Global placement determines approximate cell location (x, y) to minimize wirelength and congestion. Algorithms include: (1) simulated annealing — iterative random cell swaps, accepting/rejecting swaps based on cost function (wirelength + timing + congestion), temperature parameter controls acceptance rate, (2) force-directed / gradient — models cells as masses connected by springs (nets as springs), iteratively moves cells to minimize energy. Modern tools (Innovus) use hierarchical placement (placement at multiple hierarchy levels) for speed. Global placement typically completes in hours for 10M-100M cell designs. **Legalization (Non-Overlap)** Global placement ignores cell dimensions, allowing overlaps. Legalization shifts cells into rows (avoiding overlaps) while minimizing movement from global placement result. Legalization uses: (1) abacus packing — places cells in predefined rows, shifting cells to nearest legal position, (2) integer linear programming — solves assignment of cells to rows/columns. Target: minimize movement (preserve global placement quality), achieve zero overlap. **Detailed Placement (Optimization)** After legalization, detailed placement optimizes cell order within rows for timing/routability. Optimization includes: (1) swapping adjacent cells if improves timing, (2) moving cells to reduce congestion, (3) balancing cell distribution (even utilization across rows). Detailed placement is local (doesn't change global block structure), targeting within-row and within-few-rows optimization. Timing-driven detailed placement can recover 5-10% timing margin by cell repositioning alone. **Global Routing (Channel Assignment)** Global routing assigns nets to routing channels (spaces between cell rows) and determines approximate routing paths. Global router: (1) divides chip into grid of regions, (2) for each net, finds least-congested path through grid (similar to Steiner tree), (3) increments congestion counter for regions used. Global routing estimates routable capacity: each region has limited metal tracks. Overuse of region (congestion >100%) indicates future routing may fail in that region. Global router output: routed congestion map and estimated wire length. **Track Assignment and Detailed Routing** Detailed routing assigns specific metal tracks and vias. Process: (1) assign tracks — within each routing region, assign specific metal1/metal2 tracks to each net, (2) route on grid — follow track assignments, add vias at layer transitions. Detailed router handles: (1) DRC compliance (spacing rules, via enclosure, antenna rules), (2) timing optimization (critical paths on shorter routes, less delay), (3) congestion resolution (reroute congested regions, may require re-assignment of other nets). **DRC-Clean Sign-off Routing** Routing completion requires DRC cleanliness: zero shorts (nets properly separated), zero opens (all nets fully connected). Sign-off routing tools (Innovus, ICC2, proprietary foundry routers) produce DRC-clean results before design release. Verification steps: (1) LVS (extract netlist from routed layout, compare to schematic), (2) DRC (verify all rules met), (3) parameter extraction (R, C from final layout for timing sign-off). **Timing-Driven and Congestion-Aware Algorithms** Modern APR is multi-objective: (1) timing-driven — optimize critical paths, reduce delay, (2) congestion-aware — minimize routing congestion (avoid dense regions), (3) power-aware — reduce total wire length and switching activity (power ∝ wire length and activity). Trade-offs exist: tight timing may force routing detours (increased congestion); aggressive congestion reduction may cause timing violations. Multi-objective optimization balances these. **Innovus/ICC2 Design Flow** Innovus (Cadence) and ICC2 (Synopsys) are industry-standard APR tools. Typical flow: (1) import netlist and constraints, (2) floorplanning (define block boundaries, I/O placement), (3) power planning (define power straps, add decaps), (4) placement (global, legalization, detailed), (5) CTS (insert clock buffers, balance skew), (6) routing (global, detailed, sign-off), (7) verification (LVS, DRC, timing, power). Each step is parameterized (effort level, optimization goals) and iterative. Typical design cycle: weeks to months depending on chip size and complexity. **Design Quality and Convergence** Quality of APR result directly impacts design schedules: (1) timing closure — percentage of paths meeting timing; aggressive designs may require 3-5 iterations to close, (2) routing congestion — if severe, major rerouting required (long turnaround), (3) power — if power exceeds budget, must reduce switching activity or lower frequency. Design teams often use intermediate checkpoints (partial placement, partial routing) to assess convergence early and avoid late surprises. **Why APR Matters** APR translates design intent (netlist, constraints) into manufacturable layout. Quality of APR directly impacts first-pass silicon success and design cycle time. Advanced APR capabilities (timing-driven, power-aware) are competitive differentiators for EDA vendors. **Summary** Automated placement and routing is a mature EDA discipline, balancing multiple objectives (timing, power, congestion, DRC). Continued algorithmic advances (machine learning, new heuristics) promise improved convergence and design quality.