Why trees are not enough

A tree has no shared logic: each node feeds one parent. Real networks reuse results, so one node can feed several parents — building one copy per parent duplicates the shared logic and charges it twice. Mapping works on the DAG directly, and its unit of work is the cut: leaves separating a node from the primary inputs. Match a library cell against a cut, and the cone above the leaves collapses into that cell.

Two examples carry the lesson: n1 = a AND b, n2 = c AND d, y = n1 OR n2 for enumeration; and t = a AND b feeding y1 = t OR c, y2 = t AND d for sharing.

k-feasible cuts

A cut is k-feasible when it holds at most k leaves. The mapper enumerates every node's k-feasible cuts, then matches library cells against them. Small k keeps the enumeration cheap. The trivial single-leaf cut {y} always exists; larger k adds choices, but the count grows fast, so production mappers keep k small.

Read the table top-down. At k = 1 only the trivial cut fits. At k = 2 the two-leaf cut {n1, n2} appears: both middle nodes as leaves, exactly the shape a two-cell cover needs. At k = 3 each middle node expands into its inputs on one side, and at k = 4 the whole cone becomes one cut. The program below proves the counts instead of asking you to trust the table.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import sys

# Cut enumerator for the n1, n2, y example, plus the duplicated-against-shared cost check.
# Subject: n1 = a AND b, n2 = c AND d, y = n1 OR n2.
# Shared-node subject: t = a AND b, y1 = t OR c, y2 = t AND d.

FANIN = {"a": (), "b": (), "c": (), "d": (),
         "n1": ("a", "b"), "n2": ("c", "d"), "y": ("n1", "n2")}
PIS = {"a", "b", "c", "d"}

def cuts(node, k):
    if node in PIS:
        return [frozenset([node])]
    out = {frozenset([node])}
    subs = [cuts(f, k) for f in FANIN[node]]
    combos = [frozenset()]
    for choices in subs:
        grown = []
        for prefix in combos:
            for ch in choices:
                u = prefix | ch
                if len(u) <= k:
                    grown.append(u)
        combos = grown
    out.update(combos)
    return sorted(out, key=lambda s: (len(s), sorted(s)))

counts = {k: len(cuts("y", k)) for k in (1, 2, 3, 4)}
if counts != {1: 1, 2: 2, 3: 4, 4: 5}:
    print("FAIL: cut counts " + str(counts))
    sys.exit(1)
if frozenset(["n1", "n2"]) not in cuts("y", 2):
    print("FAIL: two-leaf cut {n1, n2} missing at k=2")
    sys.exit(1)
if frozenset(["a", "b", "c", "d"]) not in cuts("y", 4):
    print("FAIL: full-input cut missing at k=4")
    sys.exit(1)

AREAS = {"AND2": 3, "OR2": 3}
dup_cost = 2 * AREAS["AND2"] + AREAS["OR2"] + AREAS["AND2"]
shared_cost = AREAS["AND2"] + AREAS["OR2"] + AREAS["AND2"]
if dup_cost != 12 or shared_cost != 9:
    print("FAIL: duplicated " + str(dup_cost) + " shared " + str(shared_cost))
    sys.exit(1)
print("PASS: cuts of y are 1 2 4 5 for k 1 2 3 4, duplicated cover 12 against shared cover 9")

The program checks two things: the enumerator returns 1, 2, 4, and 5 cuts for k = 1 through 4, with the two-leaf cut {n1, n2} from k = 2; and the shared-node subject priced two ways from library data on plain AND2/OR2 covers (AND2 3, OR2 3) — 12 units duplicating t one copy per parent, 9 building it once and sharing it. The 3-unit gap is exactly one AND2: a copy the shared cover never builds. Those two prices are a hand model, not a tool result: complex or inverting cells can erase the gap, as the ban run below shows.

Cuts on the shared DAG

The sketch draws the shared DAG with two cuts of y1 as dotted lines. The first crosses a, b, and c (cut {a, b, c}); the second only t and c (cut {t, c}), the better match twice over. Two leaves fit the small cells every library holds; the three-leaf cut needs a 3-input cell. And t is shared: below both lines it feeds y1 and y2 alike, so covering t once serves both outputs.

One shared cell in stat

The script maps the shared-node design twice against course.lib — whole library, then NAND2 banned — both under typical.constr with a very loose 100000 ps target. Both runs write report, histogram, and netlist; the assertions prove no generic gate survives either mapping and no NAND2 survives the ban.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

read_verilog <<EOV
module share2(input a, b, c, d, output y1, y2);
wire t;
assign t = a & b;
assign y1 = t | c;
assign y2 = t & d;
endmodule
EOV
synth -top share2
design -save generic
tee -o abc_full.txt abc -liberty course.lib -constr typical.constr -D 100000
tee -o stat_full.txt stat -liberty course.lib
write_json net_full.json
select -assert-none t:$and t:$or t:$xor t:$xnor t:$mux t:$not
select -assert-none t:$_AND_ t:$_OR_ t:$_XOR_ t:$_XNOR_ t:$_MUX_ t:$_NOT_ t:$_NAND_ t:$_NOR_
select -assert-none t:AND2
check
design -load generic
tee -o abc_nonand2.txt abc -liberty course.lib -dont_use NAND2 -constr typical.constr -D 100000
tee -o stat_nonand2.txt stat -liberty course.lib
write_json net_nonand2.json
select -assert-none t:$and t:$or t:$xor t:$xnor t:$mux t:$not
select -assert-none t:$_AND_ t:$_OR_ t:$_XOR_ t:$_XNOR_ t:$_MUX_ t:$_NOT_ t:$_NAND_ t:$_NOR_
select -assert-none t:NAND2
check
log PASS: shared node maps once with and without NAND2

The full run holds 5 cells at area 8 with 1 shared net: t built once, consumed twice. The recorded INV x2, NAND2 x2, NOR2 x1 is a different cover from the hand model — NAND2 and NOR2 cells plus inverters instead of plain AND2/OR2 — so it lands where the hand prices do not predict. The shared net is t itself: the NAND2 output fed by a and b, fanning out twice, built once in complemented form.

Break it: ban a cell the cover uses

The break-it reruns the same DAG and library minus NAND2, which the recorded full cover uses twice. The mapper rebuilds the design as AOI21 x1, INV x2, NAND3 x1: 4 cells at area 8 against 5 cells at area 8 free. Area holds but sharing does not — 0 shared nets against 1 shared net before — because with no NAND2 the mapper duplicates t inside the NAND3 and the AOI21. A dont_use entry bites exactly when it removes a cell the cover wants; here the price is duplication, yet in this ABC script the duplicated cover reports the shorter arrival (181 ps against 191 ps): each output cone is one complex cell plus an inverter, so neither output waits on the shared complemented t. Duplication for speed is a real trade, not just a cost.

Common mistakes

Related topics

• Covering a Network with Cells

• Area Against Delay