Capstone: an ALU with a budget

Build an 8-bit ALU from a brief, compute its flags from logic it already has, and share one adder between addition, subtraction and compare until it fits a cell budget.

Lesson: R1.8
Time: 35 min
Runs on: Your browser
Check: 5 questions

An 8-bit ALU passed every test and missed its cell budget: 207 cells against 200. Its designer removed the comparator, sure it was the waste, and the count went to 206. The synthesizer had already merged it. The waste was the second adder: SUB had its own subtractor in its own case arm.

Version	Cells	Levels of logic on this flow
the starter: adder, subtractor, comparator, carry by compare	207	18
step 1: a < b read from the borrow of a 9-bit subtraction	206	19
step 2: also the carry from a 9-bit addition	206	19
step 3: one adder for ADD, SUB and CMP	174	22
the budget: the step-3 count plus 15 percent	200

Measured with Yosys 0.70 on this flow. Only step 3 moves the count.

The brief: eight operations and three flags

An ALU (arithmetic logic unit) takes two operands and an operation code and returns a result plus flags, single bits that describe the result. This one is 8 bits wide and purely combinational. Z is 1 when the result is zero. N is the top bit of the result. C depends on the operation.

op	Name	y	c
0	ADD	a + b, low 8 bits	the carry out of bit 7
1	SUB	a - b, low 8 bits	the borrow: 1 when a < b
2, 3, 4	AND, OR, XOR	a & b, a \| b, a ^ b	0
5	SHL	a shifted left by one	a[7], the bit shifted out
6	SHR	a shifted right by one	a[0], the bit shifted out
7	CMP	1 when a < b, else 0	the borrow, as for SUB

z = 1 when y is 0, and n = y[7], for every operation. Comparisons are unsigned.

Four operations and their flagsFour cycles of the lab bench, one operation each. The flags come from the same result the operation produces.

Cycle 0
200 + 100 = 300, which needs 9 bits. y keeps the low 8 bits, 44, and the ninth bit becomes c.
Cycle 1
20 - 30 wraps to 246. The subtraction borrowed, so c is 1, and the top bit of 246 sets n.
Cycle 2
9 - 9 is 0: z is 1. No borrow, so c is 0.
Cycle 3
CMP asks whether 3 < 9. The answer is the same borrow SUB produced: y is 1 and c is 1.

Measured on the lab bench, cycles 1 to 4.

The starter builds every operation from its own operator: an adder, a subtractor, a comparator for a < b and a second comparator that spots a wrapped sum. Before mapping to gates, Yosys turns each operator into an arithmetic cell. It already reads a < b from the subtractor, because both have the same operands. So the starter has three arithmetic cells, not four.

Read less-than from the borrow
Subtract in 9 bits, {lt, diff} = {1'b0, a} - {1'b0, b}: bit 8 is 1 exactly when a < b. 207 cells become 206, because the synthesizer had done this already.
Read the carry from the ninth bit
Add in 9 bits and take bit 8 as the carry. Before mapping there is one arithmetic cell fewer; after mapping the count is still 206. Gate counts do not simply add up, so measure every change.
One adder for three operations
a - b equals a + ~b + 1. Feed the adder b or ~b and a carry-in of 1 for SUB and CMP. Three arithmetic cells become one and the count drops to 174.

An operator per operation

assign sum  = a + b;
assign diff = a - b;
assign lt   = a < b;

207 cells, 18 levels. An adder and a subtractor sit in two case arms; the synthesizer keeps both.

One shared adder

assign sub = (op != ADD);
assign {co, r} = {1'b0, a}
               + {1'b0, sub ? ~b : b}
               + 9'(sub);
assign lt  = ~co;

174 cells, 22 levels. The inverter and the select now sit in front of the adder.

One adder serves ADD, SUB and CMPArrows carry data. The decode sets sub for every operation except ADD; the other operations ignore the adder, so their value of sub does not matter.

ADD
The decode sets sub to 0: b passes unchanged, the carry-in is 0, and co is the carry out.
SUB 20 - 30
Now sub is 1: the adder computes 20 + ~30 + 1. The low 8 bits are 246. No carry out means a borrow, so c = ~co = 1.
Follow the calls, values and waits
1. call sub = 1: op decode → b or ~b
2. data ~30: b or ~b → 9-bit adder
3. data 246: 9-bit adder → result mux
CMP
The same subtraction. Its borrow is the answer to a < b: it becomes y[0] and c. No comparator is needed.
Follow the calls, values and waits
1. data borrow: 9-bit adder → flags

Read the diagram as text

op decode: sub = (op != ADD)
b: operand
b or ~b: chosen by sub
9-bit adder: a + (b or ~b) + sub
result mux: y = r for ADD and SUB
flags: c = co or ~co; z, n from y

op decode → b or ~b: sub
b → b or ~b: b
b or ~b → 9-bit adder: b or ~b
op decode → 9-bit adder: carry-in
9-bit adder → result mux: r
9-bit adder → flags: co

Sharing trades depth for area here: 33 fewer cells, 4 more levels of logic on this flow.

What a cell budget means

The budget is the count of the shared design plus 15 percent: 200 cells. It is a count of generic gates from one pinned flow, Yosys 0.70 with its default mapping. It is not silicon area. A real library has cells of different sizes, and another tool maps differently. The budget compares two designs on the same flow, and that comparison is what carries over.

The levels went up from 18 to 22. Sharing put a select in front of the adder, so the longest path got longer. A budget on cells alone accepts that trade; a fast design might not.

Design brief

Port	Direction	Width	Meaning
a, b	input	[7:0]	operands
op	input	[2:0]	the operation: the table above; comparisons unsigned
y	output	[7:0]	result
z, c, n	output	1	zero, carry or borrow, negative

Latency: combinational: every output follows the inputs in the same cycle
Parameters: Budget: at most 200 cells on this flow; no latches
Corner cases: a carry out of 255 + 1; a borrow; a zero result; a bit shifted out of each end

The lab ships the starter. Run it: 1011 cases, none wrong. Synthesize: 207 cells, over budget. Apply the three steps one at a time and Synthesize after each. Run the bench every time. Measured: a shared adder with no carry-in passes ADD and fails SUB, printing 255 for 9 - 9.

Asked in interviews

How do you get a < b cheaply when you already subtract?
Subtract one bit wider: bit 8 of a - b is the borrow, 1 exactly when a < b for unsigned operands. With a + ~b + 1 the carry out is the inverse of the borrow. Either way the comparator is free.
What is logic sharing?
Using one piece of hardware for operations that never happen in the same cycle. Here ADD, SUB and CMP use one adder: SUB inverts b and sets the carry-in. Measured here, the count fell from 207 to 174 cells while the depth rose from 18 to 22 levels.
How would you estimate area before synthesis?
Count the operators and their widths: adders, comparators, multipliers, multiplexer inputs per bit, flops. Look for operators that repeat across exclusive cases. Then synthesize and compare, because the tool may already share some and not others.

Try it

The starter is correct: every directed line matches the model and the random cases add no error. 200 + 100 gives 44 with c = 1, 20 - 30 gives 246 with c and n set, 9 - 9 sets z, and the shifts report the bit that fell off each end.

Synthesize reports 207 cells. Make the three steps in order and Synthesize after each: 206, 206, then 174 cells, with the levels going from 18 to 19 to 22. The bench output never changes.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service

Edit the design, then Run, Lint or Synthesize

Expected: e0 ADD a=100 b=27 y=127 z=0 c=0 n=0 e1 ADD a=200 b=100 y=44 z=0 c=1 n=0 e2 SUB a=20 b=30 y=246 z=0 c=1 n=1 e3 SUB a=9 b=9 y=0 z=1 c=0 n=0 e4 CMP a=3 b=9 y=1 z=0 c=1 n=0 e5 CMP a=9 b=3 y=0 z=1 c=0 n=0 e6 AND a=12 b=10 y=8 z=0 c=0 n=0 e7 OR a=12 b=10 y=14 z=0 c=0 n=0 e8 XOR a=12 b=12 y=0 z=1 c=0 n=0 e9 SHL a=129 b=0 y=2 z=0 c=1 n=0 e10 SHR a=129 b=0 y=64 z=0 c=1 n=0 1011 cases, 0 wrong

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

Original example source

// alu8: an 8-bit ALU. Eight operations, a result y and three flags (see the brief).
module alu8 (
  input  logic [7:0] a, b,
  input  logic [2:0] op,
  output logic [7:0] y,
  output logic       z, c, n          // zero, carry or borrow, negative
);
  localparam logic [2:0] ADD = 3'd0, SUB = 3'd1, AND = 3'd2, OR = 3'd3,
                         XOR = 3'd4, SHL = 3'd5, SHR = 3'd6, CMP = 3'd7;
  logic [7:0] sum, diff;
  logic       carry, lt;
  assign sum   = a + b;                 // the adder
  assign diff  = a - b;                 // the subtractor
  assign carry = sum < a;               // the sum wrapped around: a carry out of bit 7
  assign lt    = a < b;                 // the comparator

  always_comb begin
    y = 8'h00; c = 1'b0;
    case (op)
      ADD: {c, y} = {carry, sum};
      SUB: {c, y} = {lt, diff};         // c is the borrow: 1 when a < b
      AND: y = a & b;
      OR:  y = a | b;
      XOR: y = a ^ b;
      SHL: {c, y} = {a, 1'b0};          // c is the bit shifted out of the top
      SHR: {y, c} = {1'b0, a};          // c is the bit shifted out of the bottom
      CMP: {c, y} = {lt, 7'd0, lt};     // y = 1 when a < b
      default: ;
    endcase
  end
  assign z = (y == 8'h00);
  assign n = y[7];
endmodule

Read included file: tb.sv

`timescale 1ns/1ps
module tb;
  logic clk = 0;
  always #5 clk = ~clk;                   // rising edges at 5, 15, 25, ...
  int edge_n = -1;
  always @(posedge clk) edge_n = edge_n + 1;
  logic [7:0] a = 0, b = 0;
  logic [2:0] op = 0;
  logic [7:0] y;
  logic       z, c, n;
  logic [10:0] want;
  int cases = 0, wrong = 0;
  int unsigned seed = 1;
  bit quiet = 0;
  localparam logic [2:0] ADD = 3'd0, SUB = 3'd1, AND = 3'd2, OR = 3'd3,
                         XOR = 3'd4, SHL = 3'd5, SHR = 3'd6, CMP = 3'd7;
  // The model: the brief, written as plainly as possible. It returns {y, z, c, n}.
  function automatic logic [10:0] model(input logic [2:0] o, input logic [7:0] x, input logic [7:0] w);
    logic [8:0] t;
    logic [7:0] r;
    logic       cy;
    cy = 1'b0;
    case (o)
      ADD: begin t = {1'b0, x} + {1'b0, w}; r = t[7:0]; cy = t[8]; end
      SUB: begin r = x - w; cy = (x < w); end
      AND: r = x & w;
      OR:  r = x | w;
      XOR: r = x ^ w;
      SHL: begin r = x << 1; cy = x[7]; end
      SHR: begin r = x >> 1; cy = x[0]; end
      default: begin r = (x < w) ? 8'd1 : 8'd0; cy = (x < w); end   // CMP
    endcase
    return {r, r == 8'd0, cy, r[7]};
  endfunction
  function automatic string name(input logic [2:0] o);
    case (o)
      ADD: return "ADD"; SUB: return "SUB"; AND: return "AND"; OR: return "OR";
      XOR: return "XOR"; SHL: return "SHL"; SHR: return "SHR"; default: return "CMP";
    endcase
  endfunction
  alu8 dut (.a(a), .b(b), .op(op), .y(y), .z(z), .c(c), .n(n));
  // Advance to the next rising edge, wait for the design to settle, then print one line.
  task automatic tick();
    @(posedge clk); #1;
    want = model(op, a, b);
    cases++;
    if ({y, z, c, n} !== want) wrong++;
    if (!quiet) $display("e%0d %s a=%0d b=%0d y=%0d z=%b c=%b n=%b%s", edge_n, name(op), a, b, y, z, c, n,
                         ({y, z, c, n} === want) ? "" : "  wrong");
  endtask
  initial begin
    op = ADD; a = 100; b = 27;  tick();
    op = ADD; a = 200; b = 100; tick();   // carry out
    op = SUB; a = 20;  b = 30;  tick();   // borrow
    op = SUB; a = 9;   b = 9;   tick();   // zero
    op = CMP; a = 3;   b = 9;   tick();
    op = CMP; a = 9;   b = 3;   tick();
    op = AND; a = 12;  b = 10;  tick();
    op = OR;  a = 12;  b = 10;  tick();
    op = XOR; a = 12;  b = 12;  tick();
    op = SHL; a = 129; b = 0;   tick();
    op = SHR; a = 129; b = 0;   tick();
    // 1000 more cases from a fixed seed, counted but not printed
    quiet = 1;
    for (int k = 0; k < 1000; k++) begin
      seed = seed * 1103515245 + 12345;
      {op, a, b} = seed[26:8];
      tick();
    end
    $display("%0d cases, %0d wrong", cases, wrong);
    $finish(0);                             // quiet: no "$finish called" line
  end
endmodule

Check yourself

Predict the outputThe shared ALU computes SUB with a = 5 and b = 7. The program prints the result and the three flags. What is the output line?

// alu8: an 8-bit ALU. Eight operations, a result y and three flags (see the brief).
module alu8 (
  input  logic [7:0] a, b,
  input  logic [2:0] op,
  output logic [7:0] y,
  output logic       z, c, n          // zero, carry or borrow, negative
);
  localparam logic [2:0] ADD = 3'd0, SUB = 3'd1, AND = 3'd2, OR = 3'd3,
                         XOR = 3'd4, SHL = 3'd5, SHR = 3'd6, CMP = 3'd7;
  logic [7:0] r;                        // the one adder's 8-bit result
  logic       sub, co, lt;
  assign sub = (op != ADD);             // subtract for SUB and CMP; the other ops ignore r
  assign {co, r} = {1'b0, a} + {1'b0, sub ? ~b : b} + 9'(sub);   // a - b = a + ~b + 1
  assign lt  = ~co;                     // no carry out of a + ~b + 1 means a borrow: a < b

  always_comb begin
    y = 8'h00; c = 1'b0;
    case (op)
      ADD: {c, y} = {co, r};
      SUB: {c, y} = {lt, r};            // c is the borrow: 1 when a < b
      AND: y = a & b;
      OR:  y = a | b;
      XOR: y = a ^ b;
      SHL: {c, y} = {a, 1'b0};          // c is the bit shifted out of the top
      SHR: {y, c} = {1'b0, a};          // c is the bit shifted out of the bottom
      CMP: {c, y} = {lt, 7'd0, lt};     // y = 1 when a < b
      default: ;
    endcase
  end
  assign z = (y == 8'h00);
  assign n = y[7];
endmodule
module tb;
  logic [7:0] a, b, y;
  logic [2:0] op;
  logic       z, c, n;
  alu8 dut (.a(a), .b(b), .op(op), .y(y), .z(z), .c(c), .n(n));
  initial begin
    op = 3'd1; a = 8'd5; b = 8'd7;   // SUB
    #1 $display("y=%0d z=%b c=%b n=%b", y, z, c, n);
    $finish(0);
  end
endmodule

Spot the bugEach option is the body of a module that computes the 8-bit sum y and the carry c of an adder. The bench tries four pairs, including 200 + 100 and 255 + 1. Which option fails?

assign s9 = {1'b0, a} + {1'b0, b};
assign y  = s9[7:0];
assign c  = s9[8];

assign {c, y} = a + b;

assign s9 = {1'b0, a} + {1'b0, b};
assign y  = s9[7:0];
assign c  = s9[7];

assign y = a + b;
assign c = (y < a);

ConceptWhy can one subtractor answer both SUB and CMP (a < b) for unsigned operands?

Because CMP needs only the top bit of a - b, which is the sign of the differenceBecause a comparator and a subtractor cost the same, so the choice does not matterBecause the synthesizer always merges every pair of operators in one moduleBecause a - b borrows exactly when a < b, and the borrow is the ninth bit of the subtraction

ConceptA design meets a 200-cell budget on this flow. What does that tell you?

That it is within 15 percent of the reference, counted on the same pinned flowThat its longest path is shorter than the reference design's longest pathThat the design will fit 200 cells of any standard-cell libraryThat it is the smallest correct design the synthesizer can produce

Read the waveformIn the trace of four operations, in which cycle is c set by a carry out of an addition rather than by a borrow?

Four operations and their flags

One operation per cycle, from cycle 0.

Cycle 1, the SUB of 20 and 30Cycle 0, the ADD of 200 and 100Cycle 2, the SUB of 9 and 9Cycle 3, the CMP of 3 and 9

Remember

Size arithmetic on purpose: a 9-bit sum keeps the carry, and bit 8 of a 9-bit difference is the borrow, which is a < b for unsigned operands.
Compute flags from logic you already have: z is a NOR of the result, n its top bit, c the ninth bit of the adder.
One adder serves ADD, SUB and CMP: a - b = a + ~b + 1. Measured here, that took the ALU from 207 to 174 cells and from 18 to 22 levels.
The synthesizer already merges an operator pair with the same operands, such as a - b and a < b, but not an adder and a subtractor in separate case arms: measure before and after every change.
A cell budget compares designs on one pinned flow; it is not silicon area, and depth is a separate number.

The brief: eight operations and three flags

Three sharing steps, measured

What a cell budget means

Try it

Check yourself

Remember