Macro Placement on the IBM/ICCAD04 Benchmarks

Adam Holmes · code on GitHub

A chip is millions of tiny logic cells plus a few hundred big fixed blocks — memory units and other prebuilt components. Macro placement is deciding where those blocks go, and it largely sets how good the finished chip is. This is my solver for a benchmark challenge that grades each placement with one number — mostly wirelength, plus density and routing congestion; lower is better, no blocks may overlap. Each animation replays one complete run: the reference placement the benchmark comes with (left), my placer working (middle) — spreading, legalizing, then improving — and the score per frame (right; dashed line = reference). Blocks are rectangles, cell clusters are dots.

Result. Starting from random placements, with one hour per benchmark, my placer averages 0.9758 across all 17 — 34% below the provided reference placements (avg 1.477; the RePlAce academic tool scores 1.458, simulated annealing 2.125) — beating the reference on every design with zero overlaps, verified on the official scorer. The hour is measured strictly: a hard wall clock covering everything, run on hardware slower than the competition machines — so the budget claim is conservative.

How it works

The score is 1.0·wirelength + 0.5·density + 0.5·congestion. The core idea is to combine a smooth global optimization of a differentiable proxy with simulated annealing using the full, non-differentiable loss — two optimization stages, with a legalization step in between, all scheduled into one hour:

• 1 · Gradient-based global placement (GPU). Treat every block's position as a free variable and run gradient descent on a smooth proxy of the proxy score (the real score isn't differentiable). It uses only wirelength and density; congestion is left out, because no differentiable congestion surrogate I built helped — even one that correlated 0.995 with the real thing. The two terms are scheduled: wirelength first, which pulls connected blocks into a clump, then density ramps in and pushes them apart. That's the bunching-then-spreading in the animations above, and it avoids the traps a full-strength objective falls into from step one. I tested the opposite schedule, spread-first, and this one won.
• 2 · Legalization. Push overlapping blocks apart until nothing overlaps, moving each as little as possible.
• 3 · Annealed local search on the exact score. Propose a small change, score it exactly, accept it by the standard annealing rule — ~1 ms per move on a fast reimplementation of the official scorer (validated to match it). Proposals move one cell, or a small cluster of neighbors together, and rather than being random they are mostly computed: the mathematically optimal spot for a cell given its wires, positions where wirelength provably doesn't change (so density and congestion improve for free), and route-shifts — nudging a wire's endpoint one grid cell so its whole route leaves a congested row or column. A small "temperature" accepts occasional score increases so these disruptions can pay off a few moves later. This stage does most of the work.
  
  The key point: the heuristics only decide where to look; acceptance always uses the real score. Proposals can be approximate, biased, even wrong — anything that doesn't help is simply rejected. That is how congestion improved without ever needing a congestion model good enough to optimize directly.
• The hour. Generate ~8 global placements (a tuned configuration, a few variants, one started from the reference), give each a quick improvement pass, keep the best two and improve them deeply — then spend all remaining time running 12 parallel annealed copies of the current best, keeping the winner, repeatedly until time runs out. Deep repeated improvement of one good placement beats collecting more placements.

The tuned configuration

About fifteen hyperparameters, tuned by Bayesian optimization on 3 designs (easy / medium / hard) and reported on all 17; the other 14 are held out. Configurations are always compared on paired random seeds, so I wasn't comparing lucky runs — single-seed differences are mostly luck.

The configuration search: score vs. trial. It plateaus once differences between good configurations fall below run-to-run noise.

What I learned

• Compare on identical seeds, decide on many. Run-to-run noise (~2%) is bigger than the gap between good configurations, so single-run rankings mostly measure luck. But collecting placements saturates after a few dozen — reallocating that time into deep repeated improvement of the single best placement is where most of the final margin came from.
• An apparent performance ceiling was really a budget ceiling. Scores stalled for a long time, and no clever mechanism moved them. The real limit was the number of local-search moves: the search simply hadn't converged, and deeper passes kept improving well past the point where I had been stopping.
• Annealing failed with random moves and became the engine with computed ones. With random-step proposals, accepting occasional score increases bought nothing. With computed proposals it became the core of the method: 87% of the final improvement came from congestion — the score term random single moves can never crack, because the congestion in a hot spot mostly comes from wires passing through it. The winning move relocates a passing wire (one-cell endpoint nudge → the whole route leaves), not the block that happens to sit there.
• It generalizes. The configuration tuned on 3 designs, applied unchanged to the other 14: held-out scores are within ~4% of tuning-design scores, and 16 of 17 beat the reference with no per-design adjustment. The remaining ~2.6% to the leaderboard leaders (~0.951) is concentrated on the most congestion-heavy designs, where my local search has converged — closing that gap would need a qualitatively different global arrangement, and how to find one is an open question.

Appendix — what didn't work

Each verdict comes from experiments run with identical random seeds in both arms, so noise cancels.

• A congestion term in the gradient stage. I built a differentiable congestion model that tracks the true metric closely (correlation 0.94–0.99) — and it still didn't help under any schedule. The local search already optimizes true congestion directly; a congestion term in the global stage only trades away wirelength. (A cruder standard model was worse: the optimizer learns to cheat it.)
• Evicting blocks from crowded spots. Moving the occupant of a congested cell to empty space fails — the long move stretches its own wires and gets rejected. The congestion is mostly through-traffic; see route-shifts above.
• Mixing the stages. Alternating gradient steps with local-search moves never beat running them in sequence: coarse arrangement first, fine detail second.
• Reordering mechanisms in the gradient stage. Gradient descent spreads blocks but rarely lets two cross past each other, so the random start largely fixes their left-to-right order. Four attempted fixes (temporary overlap tolerance, teleporting blocks toward their wires' centers, injected noise, annealed swaps) each improved the average run but never the best of many runs — they make runs converge to similar results, shrinking exactly the spread that picking-the-best feeds on.
• Also: an electrostatics-based density model — equivalent to the simpler overflow penalty used; resolving overlap inside the loss instead of a separate legalization step — over-spreads the layout; moving the big fixed blocks or flipping their orientation — the score barely responds (~0.2%).