Placement as an Optimisation Problem

This is the first article of Module 4, and it starts with a question that trips people up the first time they reach placement: what does it even mean for a placement to be right? Floorplanning had checkable answers. A core is either big enough or it is not. A pin is either on the north edge or it is not. Placement does not work like that. Hand two engineers the same floorplan and the same netlist and you get back two different placements, both perfectly legal, and neither one is wrong.

If you come from digital logic, where correctness is binary, that should feel uncomfortable. Placement lives in the world of optimisation, where the question is not “is this correct” but “how good is this compared with the alternatives”.

The objective, stated precisely

After synthesis the netlist is pure topology: a graph of standard cell instances and the nets joining their pins. There is no left or right, no coordinates, nothing physical about it. Floorplanning gave you a canvas, with a core area, standard cell rows, power straps and maybe a macro or two already sitting down. Global placement takes every one of those thousands of floating cell instances and gives each an (x, y) on that canvas.

The objective almost every placer optimises is this: minimise total wirelength, subject to every cell sitting inside the core and no region being packed more densely than the density limit allows. That is the whole problem statement. The difficulty is entirely in how you search an enormous space of candidate positions for something close to the minimum without breaking the constraints. A few thousand cells already have more possible arrangements than anything you could enumerate.

Real wire routes do not exist yet at placement time, so placers use a cheap proxy for wirelength called half-perimeter wirelength, or HPWL. Draw the smallest bounding box around every pin on a net, and the estimated length of that net is half the box’s perimeter.

$$\text{HPWL} = (x_{\max} - x_{\min}) + (y_{\max} - y_{\min})$$

It underestimates the real routed length, because real wires bend around obstacles. It is also cheap to compute for every net on every iteration, thousands of times over, which is exactly what an optimiser needs.

Computing it by hand

Take four tiny cells, one slice of a small pipeline, A feeding B feeding C feeding D, joined by three nets: net1 (A to B), net2 (B to C), net3 (C to D). Here are two candidate placements on an integer grid. Treat the units as routing tracks.

Placement 1, cells laid out in netlist order:

Placement 2, cells laid out out of order:

All cells sit at y = 0, so every net’s HPWL collapses to its x-span:

Same four cells, same netlist, same grid, and Placement 2 costs twice the wirelength of Placement 1 purely from cell order. That is the point of this article made concrete: placement quality is a number, and the number moves with decisions the placer makes.

Placement 1 works because the physical order of the cells along the row happens to match the logical order of the connections. That alignment is what a wirelength-minimising placer is hunting for. Real netlists are not clean chains, though. One cell can fan out to a dozen others, and there is no single physical ordering that suits every one of those connections at once. That tension is the next article.

One thing worth being clear about before moving on: “no overlapping cells” does not mean a placement is done or good. Legality (no overlaps, cells on real rows) and quality (low wirelength, low congestion) are separate properties. A placement can be perfectly legal and still terrible. During global placement, cells are in fact allowed to overlap for a while, because forcing legality too early gets in the way of finding a good arrangement first.

Practice Exercise

Three cells X, Y and Z, connected by two nets: netA joins X and Y, netB joins Y and Z. Two candidate placements:

Placement 1: X = (0,0), Y = (2,0), Z = (2,3) Placement 2: X = (0,0), Y = (0,3), Z = (2,3)

Compute the total HPWL for each. Which would a wirelength-minimising placer prefer?

Minimising total wirelength sounds like an unambiguous good. The next article breaks that assumption: wirelength, routing congestion and timing are three separate objectives, and pulling hard on one can make the other two worse.