Macro Placement Optimization Challenge
Bayesian optimization and adaptive local search on top of DREAMPlace, cutting proxy placement cost 16% versus RePlace with a 1000× faster per-move evaluator.
- 16% vs RePlace
- Proxy-cost reduction
- 1000×
- Eval speedup
- +3.2%
- LNS improvement
The problem
Macro placement — deciding where large blocks go on a chip before the rest of placement runs — has a huge, non-convex search space, and the standard academic baseline (RePlace) leaves real room on the table across wirelength, congestion, and density. The challenge isn’t just finding a better placement for one benchmark; it’s finding a strategy that generalizes across benchmarks without overfitting to whichever one you tuned on.
Approach
The core placer is DREAMPlace, tuned via Bayesian optimization (Optuna) rather than hand-picked hyperparameters. To keep the hyperparameter strategy from overfitting to a single benchmark, a k-means clustering step groups benchmarks by characteristics first, so hyperparameter choices generalize across a cluster instead of chasing one instance. On top of the placer, an adaptive Large Neighborhood Search (LNS) with multiple destroy/repair operators handles local refinement after the initial placement.
What broke
LNS’s local search needs to evaluate many candidate moves, and the naive per-move cost evaluation — recomputing wirelength, congestion, and density from scratch — took 1.3 seconds per move. At that cost, large-scale local search simply isn’t tractable. Building an incremental cost evaluator that updates only what changed after a move, instead of recomputing everything, cut that to 1–3 milliseconds: a 1000× speedup that’s what actually made the LNS phase usable at scale.
Results
| Metric | Result |
|---|---|
| Proxy cost vs. RePlace | −16% (wirelength, congestion, density combined) |
| Per-move evaluation | 1.3s → 1–3ms (incremental evaluator) |
| Adaptive LNS refinement | +3.2% over the placer’s initial result |
What I’d do differently
Pending — this project’s retrospective wasn’t in the source material this case study was drafted from. Krithik: what would you change if you did this again?