Cut-Based Mapping with Priority Cuts

The idea

Instead of splitting the network into trees, cut-based mapping works on the entire directed acyclic graph. A cut of a node is a set of nodes that separates it from the primary inputs. A small cut, a handful of inputs, defines a local function that a single library cell might implement.

Enumerating every cut explodes on large designs, so priority cuts (Mishchenko, Cho, Chatterjee and Brayton, 2007) keep only the best few cuts at each node, ranked by delay and then area, and build each node's cuts from the kept cuts of its fanins. Mapping then runs in passes. The first pass picks, at every node, the cut and matching cell that give the earliest arrival time, which fixes the best delay the structure can reach. Later passes revisit the nodes that are not on the critical path and choose cheaper cuts wherever their slack allows. This is area recovery, guided by area flow (a node's area shared among its fanouts) and by the exact area a choice adds locally.

Watch it work: delay first, then area recovery

A small network with one shared node and two outputs. The walkthrough enumerates the cuts, maps every node for the earliest arrival, then recovers area within a timing budget, and shows why tree covering could not reach the fast answer here.

The fine print

Keeping only a few cuts per node is a heuristic: a cut dropped early might have led to a better mapping. Area recovery is heuristic too. Mapping on one fixed structure inherits that structure's limits, which is why mapping with structural choices keeps several equivalent structures for the mapper to choose among.

Where you meet it today

Cut-based mapping drives ABC's modern mappers, including &nf, the standard-cell mapper that the OpenROAD flow's synthesis script runs after each round of rewriting.