Chapter 17 of 39

ALU & Datapath

A city has buildings where work gets done (factories, offices) and roads that carry material between them. Traffic lights decide who may use which road at which moment. A processor is organised the same way. The ALU is the factory where numbers are actually added, compared and shifted. The registers are the warehouses. The buses and multiplexers are the roads. Together, the factory, warehouses and roads form the datapath. The traffic lights are the control unit, which we study in the next two chapters.

The ALU (Arithmetic Logic Unit) is the combinational circuit that performs arithmetic, logic and shift operations on its inputs and reports status flags. The datapath is the collection of functional units (ALU, registers, buses, multiplexers, memory interface) that hold and move data while instructions execute.

A useful way to divide any processor: datapath = the parts that store and transform data, control = the part that tells the datapath what to do in each clock cycle. In this chapter we open up the ALU, see how its status flags are produced, and then build two classic datapaths: the single-bus datapath used in many textbooks (Hamacher) and the single-cycle MIPS datapath (Patterson and Hennessy). All flag values, sequences and timings below were checked with a small Python model.


What Is Inside an ALU?

An ALU takes two n-bit operands A and B, a few function-select bits, and produces an n-bit result F plus status flags.

          A (n bits)      B (n bits)
              |               |
     +--------v---------------v--------+
     |  +------------+ +------------+  |
     |  | arithmetic | |   logic    |  |
     |  |    unit    | |    unit    |  |      S (function select)
     |  +-----+------+ +-----+------+  |<------------------
     |        |   +---------+  |       |
     |        |   | shifter |  |       |
     |        |   +----+----+  |       |
     |      +-v--------v-------v-+     |
     |      |   output MUX       |     |
     |      +---------+----------+     |
     +----------------|----------------+
                      v
               F (n bits) + flags C, Z, N, V

All the units compute in parallel; the output multiplexer simply picks the one the select bits ask for. Because it is purely combinational, the ALU has no memory: the result appears a short delay after the inputs change.

The Arithmetic Unit: One Adder, Many Operations

We do not build a separate circuit for add, subtract, increment and decrement. One n-bit parallel adder (see Combinational Circuits: Adders, Multiplexers & Decoders) can do them all if we control what goes into its second input (call it Y) and its carry-in Cin:

   D = A + Y + Cin

   S1 S0 | Y input     | Cin = 0          | Cin = 1
   ------+-------------+------------------+-----------------
   0  0  | B           | A + B     (add)  | A + B + 1
   0  1  | B'  (NOT B) | A + B'           | A + B' + 1 = A - B  (subtract)
   1  0  | all 0s      | A   (transfer)   | A + 1     (increment)
   1  1  | all 1s      | A - 1 (decrement)| A   (transfer)

Why does each row work?

  • A + B' + 1 is A plus the 2's complement of B, which is A − B (see Signed Numbers: Sign-Magnitude, 1's & 2's Complement).

  • "All 1s" is the 2's complement representation of −1, so A + 111...1 = A − 1.

  • A + 111...1 + 1 = A − 1 + 1 = A, another way to transfer A.

The B input logic for each bit is just a 4-to-1 multiplexer (or two gates) choosing Bi, Bi', 0 or 1. This design appears in Mano's textbook as the "arithmetic circuit", and we built it gate by gate in Register Transfer & Micro-operations.

For example, with A = 0110 (6) and B = 0011 (3): S1S0 = 01 with Cin = 1 gives 0110 + 1100 + 1 = 0011 (3 = A − B, carry out discarded), and S1S0 = 11 with Cin = 0 gives 0110 + 1111 = 0101 (5 = A − 1). The full eight-row table with its circuit is worked out in Register Transfer & Micro-operations; here we care about how this block sits inside the ALU.

The Logic Unit and the Shifter

The logic unit performs bitwise operations: each output bit Fi depends only on Ai and Bi. A typical logic unit computes AND, OR, XOR and NOT for every bit position in parallel and uses a 4-to-1 multiplexer per bit to choose one. Other logic operations come for free: clearing a register is A XOR A, and selective complement or mask operations are XOR and AND with a chosen pattern.

The shifter moves bits left or right by one position (or, in a barrel shifter, by any amount in one step). A logical left shift by one doubles an unsigned number; an arithmetic right shift (which copies the sign bit) halves a signed number, rounding toward −∞.

Building an n-bit ALU from Slices

Because every bit position does the same job, an ALU is built from identical one-bit stages (or 4-bit "slices") connected by the carry chain. The classic TI 74181 chip was such a 4-bit ALU slice; four of them made a 16-bit ALU. The carry chain is the slowest part, which is why fast ALUs use carry look-ahead adders.


Status Flags

After an operation the ALU sets condition flags that later instructions (conditional branches, add-with-carry) can test. The four standard ones for an n-bit result F:

Flag

Name

Set when

How it is computed

C

Carry

Unsigned result does not fit

carry out of the most significant bit, cn

Z

Zero

Result is 0

NOR of all result bits

N (or S)

Negative / Sign

Result is negative (signed view)

most significant result bit Fn−1

V (or O)

Overflow

Signed result does not fit

cn XOR cn−1 (carry out of MSB XOR carry into MSB)

C is about unsigned overflow; V is about signed overflow. The ALU computes both because the same adder is used for signed and unsigned numbers; it is the program that decides which flag matters (see Binary Arithmetic & Overflow).

Worked Example: Flags for 4-bit Operations

Subtraction is done as A + B' + 1.

Operation

Result

C

V

N

Z

Signed meaning

0111 + 0001

1000

0

1

1

0

7 + 1 gave −8: signed overflow

1100 + 1100

1000

1

0

1

0

−4 + −4 = −8: correct, carry ignored

1001 + 1010

0011

1

1

0

0

−7 + −6 gave 3: signed overflow

0101 − 0011

0010

1

0

0

0

5 − 3 = 2

0011 − 0101

1110

0

0

1

0

3 − 5 = −2

1000 − 0001

0111

1

1

0

0

−8 − 1 gave 7: signed overflow

0110 − 0110

0000

1

0

0

1

6 − 6 = 0

Look at the subtraction rows: C = 1 when there was no borrow (A ≥ B as unsigned numbers), and C = 0 when a borrow occurred (3 − 5). This is the natural output of an A + B' + 1 adder, and ARM uses exactly this convention. x86 does the opposite: its carry flag is set when a subtraction borrows. So "carry after subtraction" depends on the processor; state the convention in exams.


The Datapath

An ALU on its own does nothing useful. It needs registers to feed it, a place to put results, and a connection to memory. The datapath wires all of these together. Two registers sit at the boundary to memory:

  • MAR (memory address register) holds the address sent to memory.

  • MDR (memory data register) holds the word read from or about to be written to memory.

Other key registers are PC (address of the next instruction), IR (the instruction being executed) and the general-purpose registers.

Single-Bus Datapath

In the simplest organisation, every register is connected to one shared internal bus. Each register Ri has two control signals: Riin loads it from the bus, and Riout places its contents on the bus (through tri-state gates, so only one register drives the bus at a time).

  internal processor bus (one value per clock cycle)
  ==+=====+=====+=====+=====+=====+=====+================+=========+=====
    |     |     |     |     |     |     |                |         ^
  +-+-+ +-+-+ +-+-+ +-+-+ +-+-+     +-+--+             +-v-+       |
  |PC | |MAR| |MDR| |IR | |R0 | ... |Rn-1|             | Y |       |
  +---+ +-+-+ +-+-+ +---+ +---+     +----+             +-+-+       |
          |     |                         constant 4 --+ |         |
          v     ^                                      v v         |
     address   data                                  +-----+       |
     lines     lines  (to/from memory)    Select4 -->| MUX |       |
                                          SelectY    +--+--+       |
                                                        | A        |
                                 bus value ------------)|---+ B    |
                                                        v   v      |
                                                      +-------+    |
                                          Add, Sub -->|  ALU  |    |
                                                      +---+---+    |
                                                          v        |
                                                        +---+ Zout |
                                                        | Z |------+
                                                        +---+

Why the extra registers Y and Z? The ALU needs two operands at the same time, but a single bus can carry only one value per clock cycle. So the first operand is parked in Y in one cycle; in the next cycle the second operand comes over the bus directly. The ALU result cannot go straight back onto the bus (the bus is busy carrying the second operand), so it is captured in Z and put on the bus in the following cycle. The MUX in front of the ALU chooses either Y or the constant 4 (used to increment PC by 4 bytes).

Control Sequence for ADD R1, (R3)

The instruction ADD R1, (R3) means R1 ← R1 + M[R3]. Each numbered step is one clock cycle; the listed signals are active during that step. WMFC means "wait for memory function completed": the step does not finish until memory signals that the read is done.

Step

Active control signals

What happens

1

PCout, MARin, Read, Select4, Add, Zin

Send PC to memory to fetch the instruction; at the same time compute PC + 4 into Z.

2

Zout, PCin, Yin, WMFC

PC ← PC + 4 (also copied into Y, useful for branches); wait for memory.

3

MDRout, IRin

IR ← the fetched instruction. Fetch is complete.

4

R3out, MARin, Read

Send operand address R3 to memory.

5

R1out, Yin, WMFC

Park the first operand R1 in Y while memory reads.

6

MDRout, SelectY, Add, Zin

Z ← Y + MDR = R1 + M[R3].

7

Zout, R1in, End

R1 ← Z; End resets the step counter to start the next fetch.

Steps 1 to 3 are the same for every instruction; steps 4 onward depend on the opcode. Notice the overlap trick in steps 1 and 2: the ALU computes PC + 4 while memory is busy, so no extra cycle is spent on incrementing PC.

A register-only add, ADD R1, R2 (R1 ← R1 + R2), needs fewer execute steps:

Steps 1-3: fetch (as above)
Step 4:    R1out, Yin
Step 5:    R2out, SelectY, Add, Zin
Step 6:    Zout, R1in, End

Multiple-Bus Datapaths

The single bus is cheap but slow: only one transfer per cycle. With three buses, two source buses (A and B) feed the ALU and a third bus (C) carries the result back to the register file, so a whole register-to-register operation fits in one cycle. The register file needs two read ports and one write port, and Y and Z are no longer needed.

For ADD R6, R4, R5 (R6 ← R4 + R5), a three-bus datapath (with an incrementer for PC) needs:

Step 1: PCout, R=B, MARin, Read, IncPC   ; send PC to memory, PC ← PC + 4
Step 2: WMFC                             ; wait for memory
Step 3: MDRoutB, R=B, IRin               ; IR ← instruction (ALU just passes B)
Step 4: R4outA, R5outB, SelectA, Add, R6in, End

"R=B" means the ALU simply passes its B input through. The same three-operand add on the single-bus datapath needs 6 steps (3 fetch + R4out, Yin; R5out, SelectY, Add, Zin; Zout, R6in, End).

Feature

Single bus

Two bus

Three bus

Transfers per cycle

1

2 (one in, one out)

3 (two sources, one result)

Temporary registers needed

Y and Z

Usually one (Y or Z)

None

Register file ports

1 shared

1 read + 1 write

2 read + 1 write

Steps for ADD R6, R4, R5 (with fetch)

6

in between

4

Cost

Lowest

Medium

Highest


The Single-Cycle MIPS Datapath

RISC processors use a different style: a datapath designed so that each instruction flows through it from left to right. The famous teaching example is the single-cycle MIPS datapath, which executes R-type instructions, lw, sw and beq, each in exactly one (long) clock cycle.

 +----+   +-------------+   +---------------+   +-----+   +--------+   +-----------+
 | PC |-->| Instruction |-->| Register file |-->| ALU |-->|  Data  |-->| write-back|
 +----+   |   memory    |   | (2 read ports)|   +-----+   | memory |   |   MUX     |
   ^      +-------------+   +---------------+     ^       +--------+   +-----+-----+
   |                              ^  imm16        |                          |
   |   PC+4 / branch target MUX   |  sign-extend--+ (ALUSrc MUX)             |
   +------------------------------+--------------------------------- writes Rd/Rt
 Stages inside one cycle: fetch -> decode/read registers -> ALU -> memory -> write back

The main elements are:

  • PC and an adder computing PC + 4.

  • Instruction memory (separate from data memory so both can be used in the same cycle).

  • Register file: 32 registers, two read ports (rs, rt) and one write port.

  • Sign-extend unit: turns the 16-bit immediate into 32 bits.

  • ALU controlled by a 4-bit ALU control code.

  • Data memory for lw/sw.

  • Multiplexers wherever a unit can receive input from two places, each controlled by a control signal.

Main Control Signals

Signal

Effect when 0

Effect when 1

RegDst

Destination register is rt (bits 20-16)

Destination register is rd (bits 15-11)

ALUSrc

Second ALU operand is register rt

Second ALU operand is the sign-extended immediate

MemtoReg

Value written to register comes from the ALU

Value written comes from data memory

RegWrite

No register write

Write the register file

MemRead

-

Read data memory

MemWrite

-

Write data memory

Branch

PC ← PC + 4

PC ← branch target if the ALU's Zero output is 1

The settings for each instruction type (X = don't care):

Instruction

RegDst

ALUSrc

MemtoReg

RegWrite

MemRead

MemWrite

Branch

ALUOp

R-type

1

0

0

1

0

0

0

10

lw

0

1

1

1

1

0

0

00

sw

X

1

X

0

0

1

0

00

beq

X

0

X

0

0

0

1

01

RegDst and MemtoReg are don't-cares for sw and beq because RegWrite = 0: whatever those multiplexers choose is never written anywhere.

ALUOp is a 2-bit hint to a small second-level ALU control unit: 00 means "add" (address calculation for lw/sw), 01 means "subtract" (beq compares by subtracting and checking Zero), and 10 means "look at the funct field". For R-type instructions the funct field selects the operation: add → 0010, sub → 0110, and → 0000, or → 0001, slt → 0111.

How Each Instruction Uses the Datapath

  • add $t0, $t1, $t2: read $t1 and $t2, ALU adds, result written to rd = $t0. Data memory unused.

  • lw $t0, 8($s1): read $s1, ALU computes $s1 + 8, data memory read at that address, data written to rt = $t0. Uses every unit, so it is the longest instruction.

  • sw $t0, 8($s1): ALU computes $s1 + 8, the value of $t0 (read port 2) is written to memory. No register write.

  • beq $t0, $t1, L: ALU subtracts; if Zero = 1, PC ← PC + 4 + (sign-extended offset × 4). No memory or register write.

Worked Example: Clock Period of a Single-Cycle Datapath

Suppose the units have these delays (ignore multiplexers, PC adder and wires): instruction memory 250 ps, register read 150 ps, ALU 200 ps, data memory 300 ps, register write 100 ps.

Instruction

Units on its path

Total

lw

250 + 150 + 200 + 300 + 100

1000 ps

sw

250 + 150 + 200 + 300

900 ps

R-type

250 + 150 + 200 + 100

700 ps

beq

250 + 150 + 200

600 ps

In a single-cycle design every instruction gets the same clock, so the clock period must fit the slowest one: 1000 ps (1 GHz). Even an R-type instruction that is ready after 700 ps waits the full 1000 ps.

If the program mix is 25% lw, 10% sw, 45% R-type and 20% beq, an imaginary clock that adapted to each instruction would average 0.25×1000 + 0.10×900 + 0.45×700 + 0.20×600 = 775 ps. The single-cycle design is therefore 1000 / 775 ≈ 1.29 times slower than it would need to be. This waste is the motivation for multi-cycle designs and, ultimately, for pipelining (covered later in Pipelining Basics).

Be careful: splitting into shorter cycles is not automatically a win. If we used a 300 ps clock (the slowest unit) with lw taking 5 cycles, sw and R-type 4 and beq 3, the same mix gives CPI = 0.25×5 + 0.10×4 + 0.45×4 + 0.20×3 = 4.05 and 4.05 × 300 = 1215 ps per instruction, worse than single-cycle. A multi-cycle design wins only when the unit delays are well balanced. Its real advantages are reusing hardware (one memory, one ALU) and enabling pipelining.


Solved Problems

Problem 1: Flags

An 8-bit ALU adds 0x7F and 0x01. Give the result and C, Z, N, V.

Solution. 0111 1111 + 0000 0001 = 1000 0000 (0x80). There is no carry out of bit 7, so C = 0. Result non-zero, Z = 0. MSB is 1, N = 1. The carry into bit 7 is 1 and out of bit 7 is 0, so V = 1 XOR 0 = 1: 127 + 1 does not fit in 8-bit signed.

Problem 2: Counting Clock Cycles

On the single-bus datapath, memory needs 2 extra clock cycles after each Read before MFC arrives (each WMFC step therefore lasts 3 cycles). How many cycles does ADD R1, (R3) take?

Solution. The control sequence has 7 steps, two of which (steps 2 and 5) contain WMFC. Each WMFC step adds 2 cycles: 7 + 2 × 2 = 11 cycles.

Problem 3: Stuck-at Faults in MIPS Control

In the single-cycle MIPS datapath, which of R-type, lw, sw and beq still work if (a) ALUSrc is stuck at 0, (b) RegDst is stuck at 0, (c) MemtoReg is stuck at 0?

Solution.

  • (a) ALUSrc = 0 always selects register rt instead of the immediate. R-type and beq need 0, so they work. lw and sw compute rs + R[rt] instead of rs + offset, so they fail.

  • (b) RegDst = 0 always writes to rt. lw needs this and works; sw and beq do not write and work. R-type writes its result into rt instead of rd, so it fails.

  • (c) MemtoReg = 0 always writes the ALU result. R-type works; sw and beq do not write. lw writes the computed address instead of the loaded data, so it fails.

Problem 4: Which ALU Operation?

For the arithmetic circuit above, what S1, S0, Cin give A − 1 and A − B?

Solution. A − 1: Y = all 1s, Cin = 0, so S1S0 = 11, Cin = 0. A − B: Y = B', Cin = 1, so S1S0 = 01, Cin = 1.


Common Mistakes

  • Confusing C and V. C is unsigned overflow (carry out of the MSB); V is signed overflow (carry into MSB XOR carry out of MSB).

  • Assuming one convention for carry after subtraction. An A + B' + 1 adder gives C = 1 for "no borrow" (ARM); x86 sets CF on borrow.

  • Forgetting Y and Z in single-bus sequences. Only one value can be on the bus per cycle, so one operand must wait in Y and the result must wait in Z.

  • Putting two "out" signals in the same single-bus step. R1out and R2out together would make two registers drive the bus at once.

  • Clocking a single-cycle datapath at the average delay. The clock must fit the slowest instruction (usually lw).

  • Treating don't-cares as zeros. In the MIPS control table, RegDst and MemtoReg are X for sw and beq because nothing is written.


Interview Questions

What is the difference between the datapath and the control unit?

The datapath holds and transforms data (registers, ALU, buses, multiplexers, memory interface). The control unit generates the signals that tell the datapath which transfers and operations to perform in each clock cycle.

How can one adder perform subtraction, increment and decrement?

By controlling its second input and carry-in: B' with Cin = 1 gives A − B; all 0s with Cin = 1 gives A + 1; all 1s with Cin = 0 gives A − 1.

How is the overflow flag computed?

V = carry into the most significant bit XOR carry out of it. Equivalently, overflow occurs when two operands with the same sign produce a result with a different sign.

Why does a single-bus datapath need the Y and Z registers?

The ALU needs two inputs at once, but the bus carries one value per cycle, so the first operand is held in Y. The result is held in Z because the bus is busy carrying the second operand during the ALU operation.

Why does the single-cycle MIPS datapath have separate instruction and data memories?

Because lw and sw must fetch the instruction and access data in the same clock cycle; a single memory with one port cannot do both.

What decides the clock period of a single-cycle processor?

The delay of the slowest instruction's path, typically lw (instruction memory, register read, ALU, data memory, register write).


Summary

  • The ALU is a combinational block with an arithmetic unit, a logic unit and a shifter, chosen by function-select bits. One parallel adder plus B-input logic and Cin gives add, subtract, increment, decrement and transfer.

  • Flags: C (carry out, unsigned overflow), Z (result zero), N (MSB), V (cn XOR cn−1, signed overflow).

  • The datapath connects registers, ALU and memory (via MAR and MDR). A single-bus datapath needs Y and Z and several steps per instruction (7 for ADD R1, (R3)); a three-bus datapath can do a register add in one execute step.

  • The single-cycle MIPS datapath runs each instruction in one cycle, steered by RegDst, ALUSrc, MemtoReg, RegWrite, MemRead, MemWrite, Branch and ALUOp. Its clock must fit the slowest instruction, which wastes time on the others.

  • The next chapter, Hardwired Control Unit, shows how the control signals in these sequences are generated by logic circuits.