Capstone: An ALU

Build an 8-bit ALU with flags from this module's blocks, and check it with a bench that reads a vector file.

You Will Be Able To

  • Read an ALU datapath: shared adder, logic unit, output mux and flags.
  • Decode an opcode into the adder mode and the mux select.
  • Compute the flags Z, N, C and V for every operation.
  • Write a self-checking bench that reads vectors with $readmemh.
Lesson
G4.11
Time
35 min
Runs on
Your browser
Check
5 questions

A small processor branches on "a < b", which its ALU computes as N XOR V of a − b. The designer reused the overflow rule of the add operation, on b. Every branch goes the wrong way for some operands, even 3 < 5.

A < b as N XOR V, with V Right and V WrongOne comparison per step. The right column is what the shipped ALU said.
0123compare3 < 55 < 3127 < −128−128 < 127correctV from bwrongwrong
Scroll horizontally ↔
  1. Cycle 0

    3 − 5 = −2. The adder added 3 and ~5, which differ in sign, so no overflow. The rule on b sees 3 and 5, same sign, a negative result, and calls it overflow.

  2. Cycle 2

    127 − (−128) overflows to −1. The correct V flips N back to "not less"; the rule on b misses it.

Measured on the simulator. Lesson G4.7 derived the correct rule.

The Datapath

An ALU (arithmetic logic unit) computes one of several operations on two operands, chosen by an opcode. It also reports flags about the result. The ALU below has six operations and four flags.

An 8-bit ALUThe opcode sets the adder's mode and the output mux. The adder and the logic unit work in parallel; the mux picks one result.
  • I/O
  • Datapath
  • Data
  • Control
CallValueReturnWaiting
An 8-bit ALUThe opcode sets the adder's mode and the output mux. The adder and the logic unit work in parallel; the mux picks one result. io a, b 8 bits each io op 3-bit opcode datapath Adder a + (b ⊕ sub) + sub datapath Logic unit AND, OR, XOR datapath Output mux picks y io y result io Z N C V flags a, ba, bsubselectsuma op byC, VZ, N
  1. io a, b8 bits each
    • a, b → Adder
    • a, b → Logic unit
  2. io op3-bit opcode
    • sub → Adder
    • select → Output mux
  3. datapath Addera + (b ⊕ sub) + sub
    • sum → Output mux
    • C, V → Z N C V
  4. datapath Output muxpicks y
    • y → y
    • Z, N → Z N C V
  5. io yresult
  6. io Z N C Vflags
  7. datapath Logic unitAND, OR, XOR
    • a op b → Output mux
  1. ADD 7f + 01

    sub = 0, so the adder adds b. The mux passes the sum, 80. N = 1 and V = 1: two positives gave a negative.

    Follow the calls, values and waits
    1. data sub = 0: op → Adder
    2. data 80: Adder → Output mux
    3. data 80: Output mux → y
  2. SUB 05 − 07

    sub = 1 inverts b and sets the carry in. The sum is fe = −2; C = 0 says a borrow happened.

    Follow the calls, values and waits
    1. data sub = 1: op → Adder
    2. data fe: Adder → Output mux
    3. data fe: Output mux → y
  3. AND f0, 3c

    The logic unit computes 30 and the mux passes it. C and V are 0 for a logic operation.

    Follow the calls, values and waits
    1. data 30: Logic unit → Output mux
    2. data 30: Output mux → y
Read the diagram as text
  • a, b: 8 bits each
  • op: 3-bit opcode
  • Adder: a + (b ⊕ sub) + sub
  • Logic unit: AND, OR, XOR
  • Output mux: picks y
  • y: result
  • Z N C V: flags
  • a, b → Adder: a, b
  • a, b → Logic unit: a, b
  • op → Adder: sub
  • op → Output mux: select
  • Adder → Output mux: sum
  • Logic unit → Output mux: a op b
  • Output mux → y: y
  • Adder → Z N C V: C, V
  • Output mux → Z N C V: Z, N

One adder serves ADD, SUB and SLT; the XOR row and the carry in make the difference (lesson G4.7).

Opcode Decode and the Output Mux

The opcode drives two things: the adder's mode bit sub, and the select of the output mux. Decode each from the opcode in one place, so that two operations can never share a select value.

opOperationsuby
0ADD0a + b
1SUB1a − b
2AND−a & b
3OR−a | b
4XOR−a ^ b
5SLT11 if a < b (signed), else 0
6, 7unused−0

SLT computes a − b and keeps only N XOR V: signed less-than, from lesson G4.8.

The lab ALU synthesized on this site to 143 cells in 20 logic levels. The adder's carry chain sets most of that depth.

The Flags

Z is 1 when the result is zero. N is the top bit of the result. C is the adder's carry out: on a subtraction, 1 means no borrow. V is signed overflow. For logic operations this ALU sets C and V to 0.

OperationyZ N C VWhy
ADD 7f + 01800 1 0 1127 + 1 overflows to −128
ADD ff + 01001 0 1 0unsigned 255 + 1 carries out; signed −1 + 1 = 0 is fine
SUB 05 − 07fe0 1 0 05 − 7 borrows: C = 0
SUB 80 − 017f0 0 1 1−128 − 1 overflows to 127
SUB 42 − 42001 0 1 0equal: zero, and no borrow

From the lab run below.

A Self-Checking Bench with a Vector File

A self-checking bench decides pass or fail by itself. A common shape reads test vectors from a file: one line per test, with the inputs and the expected outputs. A script or a golden model in another language writes the file.

The lab bench plays both parts. A golden function, written from the specification, writes alu_vectors.hex. Then $readmemh loads the file into an array, and a loop applies each vector and compares every output with !==.

Keeping the expected values outside the design matters. A bench that computes them with the design's own expressions repeats its mistakes.

Asked in interviews
  1. How do you get signed less-than from an ALU?

    Subtract and take N XOR V. The sign of a − b is right unless the subtraction overflowed, and then V flips it.

  2. What do the flags Z, N, C and V mean?

    Zero result, negative result (the top bit), carry out of the adder (no borrow, on a subtract), and signed overflow.

  3. How do you verify an ALU?

    With a self-checking bench. A golden model, written from the specification, gives vectors of inputs and expected outputs. A loop applies them and compares every output.

Try It

The golden function writes ten vectors; the checker reads them back with $readmemh and finds no mismatch.

Break the ALU: compute ovf from b instead of bx. Run, and read which vectors the bench now flags.

Delete the default arm of the case. Press Synthesize: the flow refuses the design. Opcodes 6 and 7 assign no y.

Add an operation: op 6 = NOT a. Extend the golden function and add a vector line for it.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: vector 0: op 0 7f 01 -> 80 ZNCV=0101 vector 1: op 0 ff 01 -> 00 ZNCV=1010 vector 2: op 1 05 07 -> fe ZNCV=0100 vector 3: op 1 80 01 -> 7f ZNCV=0011 vector 4: op 1 42 42 -> 00 ZNCV=1010 vector 5: op 2 f0 3c -> 30 ZNCV=0000 vector 6: op 3 f0 0c -> fc ZNCV=0100 vector 7: op 4 ff 0f -> f0 ZNCV=0100 vector 8: op 5 fe 01 -> 01 ZNCV=0000 vector 9: op 5 7f 80 -> 00 ZNCV=1000 0 of 10 vectors wrong

Original design · 143 cells · 0 flip-flops · 0 latches · 20 logic levels. Synthesis uses Yosys; counts depend on the toolchain.

Read included file: tb.sv
// tb.sv: a self-checking bench (read-only). A golden model writes a vector file, as a script would;
// the checker reads it back with $readmemh, applies each vector and compares every output.
module tb;
  localparam int NV = 10;
  logic [2:0]  op;
  logic [7:0]  a, b, y;
  logic        z, n, c, v;
  logic [31:0] vec [NV];         // {op, a, b, y, flags}: one 8-digit hex word per vector
  int          fd, wrong = 0;
  alu8 dut (.op(op), .a(a), .b(b), .y(y), .z(z), .n(n), .c(c), .v(v));

  // The golden model: written from the specification, not from the design.
  function automatic logic [31:0] golden(input logic [2:0] o, input logic [7:0] x, w);
    logic [8:0] t;
    logic [7:0] r;
    logic cy, ov;
    cy = 0; ov = 0;
    case (o)
      3'd0: begin t = x + w;         r = t[7:0]; cy = t[8]; ov = ($signed(x) + $signed(w) > 127) || ($signed(x) + $signed(w) < -128); end
      3'd1: begin t = x + ~w + 9'd1; r = t[7:0]; cy = (x >= w); ov = ($signed(x) - $signed(w) > 127) || ($signed(x) - $signed(w) < -128); end
      3'd2: r = x & w;
      3'd3: r = x | w;
      3'd4: r = x ^ w;
      3'd5: r = ($signed(x) < $signed(w)) ? 8'd1 : 8'd0;
      default: r = 8'd0;
    endcase
    return {1'b0, o, x, w, r, r == 8'd0, r[7], cy, ov};
  endfunction

  initial begin
    // 1. The "script": write the vectors to a file.
    fd = $fopen("alu_vectors.hex", "w");
    $fdisplay(fd, "%h", golden(3'd0, 8'h7F, 8'h01));
    $fdisplay(fd, "%h", golden(3'd0, 8'hFF, 8'h01));
    $fdisplay(fd, "%h", golden(3'd1, 8'h05, 8'h07));
    $fdisplay(fd, "%h", golden(3'd1, 8'h80, 8'h01));
    $fdisplay(fd, "%h", golden(3'd1, 8'h42, 8'h42));
    $fdisplay(fd, "%h", golden(3'd2, 8'hF0, 8'h3C));
    $fdisplay(fd, "%h", golden(3'd3, 8'hF0, 8'h0C));
    $fdisplay(fd, "%h", golden(3'd4, 8'hFF, 8'h0F));
    $fdisplay(fd, "%h", golden(3'd5, 8'hFE, 8'h01));
    $fdisplay(fd, "%h", golden(3'd5, 8'h7F, 8'h80));
    $fclose(fd);
    // 2. The checker: read the file, apply each vector, compare.
    $readmemh("alu_vectors.hex", vec);
    for (int i = 0; i < NV; i++) begin
      {op, a, b} = vec[i][30:12];
      #1;
      if ({y, z, n, c, v} !== vec[i][11:0]) begin
        wrong++;
        $display("vector %0d: op %0d %h %h gave %h ZNCV=%b%b%b%b, want %h ZNCV=%b", i, op, a, b, y, z, n, c, v, vec[i][11:4], vec[i][3:0]);
      end else $display("vector %0d: op %0d %h %h -> %h ZNCV=%b%b%b%b", i, op, a, b, y, z, n, c, v);
    end
    $display("%0d of %0d vectors wrong", wrong, NV);
  end
endmodule

Check Yourself

Spot the bugEach option sets the overflow flag v of an 8-bit adder-subtractor, after bx and y are computed. The bench tries 600 seeded operations. Which option fails?
ConceptThe ALU computes 42 − 42. Which flags are set?
ConceptWhich operations of the lab ALU use the adder?
ConceptWhy does the lab bench write its vectors with a golden function instead of copying expressions from the ALU?
Predict the outputPredict the exact line: SLT of a = fe (−2) and b = 01 as N XOR V of a − b.
module tb;
  logic [7:0] a = 8'hFE, b = 8'h01, bx, d;
  logic v;
  initial begin
    bx = ~b;
    d  = a + bx + 8'd1;
    v  = (a[7] == bx[7]) && (d[7] != a[7]);
    $display("%h %b", d, d[7] ^ v);
  end
endmodule

Common Mistakes

Wrong Compute V for a subtraction with the add rule on b.

The adder adds the inverted b. With the rule on b, even 3 < 5 comes out false, as the hook shows.

Fix Apply the overflow rule to what the adder adds: a and b XOR sub.

Wrong Leave out the default arm of the operation case.

Unused opcodes then keep the old result, which needs a latch. This site's synthesis flow refuses such an always_comb block.

Fix Give every output a value on every path: a default arm, and default flag values before the case.

Wrong Take Z from the 9-bit sum, carry included.

ff + 01 gives 1_00 with a zero result. Z must be 1 there, but the 9-bit value is not zero.

Fix Z = (y == 0) on the 8-bit result that leaves the ALU.

Wrong Build one adder per arithmetic operation.

ADD, SUB and SLT can share one adder with an XOR row; three adders triple the area for no speed.

Fix One adder; the opcode sets the XOR row and the carry in, and the output mux picks the result.

Remember

  • An ALU shares one adder for add, subtract and compare, and a mux picks the result.
  • Decode the opcode once: the adder mode and the mux select.
  • Z = result is zero; N = top bit; C = carry out (no borrow on subtract); V = signed overflow on the adder's operands.
  • Signed less-than is N XOR V of a − b.
  • Check with vectors from a golden model written from the specification, read with $readmemh.

Practice

Report a problem with this page