TL;DR
This paper tackles the "macro legalization" problem in microchip design—the challenge of shifting large circuit components (macros) from an initial overlapping layout into a legal, grid-aligned configuration. The authors propose a Mixed-Integer Programming (MIP) framework and a "Flexible Greedy" heuristic that successfully scales to handle over 1,000 macros while minimizing the total displacement from the original design.
What Problem Does This Paper Address?
In modern VLSI (Very Large Scale Integration) design, chips are composed of millions of standard cells and larger "black-box" components called macros. Initial automated placement often results in "non-physical" layouts where macros overlap or violate complex spacing rules.
The "Legalization" step is the process of moving these macros as little as possible to satisfy three main constraints:
- Non-overlap: No two macros can occupy the same space.
- Spacing Rules: Macros must be separated by either an exact small distance ($b$) or a significantly larger minimum distance ($c$).
- Grid Alignment: The lower-left corner of every macro must sit on a specific coordinate grid.
Because this is a variation of the rectangle packing problem, it is NP-hard. The challenge, set by Synopsys for the 2022 Study Group Mathematics with Industry (SWI), was to find a "legal" placement for large-scale instances in under 30 minutes.
Methods
The authors explored four distinct algorithmic approaches:
- Mixed-Integer Programming (MIP): An exact mathematical model using "Big-M" constraints to handle the "either/or" nature of the spacing rules. While it guarantees an optimal solution (minimizing $L_1$ displacement), it becomes computationally intractable as the number of macros grows.
- Greedy Algorithm: Macros are placed one by one in a fixed order. Each macro is placed as close as possible to its original position without overlapping previously placed ones. This is fast but often fails to find a feasible solution for the final macros because it lacks "look-ahead" or the ability to shift earlier macros.
- Flexible Greedy Algorithm (The Standout): A hybrid approach. Like the greedy method, it adds macros one by one. However, instead of fixing a macro's position forever, it allows previously placed macros to shift slightly. By fixing the relative positions (the integer variables in the MIP) but leaving the exact coordinates as continuous variables, the problem remains a solvable Linear Program (LP) at each step.
- Brownian Motion (Heuristic): A proposed probabilistic approach where "illegal" macros perform random walks (jiggling) to find open space, with the "jiggle" intensity inversely proportional to the macro's size.
Datasets
The study used nine benchmark instances provided by Synopsys (labeled instance101 through instance109).
- Scale: The instances ranged from a tiny test case of 13 macros (
instance106) to a massive production-scale problem with 1,171 macros (instance109). - Complexity: These datasets included "blockages" (fixed areas where no macros can go) and "keep-out margins" (extra buffers around specific macros).
Key Insights and Ideas
- The Spacing "Gap": The rule requiring a distance of exactly $b$ or at least $c$ creates a non-convex solution space. This makes the problem much harder than standard non-overlap constraints, as a macro can't simply "slide" continuously; it must "jump" over the forbidden zone between $b$ and $c$.
- Ordering is Everything: In greedy approaches, the sequence in which you place macros drastically changes the outcome. Placing macros based on their distance from the origin often led to "dead ends" at the chip borders, whereas placing larger macros (by perimeter) first tended to produce more feasible (though less optimal) results.
- Flexibility Prevents Deadlocks: The "Flexible Greedy" method's success highlights that in dense chip designs, you cannot afford to be rigid. Allowing small, ripple-effect shifts in already-placed components is essential to "making room" for the final pieces of the puzzle.
Key Results
The researchers compared the $L_1$ error (total distance moved) across their implemented algorithms:
| Instance | # Macros | MIP ($L_1$ error) | Greedy | Flexible Greedy |
|---|---|---|---|---|
| instance101 | 59 | 134.70 | 10566.39 | 165.65 |
| instance104 | 100 | 704.15 | 2379.79 | 771.49 |
| instance109 | 1171 | - | - | 26484.18 |
- MIP was the champion for small instances (up to ~100 macros) but failed to produce any solution for larger ones within the time limit.
- Greedy was fast but frequently failed to find a feasible solution (indicated by dashes in the table) or produced massive displacement.
- Flexible Greedy was the most robust, successfully legalizing the 1,171-macro instance where all other methods failed.
Limitations and Future Work
- Grid Relaxation: To simplify the problem, the authors relaxed the discrete grid constraints in their implementation, allowing macros to sit at continuous coordinates. Real-world applications would require a final "snapping" phase to align with the manufacturing grid.
- Brownian Motion Implementation: Due to time constraints at the SWI workshop, the Brownian motion algorithm was designed but not implemented. The authors suggest this probabilistic "simulated annealing" style approach holds potential for escaping local optima.
- Python Performance: The algorithms were implemented in Python. The authors note that moving to a lower-level language like C++ would significantly speed up the MIP solver calls, potentially allowing for more iterations or larger flexible windows.
Summary updated