Why it's used: Computes instantly in O(n) time — a fast first estimate before running the heavier RSMT model.
Limitation: Always underestimates real wire length because actual wires share Steiner junctions and route around obstacles.
Half-Perimeter Wire Length is the simplest wire estimation in EDA. Given a group of pins, it computes half the perimeter of the smallest bounding rectangle. No routing needed — just find MinX, MaxX, MinY, MaxY.
213 groups of components need fast evaluation. HPWL gives an instant estimate for all simultaneously before RSMT. It also drives the Problem 2 objective function (grid density) where speed matters more than precision.
For points (x₁,y₁)…(xₙ,yₙ):HPWL = (max(xᵢ)−min(xᵢ)) + (max(yᵢ)−min(yᵢ))
Exactly half the bounding rectangle's full perimeter — hence the name.
HPWL always underestimates. RSMT (with Steiner points) is more accurate but slower. For 2-pin groups they are equal. For 3+ pins the gap grows. The paper uses both: HPWL for speed in SA, RSMT for final accuracy scoring.
A virtual branching node — not a real component — added purely to shorten total wire length. Named after mathematician Jakob Steiner. These junction points let wires share paths rather than running independently to each pin.
Direct connections waste wire. If A, B, and C share a nearby region, routing through a central point S means portions of wire are shared. Even one Steiner point can cut total wire 10–25%. In the paper it's applied across all 213 groups.
Real chip wires can only travel horizontally or vertically — no diagonals. So Manhattan distance |Δx|+|Δy| is used. The resulting tree is a Rectilinear Steiner Minimum Tree (RSMT), not a Euclidean one.
Steiner points are added iteratively to each of the 213 groups. Then Kruskal's algorithm builds the MST on the expanded point set. The result is compared to Grey Relational reference data to produce a quality score from 0 to 1.
A Spanning Tree connects all N nodes using exactly N−1 edges with no cycles. The MST minimises the total edge weight — in VLSI this means the minimum total wire needed to connect all pins in a group.
1. Sort all edges by length (shortest first).
2. For each edge: if it connects two separate components → add it.
3. If both nodes already connected → reject (loop).
4. Stop when N−1 edges added.
To detect loops instantly, Kruskal's uses a Union-Find (Disjoint Set) structure. Each node starts in its own set. Adding an edge merges two sets. If both nodes are already in the same set → loop detected → reject.
After Steiner points are added to a group, Kruskal's runs on the expanded set (real components + virtual Steiner helpers). The MST produced — using only horizontal/vertical edges — is the RSMT. Its quality is scored via Grey Relational Analysis.
Cooling: Move size shrinks. P = e−Δf/T falls — more selective.
Cold phase: Only improvements accepted — converges to best layout.
Try it: Set α = 0.999 (slow cool) vs 0.970 (fast) and compare results!
SA is a probabilistic optimisation algorithm inspired by metallurgical annealing — heating metal then cooling slowly so atoms settle into a low-energy state. Used for NP-Hard problems like VLSI placement where exhaustive search is impossible.
Always moving to a better state leads to local optima — solutions that look best nearby but aren't globally optimal. Accepting worse solutions with probability P = e^(−Δf/T) lets the algorithm escape traps. High T = escape often. Low T = almost never.
Initial temperature: T = 100
Cooling rate: α = 0.992
Outer iterations: M = 100
Inner steps per T: LK = 500
Move type: SHIFT operation
Density constraint: S_mn/(595×630) ≤ 0.9
Some component overlap remains in the final layout. The objective function minimises wire length — which pulls components together — conflicting with the density constraint. SA balances both goals but cannot perfectly satisfy them simultaneously. This is an inherent trade-off acknowledged by the paper.
S′mn = overlap of group i's bbox with cell [m,n]
Key result: Try "Center-clustered" — center glows hottest, matching the paper's exact heatmap. SA (Panel 4) pulls components to center → more wires there.
Scale: Paper uses 213 groups × 3,840 cells = 817,920 calculations in MATLAB.
Grid density (Panel 4) measures component crowding — is there physical space? Wiring density (this panel) measures wire crowding — can all signals fit through? Both are required for a manufacturable chip layout.
Level 1 — per group:gρᵢ = (Lᵢ × WIDᵢ) / (Hᵢ × Wᵢ)
Wire area as fraction of bounding box.
Level 2 — per cell:ρ_mn = Σ gρᵢ × S′mn
Sum over all groups overlapping cell [m,n].
Wire width varies → standardise to uniform width.
Multi-layer chips → minimise layers (acknowledged limitation).
Empty bounding box areas → the group-level formula weights only the wired region correctly.
SA (Problem 2) minimises wire length by pulling components toward the center. So most groups have bounding boxes centered on the chip. This concentrates wiring density there — producing the characteristic hot-center heatmap that matches the paper's actual MATLAB output.