Place and route (P&R) — Hardware notes

WHAT is P&R?

WHY it matters: In modern chips, wires — not gates — dominate delay, power, and area. A logically-correct netlist is useless until it is placed and routed legally (no overlaps, no design-rule violations) and well (meets timing/power). This is where "logic" becomes "physics."

The inputs and outputs

STEP 1 — Placement (the WHY of good placement)

Goal: minimize total wirelength while keeping cells legal (non-overlapping, on-grid, meeting timing/density).

Why wirelength is the key objective

Wire delay grows with length, and wire capacitance $\propto$ length, so: $P_{\text{dyn}} = \alpha\, C\, V^2 f, \qquad C \propto \text{wirelength}$ Shorter wires $\Rightarrow$ less $C \Rightarrow$ less delay and less dynamic power. So minimizing wirelength is a proxy for optimizing everything.

HOW we estimate wirelength: Half-Perimeter Wirelength (HPWL)

Formula HPWL — derived from first principles

Take a net with pins at coordinates $(x_i, y_i)$ . Draw the smallest rectangle containing all pins: $w = \max_i x_i - \min_i x_i, \qquad h = \max_i y_i - \min_i y_i$ A rectilinear tree must at least span $w$ horizontally and $h$ vertically, so: $\text{HPWL} = w + h = (\max x_i - \min x_i) + (\max y_i - \min y_i)$ Total placement cost $= \sum_{\text{nets}} \text{HPWL}$ .

Why half-perimeter (not full)? Full perimeter $= 2(w+h)$ double-counts: to connect corners of a box you traverse each side length once on average, not twice. For a 2-pin net HPWL is exact Manhattan distance $=|x_1-x_2|+|y_1-y_2|$ .

Placement is done in phases

Global placement — coarse positions minimizing $\sum$ HPWL (allows slight overlap; solved via analytic/quadratic optimization).
Legalization — snap cells onto rows/sites, remove overlaps with minimal movement.
Detailed placement — small local swaps to squeeze out remaining wirelength.

STEP 2 — Routing

Goal: physically connect every net using metal layers + vias, obeying design rules (min spacing/width) with no shorts/opens.

Why layered routing (Manhattan style)

Routing phases

Global routing — divides chip into a grid of GCells; decides which coarse regions each net passes through, balancing congestion (demand vs. track capacity).
Detailed routing — assigns exact tracks, wires, and vias inside each region, fixing design-rule violations (DRC).

Timing closure (why P&R iterates)

Placement affects wire length → wire delay → whether the clock constraint is met: $t_{\text{arrival}} = t_{\text{gate}} + t_{\text{wire}} \le T_{\text{clk}} - t_{\text{setup}}$ If a path is too slow after routing, the tool re-places / re-routes / buffers that path. P&R is an iterative optimization loop, not a one-shot.

Common mistakes

Active recall

Recall Feynman: explain to a 12-year-old

You have a box of toy robots and you must wire them together with string. First you pick a spot on the table for each robot so friends who talk a lot sit close (that's placement — short strings = quick chatting). Then you actually run the strings between them without letting strings cross and tangle, using little bridges when two strings must go over each other (that's routing — bridges are vias). If you seat the robots badly, no amount of clever string-running will fix the mess — so seating them well is half the battle.

Flashcards

What are the two core steps of P&R?

Placement (assign x,y locations to cells) and Routing (draw the physical wires/vias connecting nets).

What is the P&R input and output?

Input: gate-level netlist + library + floorplan + constraints; Output: GDSII geometric layout.

Define HPWL.

Half-Perimeter Wire Length

=(\max x-\min x)+(\max y-\min y)

, the width+height of a net's pin bounding box, used to estimate wirelength.

Why is HPWL "half" perimeter, not full?

A rectilinear tree spans each dimension once; full perimeter

2(w+h)

double-counts, so half-perimeter

w+h

is the right estimate. For a 2-pin net it equals Manhattan distance.

Why minimize wirelength during placement?

Wire capacitance ∝ length, so shorter wires reduce delay and dynamic power (

P=\alpha CV^2f

), and improve routability.

What are the three placement phases?

Global placement, legalization, detailed placement.

What are the two routing phases?

Global routing (assign nets to coarse GCell regions) then detailed routing (exact tracks, wires, vias, DRC-clean).

Define routing congestion.

Congestion = demand/tracks (D/T); >1 means overflow — not all nets fit, forcing detours.

Why alternate layer directions in routing?

Prevents same-layer crossings (shorts); horizontal on one layer, vertical on next, connected by vias.

What algorithm gives a guaranteed shortest maze route?

Lee's algorithm (BFS wavefront labeling + backtrace).

Why does placement determine routability?

Placement fixes pin positions; if related cells are far/clustered, congestion rises and routing may fail regardless of the router.

What timing inequality must a path satisfy?

t_{gate}+t_{wire} \le T_{clk}-t_{setup}

Connections

Logic Synthesis — produces the netlist that P&R consumes.
Floorplanning — defines chip outline/macros before placement.
Static Timing Analysis (STA) — checks if placed+routed paths meet $T_{clk}$ .
Clock Tree Synthesis (CTS) — inserted between placement and routing.
Design Rule Checking (DRC) — validates the routed geometry.
Interconnect delay / RC model — why wirelength maps to delay.
Standard Cell Library — physical + timing data driving P&R.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, P&R ka matlab hai physical design — jahan tumhara logical netlist (gates aur connections ki list) actual chip pe geometry ban jaata hai. Do main kaam hote hain: Placement — har standard cell ko chip pe ek $(x,y)$ jagah dena, aur Routing — un cells ke beech actual metal wires khichna. Soch lo LEGO board pe bricks rakhna (placement) aur phir unko strings se jodna (routing) — bina strings ko cross-tangle kiye.

Placement me humara main goal hai wirelength minimize karna, kyunki wire jitni lambi, utni zyada capacitance $C$ , aur $P=\alpha CV^2 f$ ke hisaab se zyada power aur zyada delay. Real routing se pehle length estimate karne ke liye HPWL use karte hain: net ke saare pins ke around ek bounding box banao, uski width $w$ aur height $h$ nikalo, aur $\text{HPWL}=w+h$ . Yaad rakho — half perimeter, poora nahi, warna 2x over-count ho jaata hai.

Routing me chip ko GCell grid me baant ke pehle global routing (kaunsa net kaunse region se jayega) phir detailed routing (exact track, wire, via) hota hai. Ek layer horizontal, doosri vertical — taaki same layer pe crossing (short circuit) na ho; layer change ke liye via. Agar kisi region me tracks $T$ se zyada nets $D$ crossing chahte hain to $D/T>1$ — congestion overflow, chip route hi nahi hoga.

Sabse important baat: placement hi routability decide karta hai. Agar related cells door-door ya ek jagah thuse hue rakh diye, to router kitna bhi smart ho, congestion aur timing fail ho jayenge. Isliye P&R ek iterative loop hai — place, route, timing check, buffer/re-place, repeat — jab tak $t_{gate}+t_{wire}\le T_{clk}-t_{setup}$ satisfy na ho jaaye.

Test yourself — VLSI Design

Connections