Technology Mapping

Technology-Independent Optimization produced a compact, multi-level network of generic AND/OR/NOT gates — still entirely abstract, with no relationship to any real, fabricable cell. This page covers the step that actually connects that network to the standard cell library: technology mapping.

The real problem: covering a network with library patterns

Technology mapping runs in three real phases: decomposition (breaking the network down into simple base structures), pattern matching (checking, at each point in the network, which library cells' logic function could realize that local structure), and covering (choosing an actual combination of matched cells that, together, correctly and efficiently implement the entire network). The genuinely hard part is covering: a library rarely has a cell whose function exactly matches every subnetwork encountered, and the same network can typically be covered several different ways — a large cell covering a bigger chunk, or a chain of smaller cells covering the same logic piece by piece — each choice trading off differently in area, delay, and power.

Why this problem is solved as a tree-covering problem, not a general graph one

Covering a general network — a directed acyclic graph, since real logic has shared subterms feeding multiple downstream points — with library patterns is an NP-hard problem in the general case, and stays NP-hard even under fairly restrictive conditions. Solved exactly, at real design scale, it's intractable. Real tools sidestep this rather than attempting it directly: they decompose the network into a forest of trees (breaking shared structure at reconvergence points), because covering a tree with tree-shaped patterns has an efficient, exact algorithm — a genuine, deliberate trade of some global optimality for tractability at real scale. Historical tools (DAGON among them) built on exactly this insight, matching against thousands of candidate library patterns per node while keeping the underlying covering step efficient by working tree-by-tree.

generic network (post technology-independent optimization)
                                                                library patterns available:
        ┌───┐                                                   ┌─────┐  ┌──────┐  ┌───────┐
   A ──►│AND│──┐    ┌───┐                                       │ AND2│  │ AND3 │  │ AOI21 │
   B ──►│   │  ├───►│OR │──► Y                match against ──► └─────┘  └──────┘  └───────┘
        └───┘  │    │   │                                        (2-in)   (3-in)   ((A·B)+C)
   C ──────────┘    └───┘

covering choice: one AOI21 cell covers the whole subnetwork in a single cell,
                  vs. an AND2 + OR2 pair covering the same logic in two cells —
                  different area/delay/power, same function

How "breaking shared structure at reconvergence points" actually works

Turning a DAG into a forest of trees isn't free — a node that fans out to multiple downstream trees can't just be assigned to one of them and ignored by the others, since every tree that uses it genuinely needs its logic. The real mechanism is node duplication: at each reconvergence point, the shared logic gets copied so each tree that needs it owns its own private copy, rather than the two trees somehow sharing a single instance. This is exactly the tractability trade already named above — duplicating some logic costs extra area (and, in the mapped netlist, extra cell instances) in exchange for keeping each tree's covering problem cleanly independent and efficiently solvable.

What comes out the other side

Once covering finishes, "AND of A and B" is no longer an abstract operator — it's a specific, real cell instance from the library, with the exact delay/area/power numbers Standard Cell Libraries covered, chosen specifically because it was one of possibly several ways to realize that piece of logic. The network is now a real, physically-fabricable netlist for the first time in this whole flow — everything before this point was abstract; everything after it is concrete.

What's next

A mapped netlist exists, but nothing so far has told the tool what "correct enough, timing-wise" actually means. The next page covers exactly that — writing the SDC constraints that give every optimization decision, from here forward, something concrete to be judged against.