2. The MAC and Number Formats: Two's Complement, Overflow, and the Tests That Found Three Holes

About the animals in this picture and where they are standing

• Nubian ibex (Capra nubiana) lives in the rocky, arid hills of north-east Africa and the Arabian Peninsula, from the Sinai and Egypt south to Sudan and Ethiopia. Its coat matches the desert rock, and the males' ridged horns sweep back like a sickle.
• Walia ibex (Capra walie) lives nowhere but the Simien Mountains of northern Ethiopia, on high cliffs. It is endangered, with only a few hundred animals remaining, and is protected within the Simien Mountains National Park.
• Iberian ibex (Capra pyrenaica) lives in the mountains of Spain and Portugal. Its Pyrenean subspecies, the bucardo, died out in 2000. In 2003 scientists cloned one; the kid lived only minutes, making it the first extinct animal to be cloned.
• Markhor (Capra falconeri) lives in the mountains of Pakistan, Afghanistan and neighbouring regions. The males' horns twist in a corkscrew; the name is often explained as Persian for 'snake-eater'. It is Pakistan's national animal, and community-based conservation has helped some populations recover.

The scene is imaginary: it is set on Mars: gravity about 38% of Earth's, a dusty red landscape and two small moons, Phobos and Deimos. The animals are stylised drawings, shown where they could not live, for effect.

What you will understand: how an 8-bit signed number is stored, why the multiply-accumulate (MAC) unit is the atom of every matrix engine, what happens when a sum does not fit (wrap or saturate), and what the same multiplier costs when it is written two different ways. You will also see a test suite that looked complete have three holes, found by breaking the circuit on purpose.

What you need to know first: Chapter 1 (the flow: golden model, two simulators, Yosys, mutation). Appendix C (number formats) goes deeper on everything in the first half of this chapter.

What this chapter builds: rtl/mul8.v (two multipliers), rtl/mac.v (the multiply-accumulate unit, wrapping or saturating), their golden models model/mul8_gold.py and model/mac_gold.py, testbenches tb/mul8_tb.v and tb/mac_tb.v, the mutation script tools/mut_ch02.py, and for the two running examples tb/mac_trace_tb.v, tb/mac_overflow_tb.v, tools/ch02_example_a.py, tools/ch02_example_b.py.

Why the MAC is the atom

A large language model, run to produce one token, is almost entirely one operation repeated billions of times: take two lists of numbers, multiply them pairwise, and add the products up. That is a dot product, and one output number of a matrix multiplication is one dot product. Everything else in the model (the normalizations, the softmax, the activation functions) is small next to it. When people say an AI accelerator "does 100 trillion operations per second" they are counting multiplies and adds, and nearly all of them are the multiply-add step of a dot product.

The hardware for one step of that is the multiply-accumulate unit, MAC for short: it holds a running sum, and each clock cycle it multiplies two inputs and adds the product to the sum. A systolic array (Chapter 4) is a grid of these. The rest of the book is, in a sense, about feeding MACs, emptying them, and keeping them busy; this chapter is about making one MAC correct.

"Correct" turns out to need three decisions that look trivial and are not: how a signed number is stored, how wide the running sum must be, and what to do when the sum does not fit. We take them in that order, each one first by hand and then in the circuit.

Signed numbers: two's complement

The chip stores a number in a fixed count of bits, and we want negatives. The universal answer is two's complement: give the top bit a negative weight and keep all the other weights as in ordinary binary. For eight bits the weights are -128, 64, 32, 16, 8, 4, 2, 1. A value is the sum of the weights of the bits that are 1.

Figure 2.1: add up the weights of the 1 bits. Only the top bit has a negative weight.

Work three of them yourself before reading on: 0101_0011 is 64 + 16 + 2 + 1 = 83. 1011_0101 is -128 + 32 + 16 + 4 + 1 = -75. 1111_1111 is -128 + 127 = -1, which is why "all ones" means minus one and not "very large".

Why do hardware designers prefer this to a sign bit plus magnitude? Because the same adder works for both. Add the bit patterns 1111_1111 (-1) and 0000_0001 (+1) with an ordinary unsigned adder and you get 1_0000_0000; drop the ninth bit and you have 0000_0000 = 0. No special case for negative numbers anywhere. The chip needs only one adder circuit, and the meaning of the pattern (signed or unsigned) is a decision made by whoever reads the result.

An equivalent picture is a ring. Four bits have sixteen patterns; arrange them round a clock face and count clockwise, and after 7 comes -8:

Figure 2.2: the two's-complement ring for 4 bits. The 8-bit version has 256 positions and the same jump from +127 to -128.

That jump is overflow, and it is the heart of this chapter: addition on the ring never fails, it just goes round. Whether going round is acceptable depends on what the number means.

The range of eight bits is -128 to +127: one more negative value than positive. The asymmetry matters twice in this book. First, the product -128 x -128 = +16384 is the largest product magnitude (127 x 127 = 16129 is smaller). Second, Chapter 3 will choose the quantized range -127..127 on purpose, to keep the format symmetric and avoid ever producing -128 at all.

Multiplying two signed bytes

You multiply by hand in decimal by writing a shifted copy of the top number for each digit of the bottom one and adding the rows. In binary it is easier: each digit is 0 or 1, so each row is either the top number shifted, or nothing. Two's complement adds one wrinkle: the top bit of the bottom number has weight -128, so its row is subtracted.

Figure 2.3: 5 x (-3) as shift-and-add. Rows for weights +64 ... +1 are added; the row for weight -128 is subtracted (the red row). The sum is -15.

Check the arithmetic against the figure: 320 + 160 + 80 + 40 + 20 + 5 = 625, and 625 - 640 = -15. If the sign row had been added the answer would be +1265, which is the classic mistake, and the first multiplier mutant in the table below makes exactly that change.

An 8 x 8 signed product fits in 16 bits (the largest magnitude, 16384, needs 15 bits plus a sign). That is what p is in the MAC.

Sums grow: how wide must the accumulator be?

One product is 16 bits. A sum of two products can reach twice that, which needs one more bit; a sum of four needs two more. In general a sum of K products of at most 2^14 each needs about 15 + log2(K) bits plus a sign bit.

Figure 2.4 (derived, not measured): the width needed to hold the worst case grows by one bit per doubling of K. 32 bits hold up to K = 131,071 products; the 131,072nd worst-case product needs a 33rd bit.

So a 32-bit accumulator is not unconditionally safe. It is safe for any sum of up to 131,071 products, whatever the data, and for far longer sums of ordinary data (Running example B measures how much). That sounds like plenty: a dot product in a language model is typically 4,096 to 16,384 long. But "safe for realistic inputs" and "safe for every input" are different claims, and the hardware has to do something defined for the second case.

What to do when the sum does not fit

There are exactly two reasonable answers.

• Wrap. Keep the low 32 bits and drop the rest. This is what a plain 32-bit adder does for free, and costs nothing. The price: a sum just past +2^31 becomes a hugely negative number, silently.
• Saturate. Clamp to the nearest representable value, -2^31 or +2^31 - 1. This costs comparators and a multiplexer on the sum, but the answer is wrong "gracefully": it is still the largest value the format can hold, with the correct sign.

Figure 2.5 (derived from the arithmetic, confirmed on the circuit in Running example B): after 131,072 products of +16384 the true sum is 2^31. The wrapping MAC has jumped to -2^31; the saturating one is parked at 2^31 - 1.

Which is better depends on the application. For audio or graphics, saturation is the long-standing standard (a clipped sample sounds better than a sign flip). For a neural network, an overflowing accumulator means something has already gone wrong (Chapter 3 chooses scales so that it never happens), so the cheaper option is defensible if you prove it cannot happen. This book builds both, measures the cost, and lets Chapter 3 make the larger decision.

The multiplier, in two styles: rtl/mul8.v

// Chapter 2: two signed 8x8 -> 16 bit multipliers with the same behaviour and different structure.
// mul8_beh lets the synthesis tool choose the structure (the Verilog operator *); mul8_sa spells out a shift-and-add array: one row per bit of b, each row a shifted copy of a,
// and the sign bit of b (bit 7, worth -128) SUBTRACTS its row. In two's complement an n-bit number is  -2^(n-1) * bit(n-1) + sum of 2^i * bit(i).
module mul8_beh(input signed [7:0] a, input signed [7:0] b, output signed [15:0] p);
    assign p = a * b;
endmodule

module mul8_sa(input signed [7:0] a, input signed [7:0] b, output signed [15:0] p);
    wire signed [15:0] ax = a;                       // a sign-extended to the product's width
    wire signed [15:0] r0 = b[0] ? (ax <<< 0) : 16'sd0;
    wire signed [15:0] r1 = b[1] ? (ax <<< 1) : 16'sd0;
    wire signed [15:0] r2 = b[2] ? (ax <<< 2) : 16'sd0;
    wire signed [15:0] r3 = b[3] ? (ax <<< 3) : 16'sd0;
    wire signed [15:0] r4 = b[4] ? (ax <<< 4) : 16'sd0;
    wire signed [15:0] r5 = b[5] ? (ax <<< 5) : 16'sd0;
    wire signed [15:0] r6 = b[6] ? (ax <<< 6) : 16'sd0;
    wire signed [15:0] r7 = b[7] ? (ax <<< 7) : 16'sd0;  // the row for the sign bit
    assign p = r0 + r1 + r2 + r3 + r4 + r5 + r6 - r7;
endmodule

Commentary. Both modules take two signed bytes and produce a signed 16-bit product.

• mul8_beh is one line: assign p = a * b;. Because both operands are declared signed, Verilog's * is a signed multiply, and the synthesis tool decides how to build it.
• mul8_sa builds it the way Figure 2.3 draws it. ax is a sign-extended to 16 bits (so shifting it left never loses the sign). Row k is b[k] ? (ax <<< k) : 0. The last row is r7 and it is subtracted: r0 + ... + r5 + r6 - r7.
• A few details that trip people up: wire signed [15:0] ax = a; sign-extends because a is signed; writing {8'b0, a} would zero-extend and break negative a (that is the multiplier mutant "a is zero-extended instead of sign-extended"). <<< is the arithmetic left shift (for left shifts it matches <<). Every net that takes part in the sum has to be signed, or Verilog silently treats the expression as unsigned.

The MAC: rtl/mac.v

// Chapter 2: a multiply-accumulate unit, the building block of every matrix engine. Each clock with en = 1 it adds the product a*b to a 32-bit accumulator.
//   clr = 1 starts a new sum: the accumulator becomes the product (if en) or zero (if not). rst clears everything.
//   SAT = 0 : the sum wraps around on overflow (what plain 32-bit hardware does).   SAT = 1 : it saturates at the largest or smallest 32-bit value.
// An 8x8 product needs 16 bits and a sum of k products needs 16 + log2(k) bits: 32 bits are enough for 2^16 products of the worst case, so overflow is rare, but it is real, and what to do about it is a design decision.
module mac #(parameter SAT = 0) (input clk, input rst, input clr, input en, input signed [7:0] a, input signed [7:0] b, output reg signed [31:0] acc);
    wire signed [15:0] p = a * b;
    wire signed [32:0] wide = acc + p;                                  // 33 bits: the sum cannot overflow this
    wire signed [31:0] summed = (SAT == 0) ? wide[31:0] :
                                (wide > 33'sd2147483647) ? 32'sd2147483647 :
                                (wide < -33'sd2147483648) ? -32'sd2147483648 : wide[31:0];
    always @(posedge clk) begin
        if (rst) acc <= 32'sd0;
        else if (clr) acc <= en ? {{16{p[15]}}, p} : 32'sd0;
        else if (en) acc <= summed;
    end
endmodule

// the saturating version as a module of its own, so that synthesis tools (and chapters) can name it
module mac_sat(input clk, input rst, input clr, input en, input signed [7:0] a, input signed [7:0] b, output signed [31:0] acc);
    mac #(.SAT(1)) u(.clk(clk), .rst(rst), .clr(clr), .en(en), .a(a), .b(b), .acc(acc));
endmodule

Figure 2.6: the MAC datapath. Everything left of the register is combinational; the register is the only state.

Commentary, line by line.

• wire signed [15:0] p = a * b; is the product, available a gate-delay-or-so after a and b. This is a combinational wire, not a register.
• wire signed [32:0] wide = acc + p; computes the sum in 33 bits. The extra bit is the whole trick: it lets the overflow test see the true sum, which does not fit in 32 bits, before it is cut down. If the sum were computed in 32 bits the overflow would already have happened and be invisible (that is the MAC mutant "the sum is only 32 bits wide").
• summed chooses by the parameter SAT. For SAT == 0 it is wide[31:0], the low 32 bits (wrap). For SAT == 1 it compares the true sum against the two limits and returns the limit when it is outside.
• The always @(posedge clk) block is the register with its control: priority order is rst, then clr, then en. clr with en loads the product alone (a new sum begins with this term); clr without en loads zero. With none of them, the accumulator holds.
• mac_sat is the saturating version wrapped as its own module so that Yosys and later chapters can name it.

Two properties of that design are worth saying out loud, because the testbench must check them. A clr cycle with en = 1 does not add to the old sum: it starts a new one. And reset beats everything. A mutant that swaps the priority of en and clr is plausible, and the tests catch it (the MAC mutant "en takes priority over clr").

The answer keys

#!/usr/bin/env python3
"""Chapter 2: golden vectors for the 8x8 signed multipliers: every one of the 65,536 input pairs, with the 16-bit two's-complement product, as 8 hex digits per line: {a[7:0], b[7:0], p[15:0]}."""
import sys
def s8(x): return x - 256 if x >= 128 else x
lines = []
for a in range(256):
    for b in range(256):
        p = (s8(a) * s8(b)) & 0xFFFF; lines.append("%02x%02x%04x" % (a, b, p))
open(sys.argv[1], "w").write("\n".join(lines) + "\n"); print(len(lines), "pairs written to", sys.argv[1])

#!/usr/bin/env python3
"""Chapter 2: golden vectors for the MAC unit. A fixed pseudo-random program of clock cycles: directed sequences that reach every corner (the largest product, -128 * -128 = +16384 which does not fit in int8 arithmetic, long runs that overflow 32 bits both upward and downward, clear with and
without enable, enable off), then random ones. The FIRST line is the number of rows that follow. Each following line is {repeat, clr, en, a, b, acc_wrap, acc_sat} = 20 + 1 + 1 + 8 + 8 + 32 + 32 = 102 bits, written as 26 hex digits: the same clock cycle applied `repeat` times in a row, followed by the values both units must hold AFTER the last of them (long runs are checked every 32,768 cycles).
Usage: mac_gold.py OUTFILE"""
import random, sys
M = 1 << 32
def wrap(x): x &= M - 1; return x - M if x >= M // 2 else x
def sat(x): return max(-(1 << 31), min((1 << 31) - 1, x))
R = random.Random(2); rows = []; aw = asat = 0
def clock(clr, en, a, b, rep=1):
    global aw, asat
    p = a * b
    for k in range(rep):
        if clr and k == 0: aw = asat = (p if en else 0)
        elif en: aw = wrap(aw + p); asat = sat(asat + p)
    rows.append((rep, clr, en, a & 255, b & 255, aw & (M - 1), asat & (M - 1)))
clock(0, 0, 0, 0)                                                                # right after reset: the accumulator must be 0 (a unit that resets to the wrong value is caught here)
clock(1, 0, 0, 0)
for a, b in ((-128, -128), (-128, 127), (127, 127), (127, -128), (0, 0), (1, -1), (-1, -1)):
    clock(1, 1, a, b); clock(0, 1, a, b); clock(0, 0, 5, 5)                     # a fresh sum, then one more product, then an idle cycle
for a, b in ((-128, -128), (127, 127)):                                          # overflow upward: 2^31 / 16384 = 131072 products of the largest value
    clock(1, 0, 0, 0)
    for _ in range(4): clock(0, 1, a, b, 32768)
clock(1, 0, 0, 0)
for _ in range(5): clock(0, 1, -128, 127, 32768)                                # overflow downward (-16256 each: it takes 132,105 of them to pass -2^31)
for k in range(3000):
    clock(R.random() < .1, R.random() < .85, R.randrange(-128, 128), R.randrange(-128, 128))
open(sys.argv[1], "w").write("%026x\n" % len(rows) + "\n".join("%026x" % ((r << 82) | (c << 81) | (e << 80) | (a << 72) | (b << 64) | (w << 32) | s) for r, c, e, a, b, w, s in rows) + "\n"); print(len(rows), "clock cycles written to", sys.argv[1])

The multiplier is checked exhaustively: 256 x 256 = 65,536 pairs. The MAC has state, so its key is a sequence: each row is a run of cycles with the expected wrapped and saturated accumulator after it. The sequence contains directed corner cases, an initial post-reset check, upward overflow (4 x 32,768 cycles of -128 x -128, i.e. 2^31 total), downward overflow (5 x 32,768 cycles of -128 x 127), and 3,000 random rows. Word 0 of the vector file is the row count: Verilator is a two-state simulator and cannot see an "unknown" end marker, which hung the first version of this testbench (the lesson is in the notes below).

Notice what the Python key does not do: it does not look at the Verilog, and it does not use the same method. It models the MAC as plain Python integers with explicit wrap and sat functions. Independence is the point: if the same person made the same mistake in both, the test would pass and the chip would be wrong, which is why the key is written in a different language from a different mental model (arithmetic on integers, not a circuit).

The testbenches

// Chapter 2: exhaustive test of both multipliers: all 65,536 input pairs against the answers the Python golden model wrote.
`timescale 1ns/1ps
module mul8_tb;
    reg signed [7:0] a, b; wire signed [15:0] p1, p2;
    mul8_beh d1(.a(a), .b(b), .p(p1)); mul8_sa d2(.a(a), .b(b), .p(p2));
    reg [31:0] vec [0:65535]; integer i, bad1, bad2; reg [31:0] v;
    initial begin
        $readmemh("out/mul8_vectors.hex", vec); bad1 = 0; bad2 = 0;
        for (i = 0; i < 65536; i = i + 1) begin
            v = vec[i]; a = v[31:24]; b = v[23:16]; #1;
            if (p1 !== v[15:0]) begin bad1 = bad1 + 1; if (bad1 <= 3) $display("mul8_beh MISMATCH %0d * %0d = %0d, want %0d", a, b, p1, $signed(v[15:0])); end
            if (p2 !== v[15:0]) begin bad2 = bad2 + 1; if (bad2 <= 3) $display("mul8_sa MISMATCH %0d * %0d = %0d, want %0d", a, b, p2, $signed(v[15:0])); end
        end
        if (bad1 == 0 && bad2 == 0) $display("PASS: both multipliers match the golden model on all 65536 input pairs");
        else begin $display("FAIL: mul8_beh %0d, mul8_sa %0d of 65536 pairs differ", bad1, bad2); $fatal(1, "mul8 failed"); end
        $finish;
    end
endmodule

// Chapter 2: the MAC unit (wrapping and saturating versions side by side) against the golden clock-by-clock vectors, including runs of up to 32,768 identical cycles that push the accumulator past both ends of the 32-bit range.
`timescale 1ns/1ps
module mac_tb;
    reg clk = 0, rst = 1, clr = 0, en = 0; reg signed [7:0] a = 0, b = 0; wire signed [31:0] accw, accs;
    mac #(.SAT(0)) dw(.clk(clk), .rst(rst), .clr(clr), .en(en), .a(a), .b(b), .acc(accw));
    mac #(.SAT(1)) ds(.clk(clk), .rst(rst), .clr(clr), .en(en), .a(a), .b(b), .acc(accs));
    always #5 clk = ~clk;
    reg [101:0] vec [0:4095]; integer i, k, rep, badw, bads, checks, nrows; reg [101:0] v;
    initial begin
        $readmemh("out/mac_vectors.hex", vec); badw = 0; bads = 0; checks = 0;
        @(posedge clk); #1 rst = 0;
        nrows = vec[0];
        for (i = 1; i <= nrows; i = i + 1) begin   // word 0 is the row count (a simulator that has only 0 and 1, like Verilator, cannot be asked to find the end of the data by looking for an unknown)
            v = vec[i]; rep = v[101:82]; clr = v[81]; en = v[80]; a = v[79:72]; b = v[71:64];
            for (k = 0; k < rep; k = k + 1) begin @(posedge clk); #1 clr = 1'b0; end   // clr applies to the first cycle of a repeated run only
            checks = checks + 1;
            if (accw !== v[63:32]) begin badw = badw + 1; if (badw <= 3) $display("wrap MISMATCH at row %0d: got %0d want %0d", i, accw, $signed(v[63:32])); end
            if (accs !== v[31:0]) begin bads = bads + 1; if (bads <= 3) $display("sat MISMATCH at row %0d: got %0d want %0d", i, accs, $signed(v[31:0])); end
        end
        if (badw == 0 && bads == 0) $display("PASS: wrapping and saturating MACs match the golden model at all %0d checkpoints", checks);
        else begin $display("FAIL: wrap %0d, sat %0d checkpoints differ", badw, bads); $fatal(1, "mac failed"); end
        $finish;
    end
endmodule

Running it

#!/usr/bin/env python3
"""Chapter 2: the multipliers and the MAC unit through the whole flow: golden vectors, two simulators, and Yosys area for the two multiplier styles and the MAC. Usage: ch02_run.py"""
import os, subprocess, sys
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))); import hw
def gold(script, out): return subprocess.run([sys.executable, script, out], cwd=hw.ROOT, capture_output=True, text=True).stdout.strip()
print("== 1. the golden models write their vectors"); print(gold("model/mul8_gold.py", "out/mul8_vectors.hex")); print(gold("model/mac_gold.py", "out/mac_vectors.hex"))
F = ["rtl/mul8.v", "rtl/mac.v"]
for tb, top in (("tb/mul8_tb.v", "mul8_tb"), ("tb/mac_tb.v", "mac_tb")):
    for name, fn in (("Icarus Verilog", hw.sim_icarus), ("Verilator", hw.sim_verilator)):
        rc, out = fn(F + [tb], top); print(f"\n== 2. {top} in {name}"); print([l for l in out.strip().splitlines() if l.startswith(("PASS", "FAIL", "MISMATCH", "mul8", "wrap", "sat"))][0], f"(exit status {rc})")
print("\n== 3. Yosys: what each multiplier costs")
GATES = "abc -g AND,NAND,OR,NOR,XOR,XNOR,ANDNOT,ORNOT,MUX; opt_clean; stat"
for top in ("mul8_beh", "mul8_sa"):
    g = hw.synth_stats(F, top, f"synth -flatten -top {top}; {GATES}"); l = hw.synth_stats(F, top, f"synth_ice40 -flatten -top {top}; stat")
    print(f"{top:9s} generic gates {g['total']:5d} {dict(sorted(g['cells'].items()))}\n{'':9s} iCE40 cells  {l['total']:5d} {dict(sorted(l['cells'].items()))}")
for top, params in (("mac", ""), ("mac_sat", "")):
    g = hw.synth_stats(F, top, f"synth -flatten -top {top}; {GATES}"); l = hw.synth_stats(F, top, f"synth_ice40 -flatten -top {top}; stat")
    print(f"{top:9s} generic gates {g['total']:5d} {dict(sorted(g['cells'].items()))}\n{'':9s} iCE40 cells  {l['total']:5d} {dict(sorted(l['cells'].items()))}")

Output (cloud sandbox -- live-executed; Icarus Verilog 12.0, Verilator 5.020, Yosys 0.33)

== 1. the golden models write their vectors
65536 pairs written to out/mul8_vectors.hex
3039 clock cycles written to out/mac_vectors.hex

== 2. mul8_tb in Icarus Verilog
PASS: both multipliers match the golden model on all 65536 input pairs (exit status 0)

== 2. mul8_tb in Verilator
PASS: both multipliers match the golden model on all 65536 input pairs (exit status 0)

== 2. mac_tb in Icarus Verilog
PASS: wrapping and saturating MACs match the golden model at all 3039 checkpoints (exit status 0)

== 2. mac_tb in Verilator
PASS: wrapping and saturating MACs match the golden model at all 3039 checkpoints (exit status 0)

== 3. Yosys: what each multiplier costs
mul8_beh  generic gates   401 {'$_ANDNOT_': 8, '$_AND_': 80, '$_MUX_': 2, '$_NAND_': 171, '$_NOT_': 1, '$_ORNOT_': 1, '$_OR_': 2, '$_XNOR_': 8, '$_XOR_': 128}
          iCE40 cells    191 {'SB_CARRY': 10, 'SB_LUT4': 181}
mul8_sa   generic gates   398 {'$_ANDNOT_': 1, '$_AND_': 62, '$_MUX_': 1, '$_NAND_': 197, '$_NOT_': 1, '$_ORNOT_': 1, '$_XNOR_': 14, '$_XOR_': 121}
          iCE40 cells    192 {'SB_CARRY': 11, 'SB_LUT4': 181}
mac       generic gates   725 {'$_ANDNOT_': 8, '$_AND_': 146, '$_MUX_': 3, '$_NAND_': 282, '$_NOR_': 31, '$_NOT_': 1, '$_ORNOT_': 5, '$_OR_': 40, '$_SDFFE_PP0P_': 32, '$_XNOR_': 43, '$_XOR_': 134}
          iCE40 cells    322 {'SB_CARRY': 42, 'SB_DFFESR': 32, 'SB_LUT4': 248}
mac_sat   generic gates   753 {'$_ANDNOT_': 8, '$_AND_': 147, '$_MUX_': 2, '$_NAND_': 261, '$_NOR_': 8, '$_ORNOT_': 5, '$_OR_': 93, '$_SDFFE_PP0P_': 32, '$_XNOR_': 67, '$_XOR_': 130}
          iCE40 cells    435 {'SB_CARRY': 75, 'SB_DFFESR': 32, 'SB_LUT4': 328}

Reading it

• Both simulators pass both testbenches: all 65,536 multiplier pairs and all 3,039 MAC checkpoints.
• The two multipliers cost the same. 401 vs 398 generic gates; 191 vs 192 iCE40 cells. Writing the shift-and-add by hand bought nothing: the synthesis tool already finds a good structure for *. (Measured by Yosys 0.33 with its default flow; a different tool or a hard multiplier block would change this. That is a result about this flow, not a law.) The practical rule: write the clearest description and let the tool optimize, until a measurement says otherwise.
• The MAC is dominated by the 32 flip-flops and the adder. 725 gates of which 32 are registers; saturation adds 28 gates (753) and, on the FPGA mapping, 113 cells (322 -> 435) because the comparators and the mux sit on the 33-bit sum. So the price of saturation is about 4% in generic gates and 35% on the FPGA mapping: not nothing, not prohibitive. (Both are measured counts; both depend on the flow.)
• Nothing here is timing. Gate and cell counts say nothing about speed; Chapter 10 measures that.

Running example A: follow the MAC cycle by cycle

The point of this example: the MAC is a tiny state machine, and the quickest way to understand a state machine is to follow its state through a short program. The testbench tb/mac_trace_tb.v runs ten cycles on the real circuit and prints the accumulator after each one. tools/ch02_example_a.py does the same thing in plain Python from the rules of the MAC (not from the circuit) and checks that the two tables agree.

// Chapter 2, running example A: drive the MAC with a short hand-chosen program and print one line per clock cycle (inputs, product, accumulator after the edge). tools/ch02_example_a.py compares these lines with a hand calculation written independently in Python.
`timescale 1ns/1ps
module mac_trace_tb;
    reg clk = 0, rst = 1, clr = 0, en = 0; reg signed [7:0] a = 0, b = 0; wire signed [31:0] acc;
    mac dut (.clk(clk), .rst(rst), .clr(clr), .en(en), .a(a), .b(b), .acc(acc));
    always #5 clk = ~clk;
    task cyc(input c, input e, input signed [7:0] x, input signed [7:0] y);
        begin @(negedge clk); clr = c; en = e; a = x; b = y; @(posedge clk); #1; $display("T %0d %0d %0d %0d %0d", c, e, x, y, acc); end
    endtask
    initial begin
        @(posedge clk); #1; rst = 0;
        cyc(1, 1, 3, 4);        // start a sum with 3*4
        cyc(0, 1, -5, 6);       // + (-5)*6
        cyc(0, 1, 100, -2);     // + 100*(-2)
        cyc(0, 0, 99, 99);      // en = 0: the inputs are ignored, the accumulator holds
        cyc(0, 1, -128, -128);  // + (-128)*(-128) = +16384
        cyc(0, 1, 7, -9);
        cyc(0, 1, -1, 127);
        cyc(1, 1, 2, 2);        // clr with en: a new sum begins with 2*2 (the old sum is dropped)
        cyc(0, 1, 10, 10);
        cyc(1, 0, 55, 55);      // clr without en: the accumulator becomes 0
        $finish;
    end
endmodule

#!/usr/bin/env python3
"""Chapter 2, running example A: follow the MAC cycle by cycle. A short program is run on the real circuit (Icarus) and, separately, worked out in plain Python with no reference to the circuit; the two tables must agree. Usage: ch02_example_a.py"""
import os, re, subprocess, sys
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))); import hw
R = hw.ROOT
P = [(1, 1, 3, 4), (0, 1, -5, 6), (0, 1, 100, -2), (0, 0, 99, 99), (0, 1, -128, -128), (0, 1, 7, -9), (0, 1, -1, 127), (1, 1, 2, 2), (0, 1, 10, 10), (1, 0, 55, 55)]
acc = 0; hand = []
for clr, en, a, b in P:                                    # the rules of the MAC, written out by hand
    if clr: acc = a * b if en else 0
    elif en: acc += a * b
    hand.append(acc)
subprocess.run(["iverilog", "-g2012", "-s", "mac_trace_tb", "-o", "/tmp/mact.vvp", "rtl/mac.v", "tb/mac_trace_tb.v"], cwd=R, capture_output=True, check=True)
out = subprocess.run(["vvp", "-n", "/tmp/mact.vvp"], cwd=R, capture_output=True, text=True).stdout
rows = [tuple(map(int, l.split()[1:])) for l in out.splitlines() if l.startswith("T ")]
print("cycle  clr en    a    b | product | hand-worked acc | circuit acc | agree")
ok = True
for i, ((clr, en, a, b), h, r) in enumerate(zip(P, hand, rows), 1):
    good = r[4] == h; ok &= good
    print(f"{i:5d}  {clr:3d} {en:2d} {a:4d} {b:4d} | {a*b:7d} | {h:15d} | {r[4]:11d} | {'yes' if good else 'NO'}")
print("\nall 10 cycles agree" if ok and len(rows) == len(P) else "\nMISMATCH")
print("\nread the table: cycle 4 has en = 0, so the product 99*99 is ignored and the accumulator keeps the value from cycle 3 (-218).")
print("cycle 5 adds the largest possible product, +16384: -218 + 16384 = 16166.  Cycle 8 (clr with en) throws the old sum away and starts again at 2*2 = 4.  Cycle 10 (clr without en) forces 0.")
sys.exit(0 if ok else 1)

To compile and run: python3 tools/ch02_example_a.py (it needs iverilog only).

Output (cloud sandbox -- live-executed)

cycle  clr en    a    b | product | hand-worked acc | circuit acc | agree
    1    1  1    3    4 |      12 |              12 |          12 | yes
    2    0  1   -5    6 |     -30 |             -18 |         -18 | yes
    3    0  1  100   -2 |    -200 |            -218 |        -218 | yes
    4    0  0   99   99 |    9801 |            -218 |        -218 | yes
    5    0  1 -128 -128 |   16384 |           16166 |       16166 | yes
    6    0  1    7   -9 |     -63 |           16103 |       16103 | yes
    7    0  1   -1  127 |    -127 |           15976 |       15976 | yes
    8    1  1    2    2 |       4 |               4 |           4 | yes
    9    0  1   10   10 |     100 |             104 |         104 | yes
   10    1  0   55   55 |    3025 |               0 |           0 | yes

all 10 cycles agree

read the table: cycle 4 has en = 0, so the product 99*99 is ignored and the accumulator keeps the value from cycle 3 (-218).
cycle 5 adds the largest possible product, +16384: -218 + 16384 = 16166.  Cycle 8 (clr with en) throws the old sum away and starts again at 2*2 = 4.  Cycle 10 (clr without en) forces 0.

Walkthrough. Read the table one row at a time.

1. Cycle 1: clr = 1, en = 1. A new sum begins with the first product, 3 x 4 = 12. The old accumulator (zero after reset) is irrelevant.
2. Cycles 2 and 3 accumulate: 12 + (-30) = -18, then -18 + (-200) = -218. Negative products are simply added; the hardware has no subtract step because two's complement made that unnecessary.
3. Cycle 4: en = 0. The inputs are 99 x 99 = 9801, a large product, and the accumulator does not move. en is the gate on the accumulator, not on the multiplier (the multiplier is always computing; the product is just not used).
4. Cycle 5 adds -128 x -128 = +16384, the largest product, taking -218 to 16166. Four cycles of the kind the book will later repeat 131,072 times.
5. Cycle 8: clr = 1, en = 1. The accumulator becomes 2 x 2 = 4: the old 15976 is thrown away, not added to. That one rule is how a matrix unit starts a new output element without a separate "set to zero" cycle.
6. Cycle 10: clr = 1, en = 0. The accumulator becomes 0, even though a and b are 55 and 55. Every one of those rows is a test the mutation table later shows is needed.

Running example B: overflow, derived, measured and made to happen

The point of this example: to put numbers on "rare but real". It does three things in order. (1) Derives how many worst-case products fit. (2) Runs the real wrapping and saturating circuits on exactly that many, and a few more, and compares them with Python. (3) Measures how large the sums of random int8 vectors actually get, to show how far typical data stays from the worst case.

// Chapter 2, running example B: push the worst-case product (-128 * -128 = +16384) into a wrapping MAC and a saturating MAC and print both accumulators at chosen counts. 2^31 / 16384 = 131072, so the 131072nd product is the one that does not fit.
`timescale 1ns/1ps
module mac_overflow_tb;
    reg clk = 0, rst = 1, clr = 0, en = 0; wire signed [31:0] w, s; integer n, k;
    mac #(.SAT(0)) uw (.clk(clk), .rst(rst), .clr(clr), .en(en), .a(-8'sd128), .b(-8'sd128), .acc(w));
    mac_sat        us (.clk(clk), .rst(rst), .clr(clr), .en(en), .a(-8'sd128), .b(-8'sd128), .acc(s));
    always #5 clk = ~clk;
    task run_to(input integer target);                         // keep adding until `target` products have been added in total
        begin while (n < target) begin @(negedge clk); en = 1; @(posedge clk); n = n + 1; end @(negedge clk); en = 0; #1; $display("O %0d %0d %0d", n, w, s); end
    endtask
    initial begin
        n = 0; @(posedge clk); #1; rst = 0;
        run_to(1); run_to(1000); run_to(131071); run_to(131072); run_to(131073); run_to(131074); run_to(262143); run_to(262144); run_to(262145);
        $finish;
    end
endmodule

#!/usr/bin/env python3
"""Chapter 2, running example B: overflow. (1) How many worst-case products fit in 32 bits? (2) The real circuits, wrapping and saturating, fed that many, compared with arithmetic done in Python. (3) How likely is overflow for a REAL dot product? A measured experiment on random int8 vectors. Usage: ch02_example_b.py"""
import math, os, random, subprocess, sys
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))); import hw
R = hw.ROOT
def wrap(x): x &= (1 << 32) - 1; return x - (1 << 32) if x >= 1 << 31 else x
def sat(x): return max(-(1 << 31), min((1 << 31) - 1, x))
print("== 1. derived: the width of a sum of K products, worst case |p| = 128*128 = 16384 = 2^14")
print("   K products need ceil(log2(K * 2^14 + 1)) + 1 bits (the +1 is the sign). 32 bits hold 2^31 - 1 = 2147483647.")
for K in (1, 16, 256, 4096, 65536, 131071, 131072):
    need = (K * 16384).bit_length() + 1; print(f"   K = {K:7d}: worst-case sum {K*16384:11d}  needs {need:2d} bits  {'fits in 32' if K*16384 <= 2**31-1 else 'DOES NOT FIT'}")
print(f"   so the largest K that always fits is floor((2^31 - 1) / 16384) = {(2**31-1)//16384}; the 131072nd worst-case product is the first that overflows")
print("\n== 2. the circuits: Icarus on rtl/mac.v (SAT=0, wrap) and mac_sat (SAT=1), against Python")
subprocess.run(["iverilog", "-g2012", "-s", "mac_overflow_tb", "-o", "/tmp/macov.vvp", "rtl/mac.v", "tb/mac_overflow_tb.v"], cwd=R, capture_output=True, check=True)
out = subprocess.run(["vvp", "-n", "/tmp/macov.vvp"], cwd=R, capture_output=True, text=True).stdout
print("   products added | wrap acc (circuit) | sat acc (circuit) | wrap (Python) | sat (Python) | agree")
ok = True
for l in out.splitlines():
    if not l.startswith("O "): continue
    n, w, s = map(int, l.split()[1:]); ew, es = wrap(n * 16384), sat(n * 16384); g = (w == ew and s == es); ok &= g
    print(f"   {n:14d} | {w:18d} | {s:17d} | {ew:13d} | {es:12d} | {'yes' if g else 'NO'}")
print("   look at row 131072: the wrapping unit has jumped from +2147467264 to -2147483648 (a huge positive sum became a huge NEGATIVE one);")
print("   the saturating unit sits at +2147483647. Both are wrong in the strict sense (the true sum is 2147483648), but one is wrong by 1 and the other by 4.3 billion.")
print("\n== 3. measured: a REAL dot product of random int8 vectors, seed 5, 2000 trials per length (200 for the two longest)")
rng = random.Random(5); print("   length K | largest |sum| seen | worst case K*16384 | ratio    | any overflow of 32 bits?")
for K in (64, 256, 1024, 4096, 16384, 65536):
    worst = 0
    for _ in range(2000 if K <= 4096 else 200):
        s = sum(rng.randrange(-128, 128) * rng.randrange(-128, 128) for _ in range(K)); worst = max(worst, abs(s))
    print(f"   {K:8d} | {worst:17d} | {K*16384:18d} | {worst/(K*16384):.5f} | {'yes' if worst >= 2**31 else 'no'}")
print("   Random data grows like sqrt(K), the worst case like K: the typical sum stays about 1/sqrt(K) of the bound. Overflow needs ADVERSARIAL or very structured data;")
print("   this is why 32-bit accumulators are the industry norm for int8, and why the MAC still has to define what happens (a rare event in a safety-critical system is still an event).")
sys.exit(0 if ok else 1)

To compile and run: python3 tools/ch02_example_b.py (it needs iverilog; takes a few seconds, because 262,145 clock cycles are simulated).

Output (cloud sandbox -- live-executed)

== 1. derived: the width of a sum of K products, worst case |p| = 128*128 = 16384 = 2^14
   K products need ceil(log2(K * 2^14 + 1)) + 1 bits (the +1 is the sign). 32 bits hold 2^31 - 1 = 2147483647.
   K =       1: worst-case sum       16384  needs 16 bits  fits in 32
   K =      16: worst-case sum      262144  needs 20 bits  fits in 32
   K =     256: worst-case sum     4194304  needs 24 bits  fits in 32
   K =    4096: worst-case sum    67108864  needs 28 bits  fits in 32
   K =   65536: worst-case sum  1073741824  needs 32 bits  fits in 32
   K =  131071: worst-case sum  2147467264  needs 32 bits  fits in 32
   K =  131072: worst-case sum  2147483648  needs 33 bits  DOES NOT FIT
   so the largest K that always fits is floor((2^31 - 1) / 16384) = 131071; the 131072nd worst-case product is the first that overflows

== 2. the circuits: Icarus on rtl/mac.v (SAT=0, wrap) and mac_sat (SAT=1), against Python
   products added | wrap acc (circuit) | sat acc (circuit) | wrap (Python) | sat (Python) | agree
                1 |              16384 |             16384 |         16384 |        16384 | yes
             1000 |           16384000 |          16384000 |      16384000 |     16384000 | yes
           131071 |         2147467264 |        2147467264 |    2147467264 |   2147467264 | yes
           131072 |        -2147483648 |        2147483647 |   -2147483648 |   2147483647 | yes
           131073 |        -2147467264 |        2147483647 |   -2147467264 |   2147483647 | yes
           131074 |        -2147450880 |        2147483647 |   -2147450880 |   2147483647 | yes
           262143 |             -16384 |        2147483647 |        -16384 |   2147483647 | yes
           262144 |                  0 |        2147483647 |             0 |   2147483647 | yes
           262145 |              16384 |        2147483647 |         16384 |   2147483647 | yes
   look at row 131072: the wrapping unit has jumped from +2147467264 to -2147483648 (a huge positive sum became a huge NEGATIVE one);
   the saturating unit sits at +2147483647. Both are wrong in the strict sense (the true sum is 2147483648), but one is wrong by 1 and the other by 4.3 billion.

== 3. measured: a REAL dot product of random int8 vectors, seed 5, 2000 trials per length (200 for the two longest)
   length K | largest |sum| seen | worst case K*16384 | ratio    | any overflow of 32 bits?
         64 |            147731 |            1048576 | 0.14089 | no
        256 |            327991 |            4194304 | 0.07820 | no
       1024 |            681492 |           16777216 | 0.04062 | no
       4096 |           1428317 |           67108864 | 0.02128 | no
      16384 |           2039896 |          268435456 | 0.00760 | no
      65536 |           4870015 |         1073741824 | 0.00454 | no
   Random data grows like sqrt(K), the worst case like K: the typical sum stays about 1/sqrt(K) of the bound. Overflow needs ADVERSARIAL or very structured data;
   this is why 32-bit accumulators are the industry norm for int8, and why the MAC still has to define what happens (a rare event in a safety-critical system is still an event).

Walkthrough.

1. Derived. The worst-case product is 128 x 128 = 2^14, so K of them sum to K x 2^14, and 2^31 / 2^14 = 2^17 = 131,072. One short of that, K = 131,071, needs exactly 32 bits (2,147,467,264 < 2,147,483,647). At K = 131,072 the sum is 2^31, which needs 33. This is the number in Figure 2.4.
2. Run on the circuit. The table has nine rows, from 1 product to 262,145. The two circuits agree with Python in all nine. The crucial row is 131,072: the wrapping unit's accumulator goes from +2,147,467,264 to -2,147,483,648 in one clock cycle, and the saturating unit goes to +2,147,483,647. That is Figure 2.5, now as numbers from a simulation. After 262,144 products the wrapping unit reads exactly 0: it has gone once all the way round the ring (2^32 / 2^14 = 2^18 products), and its answer is identically what an empty sum would have been.
3. Measured. For random int8 data the largest |sum| seen at length K grows roughly like the square root of K, while the worst case grows like K. At K = 64 the largest observed sum is 14% of the worst case; at K = 65,536 it is 0.45%. No trial came anywhere near 2^31. So with ordinary data the 32-bit accumulator is enormously safe; with adversarial data it is not. (These are measurements on uniformly random bytes, seed 5, a few thousand trials: they say nothing about the structure of real activations, which are far from uniform; Chapter 3 measures a real tiny model.)

What to take from the two examples together. The question "can this overflow?" has two answers, yes in principle and no in practice, and a robust design handles the first and relies on the second for performance. That is why the book builds both policies.

Testing the tests

#!/usr/bin/env python3
"""Chapter 2: test the tests. Break the multiplier and the MAC one line at a time; every mutant must be caught. Two mutants are EQUIVALENT (the saturation compare written with <= and >= where < and > were: at exactly the limit the clamp returns the value it already had)."""
import os, sys
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))); import hw
V = "rtl/mul8.v"; MAC = "rtl/mac.v"
MUL = [
 (V, "mul8_sa: the sign row is added instead of subtracted", "r6 - r7;", "r6 + r7;"),
 (V, "mul8_sa: row 3 is shifted by 2", "b[3] ? (ax <<< 3)", "b[3] ? (ax <<< 2)"),
 (V, "mul8_sa: row 5 is left out of the sum", "r4 + r5 + r6", "r4 + r6"),
 (V, "mul8_sa: row 5 is selected by bit 6", "b[5] ? (ax <<< 5)", "b[6] ? (ax <<< 5)"),
 (V, "mul8_sa: a is zero-extended instead of sign-extended", "wire signed [15:0] ax = a;", "wire signed [15:0] ax = {8'b0, a};"),
 (V, "mul8_sa: the sign row ignores the sign bit", "wire signed [15:0] r7 = b[7] ?", "wire signed [15:0] r7 = b[6] ?"),
 (V, "mul8_beh: the operands are treated as unsigned", "assign p = a * b;", "assign p = $unsigned(a) * $unsigned(b);"),
 (V, "mul8_beh: the top bit of the product is lost", "assign p = a * b;", "assign p = (a * b) & 16'h7fff;"),
]
MACM = [
 (MAC, "mac: the product is subtracted", "wire signed [32:0] wide = acc + p;", "wire signed [32:0] wide = acc - p;"),
 (MAC, "mac: clr with en loads the product without sign extension", "acc <= en ? {{16{p[15]}}, p} : 32'sd0;", "acc <= en ? {16'b0, p} : 32'sd0;"),
 (MAC, "mac: clr with en loads zero", "acc <= en ? {{16{p[15]}}, p} : 32'sd0;", "acc <= 32'sd0;"),
 (MAC, "mac: en takes priority over clr, so clr only works when en is 0", "else if (clr) acc <= en ? {{16{p[15]}}, p} : 32'sd0;\n        else if (en) acc <= summed;", "else if (en) acc <= summed;\n        else if (clr) acc <= 32'sd0;"),
 (MAC, "mac: the upper clamp is one too low", "? 32'sd2147483647 :\n", "? 32'sd2147483646 :\n"),
 (MAC, "mac: the lower clamp is one too high", "? -32'sd2147483648 : wide[31:0];", "? -32'sd2147483647 : wide[31:0];"),
 (MAC, "mac: the SAT parameter is inverted", "(SAT == 0) ? wide[31:0] :", "(SAT == 1) ? wide[31:0] :"),
 (MAC, "mac: the wrapped sum drops bit 31", "(SAT == 0) ? wide[31:0] :", "(SAT == 0) ? {1'b0, wide[30:0]} :"),
 (MAC, "mac: reset loads 1", "if (rst) acc <= 32'sd0;", "if (rst) acc <= 32'sd1;"),
 (MAC, "mac: en is ignored", "else if (en) acc <= summed;", "else acc <= summed;"),
 (MAC, "mac: the sum is only 32 bits wide, so overflow cannot be seen", "wire signed [32:0] wide = acc + p;", "wire signed [31:0] wide32 = acc + p; wire signed [32:0] wide = wide32;"),
 (MAC, "mac: the accumulator is 24 bits (a narrower register)", "output reg signed [31:0] acc);\n    wire signed [15:0] p", "output reg signed [31:0] acc);\n    wire signed [15:0] p"),
]
MACM = [m for m in MACM if "24 bits" not in m[1]]
EQUIV = [
 (MAC, "EQUIVALENT: the upper clamp triggers at the limit itself (>=)", "(wide > 33'sd2147483647)", "(wide >= 33'sd2147483647)"),
 (MAC, "EQUIVALENT: the lower clamp triggers at the limit itself (<=)", "(wide < -33'sd2147483648)", "(wide <= -33'sd2147483648)"),
]
F = ["rtl/mul8.v", "rtl/mac.v"]
print("NOTE: this script deliberately breaks copies of the RTL. 'caught' lines are EXPECTED: they show the testbenches can detect the mistake.")
ok = True
c, n, l = hw.mutate(MUL, F, "mul8_tb", ["tb/mul8_tb.v"]); print("\n".join(l)); print(f"\nmultipliers: {c} of {n} broken circuits caught"); ok &= c == n
c, n, l = hw.mutate(MACM, F, "mac_tb", ["tb/mac_tb.v"]); print("\n" + "\n".join(l)); print(f"\nMAC: {c} of {n} broken circuits caught"); ok &= c == n
c, n, l = hw.mutate(EQUIV, F, "mac_tb", ["tb/mac_tb.v"]); print("\nTwo changes that look like bugs and are not:"); print("\n".join(l)); ok &= c == 0
sys.exit(0 if ok else 1)

Output (cloud sandbox -- live-executed)

NOTE: this script deliberately breaks copies of the RTL. 'caught' lines are EXPECTED: they show the testbenches can detect the mistake.
mul8_sa: the sign row is added instead of subtracted: caught
mul8_sa: row 3 is shifted by 2: caught
mul8_sa: row 5 is left out of the sum: caught
mul8_sa: row 5 is selected by bit 6: caught
mul8_sa: a is zero-extended instead of sign-extended: caught
mul8_sa: the sign row ignores the sign bit: caught
mul8_beh: the operands are treated as unsigned: caught
mul8_beh: the top bit of the product is lost: caught

multipliers: 8 of 8 broken circuits caught

mac: the product is subtracted: caught
mac: clr with en loads the product without sign extension: caught
mac: clr with en loads zero: caught
mac: en takes priority over clr, so clr only works when en is 0: caught
mac: the upper clamp is one too low: caught
mac: the lower clamp is one too high: caught
mac: the SAT parameter is inverted: caught
mac: the wrapped sum drops bit 31: caught
mac: reset loads 1: caught
mac: en is ignored: caught
mac: the sum is only 32 bits wide, so overflow cannot be seen: caught

MAC: 11 of 11 broken circuits caught

Two changes that look like bugs and are not:
EQUIVALENT: the upper clamp triggers at the limit itself (>=): NOT CAUGHT
EQUIVALENT: the lower clamp triggers at the limit itself (<=): NOT CAUGHT

All 8 multiplier mutants and all 11 MAC mutants are caught. Two survive, and both are equivalent mutants: the clamp tests wide > 2^31-1; changing it to >= makes the circuit clamp when the sum equals 2^31-1 exactly, but clamping that value returns 2^31-1, the same number. The lower clamp is symmetric. Neither is a gap.

The three holes that the first version had

The tests above are the second version. The first one passed all its own checks and still let mutants through, each teaching something:

1. The downward overflow run was too short. The first version drove the accumulator down for fewer cycles than it takes to reach -2^31, so the lower clamp was never exercised and "the lower clamp is one too high" survived. The fix is arithmetic, not luck: -128 x 127 = -16256 per cycle needs 2^31 / 16256 ~ 132,100 cycles, so the test runs 5 x 32,768 = 163,840.
2. No check straight after reset. "Reset loads 1" survived until a row was added that looks at the accumulator before any en.
3. One mutant was not a mutant. A "priority" mutant had been written as a rewrite that, on inspection, behaved identically. It was replaced by a true priority swap (en beats clr), which the tests do catch. Reading a survivor before trying to kill it is the discipline from Chapter 1.

Two simulators, two kinds of unknown

Icarus is four-state (0, 1, x, z); Verilator is two-state. A testbench that ends its loop on an x sentinel works in Icarus and hangs in Verilator (the author watched it use 98% CPU for six minutes before finding out). The book's rule since this chapter: no sentinel values, put the count in word 0. This is also the reason to run every test in both tools: each one hides a different kind of mistake.

Common mistakes

• Forgetting signed. In Verilog an expression is signed only if every operand is. One unsigned operand in a * b makes the whole multiply unsigned, and the product of -1 and 1 becomes 255. The mutant "operands treated as unsigned" is this error on purpose.
• Sign-extending with zeros. {8'b0, x} zero-extends; {{8{x[7]}}, x} sign-extends. In mac.v the clr path uses the second form. Zero-extending a negative product silently turns it into a large positive number (the MAC mutant "clr with en loads the product without sign extension").
• Computing the sum in 32 bits and then checking for overflow. The overflow has already happened by the time the check looks; it needs the 33-bit sum (the same MAC mutant).
• Testing only the middle of the range. Random data almost never produces a sum near 2^31, so random testing alone passes the first version of any saturating MAC. The directed overflow runs are what exercise the clamp.
• Treating "equal gate count" as "equal chip". The multipliers cost the same here; that is a claim about Yosys 0.33's default flow on these two descriptions, not about silicon.
• Believing the testbench because it passes. Every mutant above is a way a plausible engineer might break the circuit; the testbench is trusted because it caught them.

What this chapter does and does not establish

• The MAC is correct against the golden model on the vectors used: exhaustive for the multiplier, directed plus 3,000 random sequences for the MAC. Not exhaustive for the MAC (the state space is 2^32 x inputs).
• The gate counts compare flows, not chips. "Same cost" is a finding about Yosys's default synthesis.
• Overflow policy is a decision, not a fact. Wrapping is cheapest and silently wrong; saturating costs gates and is wrong more gracefully. Chapter 3 will make the larger decision, which is to keep the accumulator wide enough that a real model should never need either.
• The random-data measurement is a measurement of random data. It shows the bound is loose for uniform bytes; it does not show a real network stays that far from it.

Chapter summary

Signed 8-bit numbers range -128..127 and are stored in two's complement: the top bit has weight -128, and one adder serves both signs. A multiplier is a set of shifted copies of one operand, with the sign row subtracted. A MAC adds the product to a 32-bit accumulator that is safe for up to 131,071 worst-case products and typically for far more; beyond that it must wrap or saturate. The unit can do either, and saturation costs about 4% more gates (35% more FPGA cells). The behavioural and hand-built multipliers cost the same in Yosys. The tests were exhaustive for the multiplier, sequence-based for the MAC, and mutation found three holes in the first version.

Self-check questions

1. Why is the product -128 x -128 the worst case for the accumulator, and how many such products does it take to overflow 32 bits signed?
2. In mul8_sa, why must the row for bit 7 of b be subtracted?
3. Why does the MAC compute its sum in 33 bits instead of 32?
4. The two multiplier styles cost 401 and 398 gates. What can you conclude, and what can you not?
5. A testbench ends its loop when the expected value is x. Why does it work in Icarus and hang in Verilator?
6. The mutant "the upper clamp triggers at the limit itself (>=)" survives. Is the test weak?
7. Convert 1100_1010 and 0011_0111 to decimal by hand. What is 1100_1010 + 0011_0111 as an 8-bit pattern, and what does it mean as a signed number?
8. In Running example A, what would the accumulator be after cycle 8 if clr with en = 1 loaded zero instead of the product? Which mutant in the table is that, and which row of the program catches it?
9. Running example B shows the wrapping MAC reads exactly 0 after 262,144 worst-case products. Explain why, and why that is worse than reading garbage.

Exercises

1. Change the program. Edit tb/mac_trace_tb.v to compute the dot product of [3, -5, 100, -128] and [4, 6, -2, -128] (a dot product whose last term is the largest possible product), then write the expected value by hand and run the script. Does the final accumulator match your hand result?
2. Find the break point. How many products of 127 x 127 = 16129 does it take to overflow 32 bits? Work it out on paper first, then change tb/mac_overflow_tb.v (the a and b ports and the run_to counts) and confirm.
3. A 16-bit accumulator. If the accumulator were only 16 bits, how many worst-case products would fit? What would the first overflow look like on the ring? Predict, then edit mac.v (acc and wide widths) and run mut_ch02.py to see which tests complain, and why they do.
4. Add a mutant. Write one new mutant for mut_ch02.py that you think is plausible (for example, saturating the lower clamp at -2^31 + 1). Predict whether it is caught, then run it. If it survives, decide whether it is equivalent or a gap.
5. The cost of the policy. Use synth_stats (see tools/ch02_run.py) to measure mac vs mac_sat with synth_ice40 and with the generic flow. Which part of the 35% FPGA increase do you think is the comparators and which is the multiplexer? (Hint: try a version that only checks the upper limit.)