Legalization and Detailed Placement

Global placement leaves cells overlapping and between rows. Legalization moves every cell to a legal position: inside a row, aligned to a site, with no overlaps and in the correct orientation. Detailed placement then improves the legal placement locally, by swapping and shifting cells to shorten wires. This article shows what OpenROAD's detailed placer does to the 16x16 multiplier, how far it moves the cells, and what that costs in wire length.

7 min read | Intermediate

What You'll Learn

• List the rules a legal placement must follow
• Read the displacement report of the detailed placer
• Explain why legalization increases wire length
• Run the detailed placement improvement steps in OpenROAD

What Legal Means

After global placement, cells sit at any position, overlap each other and straddle row boundaries (left). A legal placement (right) satisfies:

• Every cell sits inside a row, with its bottom edge on the row's bottom edge.
• Every cell starts on a site boundary: a multiple of 0.46 um from the row's start in sky130 hd.
• No two cells overlap, and no cell overlaps a fixed cell such as a tap cell or a macro.
• Every cell has the row's orientation, so its power pins line up with the rails: N in one row, flipped (FS) in the next.
• Library-specific rules hold, such as minimum spacing between certain cell types or keeping cells out of blockages.

Legalization in OpenROAD

The lab's flow runs detailed_placement right after repair_design. Its first line states how far a cell may move:

[INFO DPL-0005] Max displacement: +/- 500 sites horizontally, +/- 100 rows vertically.

It then moves each cell to a nearby free legal position and reports the result:

Movements Summary
---------------------------------------
Total cells:                    1267
Diamond Move Success:           1267 (100.00%)
Total Placement Failures:          0
---------------------------------------
Placement Analysis
---------------------------------
total displacement       2336.8 u
average displacement        1.5 u
max displacement            7.7 u
original HPWL           20324.1 u
legalized HPWL          22402.7 u
delta HPWL                   10 %

The "diamond move" is the search pattern: the placer looks for a free position in a growing diamond around the cell's global position and takes the nearest one that fits. All 1,267 movable cells found a place this way. The tap cells are fixed and do not move.

Each red line runs from a cell's position after global placement to its legal site. Most moves are short, a site or two sideways or half a row up or down. The average is 1.5 um, about half a row height, and the largest 7.7 um.

The Cost: Longer Wires

Every move takes a cell away from the position the global placer found best, so the HPWL rises, here by 10 %. How much depends on how crowded the global placement left the core. The same design at three target densities:

The denser the global placement, the less free space there is near each cell, the further cells must move and the more of the global placer's gain is lost. At 0.9 legalization cancelled most of the advantage over 0.7: 19.3 mm against 19.7 mm.

Legalization Again Later

Every later step that adds or resizes cells breaks the legal placement in places: clock tree synthesis inserts clock buffers, and timing repair inserts buffers and upsizes gates. The lab's flow therefore runs detailed_placement a second time after CTS and setup repair. That run moves far less:

Total cells:                    1283
total displacement        100.0 u
average displacement        0.1 u
max displacement            6.8 u
delta HPWL                    0 %

The 16 cells added by CTS and repair were placed, and only their neighbours had to make room.

Improving a Legal Placement

Legalization only makes the placement legal; it does not try to win back the wire length it cost. OpenROAD has two more commands for that, which the lab's flow runs only when the PRO Detail Opt option is set:

detailed_placement
improve_placement
optimize_mirroring

improve_placement runs a series of local moves on the legal placement, each keeping it legal: matching groups of interchangeable cells, swapping cells across the core and between rows, reordering cells within a row, random moves, and flipping cells. The log reports each step on the multiplier:

[INFO DPL-0302] End of matching; objective is 2.239755e+07, improvement is 0.08 percent.
[INFO DPL-0307] End of global swaps; objective is 2.172734e+07, improvement is 2.99 percent.
[INFO DPL-0309] End of vertical swaps; objective is 2.163573e+07, improvement is 0.42 percent.
[INFO DPL-0305] End of reordering; objective is 2.162946e+07, improvement is 0.03 percent.
[INFO DPL-0328] End of random improver; improvement is 0.743098 percent.
[INFO DPL-0383] Performed 374 cell flips.
[INFO DPL-0384] End of flipping; objective is 2.086180e+07, improvement is 2.83 percent.
Original HPWL            22402.7 u
Final HPWL               20843.9 u
Delta HPWL                  -7.0 %

The global swaps and the cell flips did most of the work. Flipping mirrors a cell left to right, which keeps it legal and moves its pins to the other side, closer to the cells they connect to. optimize_mirroring then mirrored 57 more cells for another 0.1 %.

Together they won back 7 % of HPWL, most of the 10 % that legalization cost. After routing, the multiplier had 27.6 mm of signal wire instead of 28.3 mm, and the worst slack at 10 ns improved from +0.58 to +0.62 ns.

Running It in ChipVerify Lab

Run Place and Route on the multiplier and find the two "Movements Summary" blocks in the log. Compare the displacement and the HPWL change of the first and the second detailed placement. Run again at a different utilization and see how the numbers of the first one change. With PRO, set the Detail Opt option, which runs improve_placement and optimize_mirroring after each detailed placement: on the multiplier at 40 %, the first run won back 7.4 % of HPWL, the routed signal wire fell from 27.9 to 26.7 mm, and the worst slack at 10 ns rose from +0.13 to +0.23 ns.

Common Mistakes