Van Ginneken Buffer Insertion

The idea

Long wires are quadratically slow (double the length, quadruple the Elmore delay), and the cure is buffering: break the wire into segments each driven afresh. Where exactly to break is an optimization with an exponential-looking choice space, and van Ginneken solved it exactly with a dynamic program of striking economy. Walk the routed tree from the sinks toward the driver. At every point carry a set of candidates, pairs (C, Q): the downstream capacitance this subtree presents, and the required arrival time achievable at this point given the buffering decisions below. Wire segments transform candidates (capacitance grows, required time degrades by Elmore terms); at a legal buffer site, each candidate spawns an alternative where a buffer is inserted (capacitance resets to the buffer's input capacitance, required time pays the buffer delay); at merges, candidate sets combine. The key to tractability: prune dominated candidates, any pair worse in both coordinates than a rival dies. The surviving frontier stays small (linear in sites for the classic case), and at the driver the best candidate, unwound, is the provably optimal buffering: quadratic time in the original formulation, later sharpened to near-linear.

Extensions

Lillis and colleagues folded in buffer sizing from a discrete library and inverting buffers with polarity tracking; later work added slew and cost constraints and wire sizing. The candidate-propagation- with-pruning pattern generalized into a small industry of layout optimizations.

Where you meet it today

Buffering is a dominant fraction of cell count on modern chips, and every physical-synthesis engine's repair-timing step (OpenROAD's resizer included) runs recognizable descendants of this dynamic program over its nets.