Datapath: Adders and the ALU

With CMOS gates in hand we can finally compute. The beating heart of every processor's datapath is the Arithmetic Logic Unit, and the beating heart of the ALU is an adder. Addition is not just for arithmetic: subtraction, address calculation, comparison, and loop counters all flow through the same adder. So the adder's speed is, to a first approximation, the CPU's speed — and there is one villain that sets it: the carry. Watching how architects wrestle the carry chain from a slow ripple into a fast parallel tree is one of the most satisfying stories in the whole field.

The full adder: one bit at a time

Adding two n-bit numbers is done bit by bit, exactly as you add decimal digits by hand — each column produces a digit and maybe a carry into the next. The building block is the full adder: it takes two bits a_i, b_i and an incoming carry c_i, and produces a sum bit and an outgoing carry:

s_i = a_i \oplus b_i \oplus c_i, \qquad c_{i+1} = a_i b_i + c_i\,(a_i \oplus b_i).

The carry-out is a majority function: a carry leaves this column when at least two of the three inputs are 1. That second equation — the carry — is the one that will cause all the trouble, because the carry c_{i+1} of one column is the carry input of the next.

The ripple-carry adder — correct, and slow

Chain n full adders, feeding each carry-out into the next carry-in, and you have a ripple-carry adder. It is delightfully simple and completely correct. Its problem is in the name: the carry has to ripple all the way from the least-significant bit to the most-significant one before the top bit knows its final value.

In the worst case — think 1111 + 0001, where a carry born at the bottom flips every single bit on its way up — the carry must pass through all n full adders in turn. The delay is therefore linear in the width:

t_{\text{ripple}} \approx n \cdot t_{\text{carry}} = O(n).

For a 64-bit adder that is 64 gate-delays stacked end to end — the longest path in the machine, and the thing that would set your clock period if you did nothing about it. The carry chain is the critical path.

Carry-lookahead: compute the carries in parallel

The fix is to stop waiting for the ripple and predict each carry directly from the inputs. For each column define two one-bit signals:

Then the carry recurrence unrolls: c_{i+1} = g_i + p_i c_i, and substituting repeatedly gives every carry as a direct function of the inputs, with no waiting:

c_{i+1} = g_i + p_i g_{i-1} + p_i p_{i-1} g_{i-2} + \dots + p_i p_{i-1}\cdots p_0\,c_0.

Built as a tree of these terms, a carry-lookahead adder computes all carries in O(\log n) depth instead of O(n). The price is more gates and wiring — you have traded area for speed, the deal an architect makes every day.

Carry-select: hedge both bets

A third trick is pure cunning. Split the number into blocks; for each upper block, compute its sum twice in parallel — once assuming the carry coming in is 0, once assuming it is 1 — before you know which is true. When the real carry finally arrives from below, a single multiplexer selects the correct precomputed answer instantly. You have hidden the carry latency behind speculative work, at roughly double the adder hardware per block. Modern high-performance adders blend lookahead and select ideas (Kogge-Stone, Brent-Kung, and friends) to hit O(\log n) at a tolerable area.

The ALU: a multiplexed bank of operations

Zoom out from the adder to the whole ALU. It is not one clever circuit but a bank of simple ones running in parallel on the same two operands: the adder, a bitwise AND, a bitwise OR, an XOR, a shifter, a comparator. All of them compute at once; a multiplexer, steered by the instruction's opcode, throws away every result but the one you asked for. Subtraction is not a separate unit — it reuses the adder by feeding it the inverted second operand with a carry-in of 1, i.e. two's-complement negation (a - b = a + \overline{b} + 1). Comparison (a < b) is just a subtraction whose sign bit you inspect. Because the adder is the deepest of these units, its carry path is usually the ALU's critical path too.

// A tiny ALU: every unit computes in parallel, a "mux" (the opcode) selects one result. // We also model why RIPPLE is slow: worst-case carry delay grows linearly with width n. function fullAdder(a: number, b: number, cin: number): [number, number] { const s = a ^ b ^ cin; const cout = (a & b) | (cin & (a ^ b)); // majority return [s, cout]; } function rippleAdd(x: number, y: number, n: number): number { let carry = 0, sum = 0; for (let i = 0; i < n; i++) { const [s, c] = fullAdder((x >> i) & 1, (y >> i) & 1, carry); sum |= s << i; carry = c; } return sum; } const n = 8; const a = 0b1111, b = 0b0001; console.log(`${a} + ${b} = ${rippleAdd(a, b, n)} (a carry born at bit 0 ripples all the way up)`); // Delay models, in gate-delays, for an n-bit add: for (const w of [8, 16, 32, 64]) { const ripple = 2 * w; // ~2 gate delays per stage, O(n) const lookahead = Math.ceil(2 * Math.log2(w)) + 4; // O(log n) tree console.log(`n=${w}: ripple ≈ ${ripple} gate-delays, lookahead ≈ ${lookahead}`); }

You could — a slow ripple adder is perfectly correct, and early microprocessors used them. But the adder sits on the critical path of nearly every instruction, so its delay sets the whole chip's clock period via T_{\text{clk}} \ge t_{\text{logic}} + \dots. Halving the adder delay can lift the clock frequency of the entire processor. That is why decades of research went into carry structures with names like Kogge-Stone and Brent-Kung, and why a modern 64-bit adder is a carefully tuned parallel-prefix tree rather than a humble ripple. The carry is worth fighting for because everything waits on it.

It is tempting to think doubling an adder from 32 to 64 bits merely doubles the hardware. For a ripple adder it also doubles the delay — the carry chain got twice as long, and that extra delay lands squarely on your critical path and caps your clock. This is precisely why you cannot naively scale a ripple adder to 64 or 128 bits: the fix is a different topology (lookahead / prefix), which keeps delay at O(\log n) even as width grows. Width costs area everywhere, but it costs time only if you let the carry ripple.

Where this sits in the machine

The ALU is the "execute" stage of the datapath — the place where operands, having been fetched from the register file, are actually crunched. Everything upstream (fetch, decode, register read) exists to feed it, and everything downstream (write-back, memory) exists to store what it produced. Next we build the elements that hold those operands and results steady between clock ticks — the registers and flip-flops — and then we return to that carry chain to nail down exactly how it sets the clock.