Logic Synthesis and Technology Mapping
Nobody places two billion gates by hand. You write RTL; a tool called a logic
synthesizer turns it into a netlist — a list of actual library gates and the
wires between them. Synthesis is the hardware world's compiler, and like a compiler it is not a dumb
translator: it optimises, aggressively, and the netlist it emits may look nothing like the
code you wrote while computing exactly the same function. Whether you are heading for an
FPGA or an ASIC,
this is the moment your design stops being text and starts being circuitry. The whole show runs in
three acts: elaborate, optimise, map.
Act I — Elaboration: from RTL to a generic circuit
Elaboration parses the RTL and builds a technology-independent circuit out of idealised
components. Every always_ff becomes registers; every + becomes an adder;
every if/case becomes multiplexers steering data. Consider:
always_comb begin
if (sel) y = a + b; // an adder…
else y = a - b; // …a subtractor…
end // …and a 2:1 mux on y, selected by sel
No gates yet, no delays — just an honest circuit diagram of your intent: generic adders, muxes,
registers, and clouds of Boolean logic. Getting this structural picture right is your job as
the RTL author; everything after this point is the tool's.
Act II — Logic optimisation: Boolean minimisation at scale
The generic circuit is bloated, so the tool now rewrites it into a smaller equivalent one. You already
know the hand tool for this:
Karnaugh maps minimise a
function of four or five variables by eye. Synthesis needs the same idea for functions of
hundreds of variables, and the lineage runs straight from your K-maps: the
Quine–McCluskey algorithm mechanised the K-map (find all prime implicants, then cover
the minterms); Espresso (Berkeley, 1980s) replaced exact covering with fast
heuristics that handle industrial-scale two-level logic; and modern tools rewrite the circuit as an
AIG — an and-inverter graph, everything expressed in 2-input ANDs and inverters —
and apply thousands of small local rewrites that each shave a node or a level. Along the way come the
classic clean-ups:
- constant propagation — a signal tied to 0 or 1 collapses everything it touches
(
x & 0 = 0, x & 1 = x), and the collapse cascades;
- dead-logic removal — any gate whose output can never affect an output of the
design is deleted, along with everything that only fed it;
- sharing — two places computing the same subexpression get one copy of the
hardware;
- retiming (a preview) — registers can legally slide through logic to balance path
lengths; the timing lessons ahead make heavy use of this.
What goes in, what comes out
Synthesis reads three things and writes two. In: your RTL; your
constraints (an .sdc file: the clock period, input/output delays — the
performance contract, which gets its own lesson soon); and the liberty library
(.lib) — the foundry's menu of standard cells, each characterised for area, delay as a
function of load, and power. Out: the gate-level netlist, plus
reports telling you whether the result meets the contract.
Act III — Technology mapping: covering logic with real cells
The optimised AIG is still made of idealised ANDs and inverters. The foundry does not sell those; it
sells a menu of a few hundred standard cells — NAND2, NOR3,
AOI21 (and-or-invert: \overline{ab + c}), XOR2,
and a family of DFF variants (with reset, with enable, with scan), each in several
drive strengths. Technology mapping is a pattern-matching / covering
problem: tile the logic graph with patterns from the menu so every node is covered, choosing the
tiling that minimises area (or delay, or power). One clever AOI21 can swallow what would otherwise be
three separate gates; a chain on the critical path gets fast, high-drive cells while a lazy status bit
gets the tiniest ones.
This is why the same RTL yields different netlists under different constraints. Ask
for low area and the mapper builds your adder as a compact ripple-carry chain of small cells; demand a
short clock period and it spends area on a parallel-prefix adder and big drivers. The RTL states
what; the constraints negotiate how.
A pocket optimiser you can run
Here is the heart of Act II in fifty lines: Quine–McCluskey prime-implicant generation plus a greedy
cover, run on a 3-variable function. Watch the literal and gate counts collapse — then try your own
minterm list.
// Quine–McCluskey, pocket edition: minimise f(a,b,c) given by its minterms.
const NVARS = 3;
const minterms = [1, 3, 5, 6, 7]; // f = 1 exactly on these inputs
const toBits = (m: number) => m.toString(2).padStart(NVARS, "0");
// Merge two implicants that differ in exactly one position ("010"+"011" -> "01-").
function merge(x: string, y: string): string | null {
let diff = 0, out = "";
for (let i = 0; i < NVARS; i++) {
if (x[i] === y[i]) out += x[i];
else { diff++; out += "-"; }
}
return diff === 1 ? out : null;
}
// Repeatedly merge until nothing merges; the survivors are the prime implicants.
let current: string[] = minterms.map(toBits);
const primes: string[] = [];
while (current.length > 0) {
const merged: string[] = [];
const used: boolean[] = current.map(() => false);
for (let i = 0; i < current.length; i++)
for (let j = i + 1; j < current.length; j++) {
const m = merge(current[i], current[j]);
if (m !== null) {
used[i] = true; used[j] = true;
if (merged.indexOf(m) < 0) merged.push(m);
}
}
for (let i = 0; i < current.length; i++)
if (!used[i] && primes.indexOf(current[i]) < 0) primes.push(current[i]);
current = merged;
}
const covers = (imp: string, m: number) => {
const bits = toBits(m);
for (let i = 0; i < NVARS; i++)
if (imp[i] !== "-" && imp[i] !== bits[i]) return false;
return true;
};
const show = (imp: string) => {
let s = "";
for (let i = 0; i < NVARS; i++)
if (imp[i] === "1") s += "abc"[i];
else if (imp[i] === "0") s += "abc"[i] + "'";
return s === "" ? "1" : s;
};
// Greedy cover: repeatedly take the prime covering the most uncovered minterms.
let uncovered = minterms.slice();
const chosen: string[] = [];
while (uncovered.length > 0) {
let best = primes[0], bestN = -1;
for (const p of primes) {
const n = uncovered.filter((m) => covers(p, m)).length;
if (n > bestN) { bestN = n; best = p; }
}
chosen.push(best);
uncovered = uncovered.filter((m) => !covers(best, m));
}
const litsBefore = minterms.length * NVARS;
const litsAfter = chosen.reduce((s, p) => s + p.split("").filter((c) => c !== "-").length, 0);
console.log("minterms: " + minterms.join(", "));
console.log("prime implicants: " + primes.map(show).join(", "));
console.log("chosen cover: f = " + chosen.map(show).join(" + "));
console.log("");
console.log("literals before (raw sum-of-minterms): " + litsBefore);
console.log("literals after: " + litsAfter);
console.log("gates before: " + minterms.length + " AND3 + 1 OR" + minterms.length);
console.log("gates after: " + chosen.filter((p) => show(p).length > 1).length + " AND + 1 OR" + chosen.length);
Five 3-input ANDs feeding a 5-input OR shrink to f = c + ab — the same
collapse a K-map would find, done blind by machinery that scales. Real optimisers add the AIG-rewrite
layer on top, but the flavour is exactly this: find redundancy, delete it, repeat.
- Elaborate: RTL → generic circuit (registers, adders, muxes, Boolean
clouds);
- Optimise: Boolean minimisation at scale — Quine–McCluskey → Espresso → AIG
rewriting — plus constant propagation, dead-logic removal and sharing;
- Map: cover the optimised logic with cells from the liberty library, trading
area against delay under your constraints;
- inputs: RTL + constraints (.sdc) + library (.lib); outputs: gate netlist + reports;
- the same RTL under different constraints yields different netlists.
Not with a K-map — a 100-variable function has 2^{100} minterms, more than
there are atoms in your body. Quine–McCluskey is exact but exponential; by the late 1970s IBM and
Berkeley needed to minimise the logic arrays inside real chips, and Robert Brayton's group answered
with Espresso (1984) — a heuristic that never enumerates minterms at all, instead
expanding, reducing and reshaping a set of cubes until no move helps. It was so much better than
anything before it that it simply became the field, and its successor mindset — local
rewrites on an and-inverter graph, embodied in Berkeley's open-source ABC — sits
inside essentially every commercial synthesizer today. When your million-gate design compiles in
minutes, you are riding forty years of "close enough, but fast".
The optimiser has no sentimentality. Logic with no observable effect on any output is deleted
— your carefully-written debug counter that nothing reads, the checksum register whose output pin got
dropped, the whole branch behind if (DEBUG) when DEBUG is a constant 0.
Gone, along with every gate that only fed it. Then the netlist viewer shows nothing, the simulator
shows nothing, and "why did my signal disappear?" becomes a rite of passage for every new engineer.
The tool is right: you asked for a circuit computing the outputs, and that logic computed none of
them. If you truly need a net to survive — for debug taps or lab probing — you must say so explicitly
(tools take keep/dont_touch attributes). Otherwise, trust the deletion: it
is the same ruthlessness that makes your chip small.