ALU design

Why it exists

Every arithmetic instruction, every comparison, every address calculation and every branch decision passes through the ALU. It is a purely combinational circuit: two operand inputs, a few control inputs that choose the operation, a result and a handful of status bits (flags). It is also the block that sets the clock speed of the simple processor, because its worst-case delay (the carry through the adder) is the longest path in the datapath. GATE asks you to build an ALU from adders and gates, to give the control signals for an operation, to say what the flags mean, to design the comparison, and to estimate its delay and hardware.

Prerequisites

You need the adder, the adder-subtractor and the carry/overflow flags from adders and subtractors and fixed-point arithmetic, and the multiplexer from multiplexers.

Precise definitions

ALU. A combinational circuit with operands $A$ and $B$ (each $n$ bits), a control input that selects the operation, a result $n$ bits wide and status outputs. The common operations are add, subtract, AND, OR, (NOR, XOR), set-on-less-than and sometimes shifts. Multiplication and division are usually done by a separate unit or by repeated use of the ALU (Booth multiplication).

The one-bit slice. An $n$-bit ALU is $n$ identical slices connected by the carry chain. Each slice contains

• an XOR gate (or multiplexer) that inverts $B$ when a control line $B_{invert}$ is 1,
• an AND gate and an OR gate on $A$ and the (possibly inverted) $B$,
• a full adder with carry in and carry out,
• a multiplexer that picks which of AND, OR, the adder's sum or the special "less" input becomes the result bit.

Operations by control setting (this page's design; $B_{invert}$ also feeds the carry in of the lowest slice):

Subtraction. $A - B = A + \bar{B} + 1$: invert every bit of $B$ and set the carry in to 1 (two's complement negation).

Flags. $Z$ (zero): every result bit is 0, computed by a NOR over all result bits (for $n$ bits a tree of $n - 1$ two-input gates with $\lceil \log_2 n \rceil$ levels). $N$ (negative): the top result bit. $C$ (carry): the carry out of the top slice (after a subtraction a carry of 1 means $A \ge B$ unsigned, i.e. no borrow). $V$ (overflow): the carry into the top slice XOR the carry out of it.

Set on less than. The result is 1 if $A < B$ as signed numbers, else 0. It is computed by subtracting and taking $\text{sign of } (A - B) \oplus V$ (that is $N \oplus V$): the sign bit of the difference alone is wrong when the subtraction overflows. The result is placed in bit 0 and all other bits are 0; the top slice produces the "less" value and feeds slice 0's "less" input. For an unsigned comparison use the carry: $A < B$ exactly when $C = 0$ after the subtraction.

Equality is $Z = 1$ after a subtraction.

Shifters. A barrel shifter shifts by any amount in one step: it has $\lceil \log_2 n \rceil$ stages, stage $k$ shifts by $2^k$ or passes the value unchanged under control of bit $k$ of the shift amount, each stage being $n$ two-input multiplexers: $n \lceil \log_2 n \rceil$ multiplexers in all (160 for 32 bits). A shift register shifts by one position per clock, so shifting by $k$ takes $k$ cycles.

Control codes. With $m$ operations the control field needs $\lceil \log_2 m \rceil$ bits. The classic textbook MIPS-style design uses a 4-bit ALU control: 0000 AND, 0001 OR, 0010 add, 0110 subtract, 0111 set on less than, 1100 NOR, where, in that design, bit 3 inverts $A$, bit 2 inverts $B$ (so 0110 inverts $B$ and adds with carry in 1) and the low two bits choose AND, OR, add or the "less" input; NOR is AND of both inverted inputs.

Speed. The critical path is the carry chain of a ripple adder (about $2n$ gate delays) plus the B-inversion XOR and the output multiplexer. Carry lookahead or a faster adder makes it close to constant; this is why the ALU delay appears in the clock-period calculation of the datapath.

How it works

The animation runs five operations on 8-bit operands with their flags. Look at the two subtractions: with $A = 100$ and $B = -100$ the true difference 200 does not fit, the result bits read $-56$ (so $N = 1$), the overflow flag $V$ is 1, and "set on less than" correctly returns 0 because $N \oplus V = 0$.

result = A AND B, bit by bit

Worked examples

#include <stdio.h>
#include <stdint.h>
 
/* a 1-bit ALU slice: AND, OR, add (full adder) and a "less" input, with an optional inverter on B */
typedef struct { int out, cout, sum; } Slice;
 
static Slice slice(int a, int b, int cin, int binv, int op, int less) {
    int bb = b ^ binv;
    Slice s;
    s.sum = a ^ bb ^ cin;
    s.cout = (a & bb) | (cin & (a ^ bb));
    int r[4] = { a & bb, a | bb, s.sum, less };
    s.out = r[op];
    return s;
}
 
enum { AND, OR, ADD, SUB, SLT };
 
/* an 8-bit ALU made of 8 slices; returns the result and sets the flags */
static unsigned alu8(unsigned a, unsigned b, int op, int *z, int *n, int *c, int *v) {
    int binv = (op == SUB || op == SLT), carry = binv;
    int sel = op == AND ? 0 : op == OR ? 1 : 2;
    unsigned res = 0;
    int carry_into_sign = 0, sign_sum = 0;
    for (int i = 0; i < 8; i++) {
        if (i == 7) carry_into_sign = carry;
        Slice s = slice((a >> i) & 1, (b >> i) & 1, carry, binv, sel, 0);
        res |= (unsigned)s.out << i;
        if (i == 7) sign_sum = s.sum;
        carry = s.cout;
    }
    *c = carry;
    *v = carry_into_sign ^ carry;
    *n = (int)((res >> 7) & 1);
    *z = res == 0;
    if (op == SLT) return (unsigned)(sign_sum ^ *v);      /* set-less-than: sign of the difference xor overflow */
    return res;
}
 
/* a logarithmic shifter: stage k shifts by 2^k when bit k of the shift amount is 1 */
static unsigned shl8(unsigned x, int amount) {
    for (int k = 0; k < 3; k++)
        if ((amount >> k) & 1) x = (x << (1 << k)) & 0xFF;
    return x;
}
 
int main(void) {
    int z, n, c, v;
    unsigned r = alu8(106, 53, ADD, &z, &n, &c, &v);
    printf("106 + 53 = %u  N=%d C=%d V=%d\n", r, n, c, v);
    r = alu8(106, 53, SUB, &z, &n, &c, &v);
    printf("106 - 53 = %u  N=%d C=%d V=%d\n", r, n, c, v);
    r = alu8(100, (unsigned)(-100) & 0xFF, SUB, &z, &n, &c, &v);
    printf("100 - (-100): bits %02X  N=%d V=%d, so N xor V = %d\n", r, n, v, n ^ v);
    r = alu8(100, (unsigned)(-100) & 0xFF, SLT, &z, &n, &c, &v);
    printf("100 < -100 (signed)? %u\n", r);
    int bad = 0;
    for (unsigned a = 0; a < 256; a++)
        for (unsigned b = 0; b < 256; b++) {
            bad += alu8(a, b, AND, &z, &n, &c, &v) != (a & b);
            bad += alu8(a, b, OR, &z, &n, &c, &v) != (a | b);
            bad += alu8(a, b, ADD, &z, &n, &c, &v) != ((a + b) & 0xFF) || c != (int)((a + b) >> 8);
            bad += alu8(a, b, SUB, &z, &n, &c, &v) != ((a - b) & 0xFF) || c != (a >= b) || z != (a == b);
            bad += alu8(a, b, SLT, &z, &n, &c, &v) != (unsigned)((int8_t)a < (int8_t)b);
        }
    int bad_shift = 0;
    for (unsigned x = 0; x < 256; x++)
        for (int k = 0; k < 8; k++) bad_shift += shl8(x, k) != ((x << k) & 0xFF);
    printf("slice ALU wrong on %d of 327680 operations; shifter wrong on %d of 2048 cases\n", bad, bad_shift);
    return 0;
}

106 + 53 = 159  N=1 C=0 V=1
106 - 53 = 53  N=0 C=1 V=0
100 - (-100): bits C8  N=1 V=1, so N xor V = 0
100 < -100 (signed)? 0
slice ALU wrong on 0 of 327680 operations; shifter wrong on 0 of 2048 cases

Cheat box

Traps and GATE patterns

Connections

The adder, subtractor and their flags are built in adders and subtractors and interpreted in fixed-point arithmetic. The result multiplexer is a multiplexer. The ALU is one block of the datapath, where it sits between the registers and the bus, and its delay sets the clock period that pipelining tries to shorten. Multiplication uses it repeatedly.

PYQs

Self-check

Revision card

References