Stockmeyer's Shape-Curve Algorithm
The idea
Fix the slicing topology and ask a narrower question: each hard block can be placed as W x H or rotated to H x W, so which combination of orientations minimizes the chip's bounding box? There are 2 to the power of the block count combinations, but Stockmeyer showed the optimum is computable exactly in polynomial time.
The tool is the shape curve: for each subtree, the set of non-dominated (width, height) pairs it can realize, kept as a staircase sorted by width. A leaf's curve has at most two points, one per orientation. An internal node's curve is built by combining its children's, point by point. Take one point (w1, h1) from one child curve and (w2, h2) from the other; the combined dimensions depend only on the cut direction:
| cut | combined width | combined height |
|---|---|---|
| V (subtrees side by side) | w1 + w2 | max(h1, h2) |
| H (subtrees stacked) | max(w1, w2) | h1 + h2 |
The two rules are the same relation with width and height exchanged: a vertical cut adds the widths and lets the taller subtree set the height, and a horizontal cut does the reverse.
The combined points are computed over all pairs of child points, and dominated points (some other point is no wider and no taller) are discarded, so each node's curve stays a short staircase. Merging two staircases is linear in their size. At the root, pick the point of least area and walk back down the tree, reading off which child choices produced it.
The recipe
Step 1 (leaf curves). Give each block a shape curve: its orientations as (width, height) points.
Step 2 (merge up). At each internal node, combine the two child curves with the V or H rule above, over all pairs of points, and drop dominated points. Propagate to the root.
Step 3 (pick). At the root curve, choose the point of least area (or the best point that fits the target die).
Step 4 (trace back). Walk down the tree, and at each node read off which child options produced the chosen point, giving every block's orientation.
Watch it work: merging shape curves
Two rotatable blocks combined at a vertical cut. The walkthrough plots each block's shape curve, merges them by the V rule (width adds, height takes the maximum), discards the dominated point, forms the staircase, and traces the minimum-area point back to the block orientations that achieve it.
Pros, cons, and the trade-off
Strengths
- Exact and polynomial: the optimal orientation and sizing, with no heuristic and no tuning, from a linear-time merge per node.
- Handles soft blocks: a soft block's curve is a piecewise hyperbola sampled into a staircase, so flexible aspect ratios are sized exactly too.
- Composes with search: an annealer explores topologies while this merge sizes each candidate optimally.
Weaknesses
- Slicing only: the dynamic program depends on the binary, single-cut structure of a slicing tree.
- Sizing, not placement: it chooses orientations for a fixed topology; it does not decide the topology itself.
- Staircase growth: soft-block curves sampled finely make the staircases longer, trading accuracy for merge cost.
The trade-off
Stockmeyer's algorithm is one of the few physical-design problems that is simply solved: given a slicing topology, the optimal orientation and sizing follow exactly in polynomial time. The condition is the whole point. For non-slicing floorplans the same orientation problem is NP-hard, so the guillotine structure is not just convenient, it is what makes the dynamic program compose at all.
Is it actually used today?
The evidence for Stockmeyer's algorithm is inside slicing-based floorplanning and in teaching.
- Slicing floorplanners: the sizing engine inside every slicing-based floorplanner, run for each candidate topology the search proposes.
- Soft-macro area estimation: fast, exact area and aspect-ratio estimates for flexible blocks.
- Teaching: the canonical example of dynamic programming on trees in physical design.