Technology Mapping: Covering a Boolean Network With Library Cells

Technology-independent optimization leaves a network of abstract gates: two-input ANDs, ORs, inverters, maybe an exclusive-OR. The library, by contrast, contains NAND2 at four drive strengths, a three-input AND-OR-invert cell, a multiplexer, a scan flip-flop, and a few hundred others, each with characterized area, power, and delay as a function of the load it drives. Mapping is the step that replaces the abstract network with a selection of those cells, and its output is the netlist that timing analysis, place and route, and the power tool will all consume.

The problem sounds like a lookup, and the first half of the job is a combinatorial optimization with a clean formulation. The second half is a fixed point: the delay of a cell depends on the load it drives, the load depends on which cells were chosen downstream, and the choice depends on the delay. Mapping tools therefore alternate between choosing cells and computing the loads they imply.

Subject graph, pattern graphs, and covering

The abstract network is converted into a subject graph in a canonical basis, usually two-input NANDs and inverters, because every boolean function can be decomposed into that basis and because a canonical basis makes pattern matching uniform. Each cell in the library is decomposed into the same basis to form a pattern graph: a two-input NAND cell becomes a single NAND node, a three-input AND-OR-invert becomes a small subgraph of NANDs and inverters representing the function it computes.

Mapping then searches for a set of pattern graphs whose union covers the subject graph, meaning every node of the subject graph is covered by at least one chosen pattern, with a cost function over area, delay, or both. For a tree-shaped subject graph the search is a dynamic program: process nodes from the inputs upward, and for each node record the cheapest way to cover the subgraph rooted there. Each possible match of a library pattern at that node gives a candidate cost, and the cost includes the covers already computed for the pattern’s leaf nodes. The recurrence is

cost(node) = min over patterns p matching at node:
                 cost(p) + sum over leaves l of p: cost(l)

For a general directed acyclic graph the covering problem is harder, because a node can have several consumers and the covers chosen for them interact. Tools handle this by cutting the network into trees at nodes with multiple fanout, mapping each tree, then resolving the boundaries; the result is not provably optimal for the whole graph, which is acceptable because the cost models are approximate anyway.

Boolean matching, not just shape matching

Structural matching compares the pattern’s shape to the subject graph’s shape and is fast but limited to cells the decomposition happens to produce. A cell whose function can be implemented in several ways, such as a multiplexer or an exclusive-OR, is better handled by boolean matching: test whether the cell’s function equals the local function under some assignment of cell inputs to network variables, allowing input inversions and permutations.

That test is where satisfiability and canonical-form techniques enter synthesis. Two functions are equal for all inputs if their canonical representations are identical, or if the exclusive-OR of the two is unsatisfiable. The class of functions for which a compact canonical form exists is limited, but general SAT-based equality checking handles the rest, and it is a natural use of the same engines that verification uses.

The payoff for allowing boolean matching is that compound cells become mappable. A three-input AND-OR-invert cell computes $\overline{a \cdot b + c}$ in a single stage: for a sum-of-products function, an AOI cell replaces what would otherwise be an AND stage feeding an OR stage, removing one level from the path. The same cell is six transistors, three nMOS and three pMOS, against the ten transistors of a two-input AND (a NAND2 plus an inverter) feeding a NOR2, so it is both smaller and faster because it removes a stage’s parasitics as well as the stage itself.

Delay is a function of two variables, so mapping iterates

A cell’s delay is characterized as a two-dimensional table indexed by the input transition time and the output load capacitance; this is the standard nonlinear delay model used by every library format in wide use. The delay of a net also depends on the resistance and capacitance of the wires, which place and route has not yet determined, so synthesis uses estimated wire loads derived from fanout and a statistical wire-load model.

The circularity is unavoidable in this order of operations. A mapper that assumed minimum-size cells would compute loads too small and pick cells that are too weak; a mapper that assumed worst-case loads would oversize everything and burn area and power. Production flows therefore iterate: map with estimated loads, compute the resulting loads and slacks, resize drivers and insert buffers where slack is negative, re-map the regions whose structure changed, and repeat until the estimates stop moving. Each round is cheap relative to placement, and the loop usually terminates in a handful of iterations because the estimates converge.

The delay cost used at each node is the arrival time at that node, propagated from the primary inputs. Choosing the pattern with the smallest local delay is not optimal for the whole network: a pattern with more leaves moves the critical boundary inward, and the correct formulation accounts for the arrival times of the leaves. This is why the dynamic program’s recurrence takes leaf costs as inputs rather than treating the pattern in isolation.

Limits that force structure into the netlist

Three library constraints are checked after mapping and repaired by inserting cells that implement no logic at all.

Maximum fanout. A library specifies, per cell and per drive strength, the largest number of inputs its output may drive. Exceeding it degrades the output transition time, which increases the delay of every cell it feeds, not just one. The fix is to insert a buffer tree: the driving cell’s load becomes the buffers’ inputs, and the buffers fan out to the original consumers.

Maximum transition time. Slew degrades on a heavily loaded net for the same reason. Libraries specify an upper bound because a slow input transition increases a receiving cell’s delay and because the delay tables are only characterized over a bounded slew range; beyond it the model is extrapolation.

Maximum capacitance. Some libraries constrain the total capacitive load on a net, which is a restatement of the fanout limit in electrical units.

Buffer insertion is a size-and-count optimization, not just a repair. For driving a load that is much larger than the driver’s own input capacitance, a chain of buffers has lower total delay than one oversized driver, because delay through a chain with per-stage fanout $f$ grows linearly in the number of stages while the load it can drive grows as $f^{N}$. Minimizing total delay over $N$ stages gives the classic result that each stage should have fanout $e \approx 2.7$, so the optimum number of stages is about $\ln(C_{load}/C_{in})$. Driving a load that is a hundred times the input capacitance therefore wants roughly five stages, not one. Logical effort extends the same reasoning to gates of different topologies by assigning each gate a ratio of its input capacitance to that of an inverter delivering the same current.

What the mapped netlist does not contain

Mapping produces gates, and nothing else. It has no notion of where the cells will sit, so the netlist at this point has no real wire delays; the timing report from this stage is an estimate, and the sign of its errors is not predictable. Clocks are still ideal: no clock tree exists, so clock skew and insertion delay are not yet in the timing picture, which means the slack numbers from a post-synthesis report are optimistic on setup and unreliable on hold. See static timing analysis of the mapped netlist for which of those numbers survive into the final sign-off.

Mapping also cannot recover a design from bad RTL. If the synthesized logic has a long dependency chain, mapping can only choose the fastest cells along it; it cannot restructure the chain. The structural remedies, which are adding pipeline registers, splitting wide operations, and changing the state encoding described in state encoding and next-state logic, are source-level decisions that mapping inherits rather than fixes.