Placement & Optimisation

Placement decides the exact location of millions of standard cells. Learn wirelength (HPWL) as the objective, global placement (analytical and annealing), legalization and detailed placement, timing-driven and congestion-driven placement, density, and placement-time optimisation (buffering, sizing, cloning, Vt swaps) — with a working simulated-annealing placer in Python.

Placement assigns every standard cell to a legal site in the rows so that connected cells are close together. Shorter wires mean less delay, less power and easier routing.

Real placers handle 10⁷–10⁹ cells with analytical methods (treating cells as particles pulled by nets and pushed apart by density), then legalize them into rows and polish locally. Along the way the tool resizes gates and inserts buffers to fix timing.

An analogy

Placement is seating guests at a huge wedding: people who talk a lot (connected cells) should sit together, but no seat can be double-booked (legalization) and aisles must stay clear (congestion).

What placement optimises

The main goal is short total wirelength, estimated quickly with HPWL. Secondary goals are meeting timing (critical nets short), avoiding congestion (not too many wires in one area) and keeping density even for power and heat.

Global → legal → detailed

Placement happens in stages:

Timing- and congestion-driven

Timing-driven placement weights critical nets more heavily so their cells cluster. Congestion-driven placement estimates routing demand (via global routing or RUDY maps) and spreads cells from hotspots, sometimes using cell padding or partial blockages.

Optimisation during placement

Placement is interleaved with netlist optimisation: gate sizing, buffer insertion on long wires, logic restructuring, cell cloning to split fan-out, pin swapping, and swapping high-V_t cells to low-V_t on critical paths (and back elsewhere for leakage). Scan-chain reordering follows placement to shorten scan wires. The result is judged by WNS/TNS, congestion overflow and design-rule violations (max transition, capacitance, fan-out).

Formulas

Worked example: HPWL

Given: Net pins at (0,0), (3,1), (1,4)

Find: HPWL.

Answer: HPWL = 7

Worked example: Annealing acceptance

Given: Δ = +2, T = 5 and T = 0.5

Find: Acceptance probability.

Answer: 67% early, 1.8% late

Worked example: Wire delay

Given: Copper, 0.08 Ω/□, 0.1 µm wide, 0.2 fF/µm, 1 mm long

Find: 50% delay.

Answer: ≈ 61 ps (5 mm → 1.5 ns: quadratic!)

Simulated-annealing placer minimising HPWL

import math, random
random.seed(7)

GRID = 4                                         # 4 x 4 placement sites
N = 8                                            # cells
nets = [(0, 1), (1, 2), (2, 3), (3, 0), (4, 5), (5, 6), (6, 7), (0, 4), (2, 6), (1, 5, 7)]

def hpwl(pos):                                   # half-perimeter wirelength
    total = 0
    for net in nets:
        xs = [pos[c][0] for c in net]
        ys = [pos[c][1] for c in net]
        total += (max(xs) - min(xs)) + (max(ys) - min(ys))
    return total

sites = [(x, y) for x in range(GRID) for y in range(GRID)]
random.shuffle(sites)
pos = {c: sites[c] for c in range(N)}            # random initial placement
start = hpwl(pos)

T = 5.0
while T > 0.01:                                  # simulated annealing
    for _ in range(100):
        a, b = random.sample(range(N), 2)
        before = hpwl(pos)
        pos[a], pos[b] = pos[b], pos[a]          # propose a swap
        delta = hpwl(pos) - before
        if delta > 0 and random.random() > math.exp(-delta / T):
            pos[a], pos[b] = pos[b], pos[a]      # reject: undo
    T *= 0.9
print(f"HPWL: random {start} -> annealed {hpwl(pos)}")
# HPWL: random 30 -> annealed 18

Accepting some uphill moves at high temperature lets the placer escape local minima; as T cools it becomes greedy. TimberWolf used this in the 1980s; modern placers (RePlAce, DREAMPlace) use analytical/electrostatic methods but the objective is the same HPWL.

Common mistakes

Applications

Key takeaways

Going further