Legalising a Global Placement

Section 4.2 starts from the iteration-48 density grid at the end of the previous article. Every bin is close to target, so by RePlAce’s own cost function that is a good, settled placement. And yet if you streamed it straight to GDS and sent it to a fab, it would be nonsense. Cells sit at coordinates like x = 14.37 um. Two cells might overlap by a fraction of a micron. Nothing is snapped to an actual standard cell row.

That is not a bug in RePlAce. It is a deliberate choice. Treating cell positions as continuous, real-valued numbers rather than discrete row and site slots is exactly what lets the force-directed optimiser move cells smoothly, a tiny step at a time, and settle cleanly. If every cell had to snap to a legal site on every iteration, the optimiser would be stuck making large, disruptive jumps instead of the small adjustments that let it converge. Global placement optimises for quality first and openly defers legality to a second, focused step.

That second step is legalisation, done inside OpenROAD by its detailed placement engine, OpenDP.

What a legaliser actually does

Two jobs, and only two. First, snap every cell onto a real standard cell row at a real, valid site: the row grid and site grid set up back in Module 3’s floorplan. There is no such thing as a cell sitting between two rows or between two sites in the final layout. Second, resolve every overlap, moving cells apart just enough that no two occupy the same sites, while disturbing RePlAce’s carefully optimised arrangement as little as possible.

That second point is the whole art of legalisation. A legaliser that ignored quality could resolve every overlap trivially by spreading all the cells out with huge gaps. A good legaliser treats it as its own optimisation: minimise total cell displacement, or a weighted mix of displacement and the wirelength increase it causes, subject to the hard constraint that the result is fully legal. OpenDP’s algorithm is in the same family as the classic Abacus approach. Process cells roughly left to right and slot each one into the row and site that costs it, and its neighbours, the least additional movement.

Snapping a cell by hand

Here is the arithmetic legalisation does, one cell at a time. In sky130_fd_sc_hd the rows are 2.72 um tall and the site pitch is 0.46 um, both real published values. Suppose a cell’s global placement position came out at:

x = 41.18 um
y = 19.70 um

To legalise it, snap y to the nearest row boundary (a multiple of 2.72 um) and x to the nearest site boundary (a multiple of 0.46 um):

• Row index: 19.70 / 2.72 = 7.24, which rounds to row 7, so legal y = 7 x 2.72 = 19.04 um
• Site index: 41.18 / 0.46 = 89.5, which rounds to site 90 (or 89; a legaliser breaks ties by overlap with neighbours), so legal x = 90 x 0.46 = 41.40 um

So this cell moves from (41.18, 19.70) to (41.40, 19.04), a displacement of about 0.68 um, mostly vertical. That is a tiny, cheap move for one isolated cell. In a real run OpenDP is doing this for every cell in the design at once while resolving every overlap the snaps create, which is why it is a real optimisation pass and not a rounding function.

Two things worth knowing. The DEF that comes straight out of global placement is an intermediate artefact, not something to hand to routing or treat as a finished layout. Open it in a viewer before legalisation and you will see cells overlapping and off the row grid, which is expected. And a well-behaved global placement should need only small legalisation moves, on average a small fraction of a row height or a few site widths per cell. If legalisation reports large average displacement, global placement did not converge well. Legalisation cannot fix a badly converged global placement. It can only clean up the small remaining slop.

Practice Exercise

A different cell comes out of global placement at x = 8.05 um, y = 13.10 um, on the same hd row height (2.72 um) and site pitch (0.46 um). Compute its legalised position.

Legalisation gets every cell onto a valid row and site, but valid does not mean optimal. The next article looks at a second layer of fine tuning that detailed placement does on top of legalisation: flipping cells to align pins, and the row orientation scheme that lets neighbouring rows share power rails.