Systems and hardwareDive 01 of 06

How a microprocessor works

From a line of C to the transistor: the instruction set contract, a RISC-V CPU you can clock by hand, the datapath, pipelines and caches, adders built from logic gates, and the switch at the bottom of it all.

Levels
9
Reading
50 min
Depth
Idea to Silicon
Published

Level 01/09Idea

A machine that follows instructions

Here is a function you could write in your first week of C. It adds up an array of integers.

sum.c
int sum(int *a, int n) {
  int s = 0;
  for (int i = 0; i < n; i++)
    s += a[i];
  return s;
}

Call it with the array {3, 1, 4, 1, 5} and it returns 14. Nothing about that is surprising, and yet the machine that produces the 14 has never seen a line of C. It has no idea what a for loop is, what int means, or that a is an array. It is a slab of silicon with a few billion switches on it, wired so that it does one thing over and over: read a number from memory, treat that number as an instruction, carry it out, and move on to the next one.

This dive follows sum all the way down. We will compile it, read the machine code bit by bit, run it on a processor you can clock by hand, look at the wires that carry each value, and keep descending until we reach the transistor, the switch everything else is built from. The same five numbers and the same answer, 14, come with us the whole way.

The problem a processor solves

You could build a circuit that only sums arrays. People did build fixed-function machines like that, and they still do when one job matters enough (a video decoder, a network switch, a Bitcoin miner). The catch is that a fixed-function circuit does one job. Rewiring it for a new job means building new hardware.

A general-purpose processor turns the problem inside out. Instead of wiring the algorithm into the hardware, you wire in a small set of very simple operations (add two numbers, load a word from memory, jump somewhere else if two values differ) and then describe the algorithm as a list of those operations. The list is just data. Change the list and the same chip does something completely different: sums arrays, renders this page, compiles a kernel.

The crucial design choice, described in John von Neumann's 1945 draft report on the EDVAC (the idea came out of a team, but his name stuck) and shared by almost every computer since, is to keep that list in the same memory as the data it works on. Instructions are numbers. A program can be loaded from disk like any other file, generated by a compiler, even written by another program. That is the A computer that keeps its program in the same read-write memory as its data, so instructions can be loaded and changed like any other bytes. computer.

The two halves of a stored-program machine, paused partway through sum. Memory holds the compiled instructions (blue) and the array (amber) side by side. The program counter, PC, holds the address of the next instruction: 0x020, the load that reads a[0].

Everything inside the processor box exists to serve one loop. The A register that holds the memory address of the next instruction to run. RISC-V calls it pc; x86 calls it the instruction pointer, rip. says where the next instruction lives. The processor fetches the instruction at that address, works out what it asks for, does it, and updates the program counter, usually to the next instruction in memory, sometimes somewhere else. Then it does it again, billions of times per second.

A processor is a loop in hardware: fetch the instruction the program counter points at, do what it says, pick the next program counter, repeat.

Level 02/09Interface

The instruction set contract

To run sum, a compiler has to rewrite it in the processor's own vocabulary. That vocabulary is the Instruction set architecture: the specification of the instructions, registers, memory model and encodings that software can rely on. It says what each instruction does, not how the hardware does it., or ISA. This dive uses RISC-V, an open ISA designed at UC Berkeley starting in 2010, in its smallest form: RV32I, the 32-bit base integer instruction set. RV32I has 40 instructions, few enough to read on one page and clean enough that every bit of every instruction can be explained.

Here is what clang -O2 --target=riscv32 -march=rv32i makes of our function. The comments and label names are mine; the instructions are the compiler's.

sum.c
int sum(int *a, int n) {
  int s = 0;
  for (int i = 0; i < n; i++)
    s += a[i];
  return s;
}
sum.s · clang -O2, RV32I
sum:
        li      a2, 0             # s = 0
        blez    a1, .done         # if (n <= 0) skip the loop
        slli    a1, a1, 2         # n * 4: bytes, not elements
        add     a1, a0, a1        # end = a + n
.loop:
        lw      a3, 0(a0)         # load *a
        addi    a0, a0, 4         # a++ (one word = 4 bytes)
        add     a2, a3, a2        # s += *a
        bne     a0, a1, .loop     # keep going until a == end
.done:
        mv      a0, a2            # return value goes in a0
        ret
address · instruction word · assembly
0010:  00000613    li a2, 0
0014:  00b05e63    blez a1, .done
0018:  00259593    slli a1, a1, 2
001c:  00b505b3    add a1, a0, a1
0020:  00052683    lw a3, 0(a0)
0024:  00450513    addi a0, a0, 4
0028:  00c68633    add a2, a3, a2
002c:  feb51ae3    bne a0, a1, .loop
0030:  00060513    mv a0, a2
0034:  00008067    ret

A few things happened in translation. The variable i is gone: the compiler realised it only needed a[i], so it walks a pointer through the array instead and stops when the pointer reaches the end, computed once as a + n * 4 (each int is 4 bytes). The arguments arrive in registers named a0 and a1, and the result leaves in a0. Four instructions form the loop body: load, bump the pointer, add, branch back.

Some of those instructions are not real. li, mv, blez and ret are An assembler shorthand that expands into one or more real instructions. The hardware never sees it., conveniences the assembler expands into real ones: li a2, 0 is addi a2, zero, 0, blez a1, .done is bge zero, a1, .done, and ret is jalr zero, 0(ra). The ISA stays small; the assembler makes it pleasant.

What the contract says

The ISA is a contract between software and hardware. If a compiler emits only valid RV32I instructions, any RV32I processor must produce exactly the results the specification describes, whether it is a tiny microcontroller or a big out-of-order core. The contract covers:

  • Registers. Thirty-two of them, x0 to x31, each 32 bits wide in RV32I. x0 is wired to zero: writes to it are discarded and reads always return 0, which turns out to be enormously handy. The names a0, sp, ra and friends are aliases from the calling convention, a software agreement layered on top.
  • Memory. A flat array of bytes, each with a 32-bit address. Multi-byte values are stored The least significant byte goes at the lowest address. 0x00c68633 is stored as the bytes 33 86 c6 00..
  • The program counter. Not one of the 32 registers. Only jumps and branches can change it directly.
  • Instructions. What each one does and exactly how it is encoded as bits.

Just as important is what the contract leaves out: how many instructions run at once, how deep the pipeline is, how big the caches are, how fast anything happens. That is the Microarchitecture: one particular hardware design that implements an ISA. Different microarchitectures can run the same binaries at very different speed and cost., and the rest of this dive is mostly about it.

The ISA specifiesThe microarchitecture decides
32 registers, x0 always zeroHow many physical registers exist behind them (often hundreds)
add rd, rs1, rs2 writes the 32-bit sum to rdWhich adder circuit computes it and in which cycle
Instructions appear to run one at a time, in orderHow many really run at once, and in what order
lw reads 4 bytes, little-endianCache sizes, line sizes, prefetching, latency
The bit encoding of every instructionHow the decoder is built

Six ways to pack 32 bits

Every RV32I instruction is exactly 32 bits, and there are only six layouts, called formats. Every format puts the 7-bit opcode in the lowest bits, so the first thing the hardware does with an instruction is look there to learn which layout applies.

Format312524201915141211760
R-typeadd, sub, and, sll…funct7rs2rs1funct3rdopcode
I-typeaddi, lw, jalr…imm[11:0]rs1funct3rdopcode
S-typesw, sh, sbimm[11:5]rs2rs1funct3imm[4:0]opcode
B-typebeq, bne, blt…12imm[10:5]rs2rs1funct3imm[4:1]11opcode
U-typelui, auipcimm[31:12]rdopcode
J-typejal20imm[10:1]11imm[19:12]rdopcode
The six RV32I formats. Register fields (rd, rs1, rs2) never move, and the sign bit of every immediate is always bit 31. Both choices exist to make the hardware simpler, even where they make the encoding look scrambled, as in B and J.

Look at where the register numbers sit. rs1 is always bits 19 to 15, rs2 always 24 to 20, rd always 11 to 7. A decoder can start reading the register file before it even knows what the instruction is. Each register field is 5 bits, exactly enough to name 25 = 32 registers.

The B and J formats look as if someone shuffled the immediate on purpose, and someone did. The bits are placed so that most immediate bits land in the same instruction position in every format, which saves multiplexers in the immediate generator. Branch and jump offsets also skip bit 0 entirely: instructions are always at least 2 bytes apart, so a target address always ends in 0 and storing that bit would waste space.

Try it. Type any RV32I instruction and watch it turn into bits. Branch and jump targets have to be numeric byte offsets (write bne a0, a1, -12, not .loop), since a label only means something at a known address. The pseudo-instructions mv, nop, ret, j, blez, beqz and bnez work, as does li with a value that fits in 12 bits; larger constants need lui plus addi.

As one 32-bit word
As bytes in memory, lowest address first
A real RV32I assembler running in your browser. It checks register names and immediate ranges the way an assembler would and produces the same words as LLVM's.

The 32-bit word 0x00c68633 is how we write the number, most significant digit first. Memory stores it the other way round, lowest byte at the lowest address. Address 0x28, where this add lives, holds 33; address 0x2b holds 00.

33001100118610000110C6110001100000000000
  1. Byte 0x28opcode 0110011 plus the low bit of rd
  2. Byte 0x29rest of rd, funct3, low bit of rs1
  3. Byte 0x2arest of rs1, low four bits of rs2
  4. Byte 0x2btop bit of rs2 and funct7 (zero for add)
add a2, a3, a2 as four bytes in memory, lowest address first. The opcode lives in the low 7 bits of the first byte.
Check yourselfThe branch bne a0, a1, .loop jumps back 12 bytes. Why does the B-type format store imm[12:1] and never bit 0?

Other contracts

RISC-V is not the only way to write this contract. The two ISAs you are most likely to be running right now made very different choices.

x86-64AArch64 (Arm)RV32I / RV64I
Instruction length1 to 15 bytesAlways 4 bytes4 bytes; 2 with the C extension
General-purpose registers16 (32 with the new APX extension)31, plus a zero register31, plus x0
Arithmetic on memoryYes: add eax, [rdi]No: load, then addNo: load, then add
DecodingHard: find where each instruction ends firstEasyEasy
Who controls itIntel and AMDArm, licensedRISC-V International, open

The labels CISC and RISC (complex and reduced instruction set) describe where each family started more than how it is built today. Modern x86 cores translate their variable-length instructions into simpler internal operations, called micro-ops, that look a lot like RISC instructions. The contract and the machine underneath it have drifted apart, which is exactly what the contract allows.

Level 03/09Machine

Fetch, decode, execute

The ISA tells us everything a program can see: the program counter, 32 registers and memory. Together that is the machine's Everything an ISA lets software observe. After each instruction, the architectural state must look as if that instruction, and only that one, has just run.. Running a program means changing that state one instruction at a time.

Every instruction goes through the same steps:

  1. Fetch. Read the 32-bit word at the address in the program counter.
  2. Decode. Split it into fields, read the source registers it names, and build the immediate.
  3. Execute. Do the arithmetic in the Arithmetic logic unit: the circuit that adds, subtracts, compares, shifts and does bitwise logic on two inputs.: a sum, a comparison, or an address calculation for a load or store.
  4. Memory. Loads read data memory and stores write it. Everything else skips this step.
  5. Write back. Put the result into the destination register.
  6. Next PC. Usually PC + 4. Branches and jumps can pick a different address.

Below is an RV32I processor (every RV32I instruction except fence), written in a few hundred lines of TypeScript, loaded with sum, a tiny main that calls it with our array, and an ebreak that stops the simulator. Each press of the button is one clock cycle, and in this simple machine one cycle runs one whole instruction. The decoder and executor are the same code that powers the encoder above, so the bits you see are the bits that ran.

Cycle
0
PC
0x000

The machine is reset. PC is 0, so the first instruction it will run is the one at address 0x000.

Program memory

  1. main:0x00010000513li a0, 256# a = the array
  2. 0x00400500593li a1, 5# n = 5
  3. 0x008008000efjal ra, sum# call sum
  4. 0x00c00100073ebreak# stop the simulator
  5. sum:0x01000000613li a2, 0# s = 0
  6. 0x01400b05e63blez a1, .done# n <= 0?
  7. 0x01800259593slli a1, a1, 2# n * 4
  8. 0x01c00b505b3add a1, a0, a1# end = a + n
  9. .loop:0x02000052683lw a3, 0(a0)# load *a
  10. 0x02400450513addi a0, a0, 4# a++
  11. 0x02800c68633add a2, a3, a2# s += *a
  12. 0x02cfeb51ae3bne a0, a1, .loop# a != end?
  13. .done:0x03000060513mv a0, a2# return s
  14. 0x03400008067ret# back to main

Last cycle

  1. Fetch–
  2. Decode–
  3. Execute–
  4. Memory–
  5. Write back–
  6. Next PC–

Register file read written

  1. x0zero0
  2. x1ra0
  3. x2sp0
  4. x3gp0
  5. x4tp0
  6. x5t00
  7. x6t10
  8. x7t20
  9. x8s00
  10. x9s10
  11. x10a00
  12. x11a10
  13. x12a20
  14. x13a30
  15. x14a40
  16. x15a50
  17. x16a60
  18. x17a70
  19. x18s20
  20. x19s30
  21. x20s40
  22. x21s50
  23. x22s60
  24. x23s70
  25. x24s80
  26. x25s90
  27. x26s100
  28. x27s110
  29. x28t30
  30. x29t40
  31. x30t50
  32. x31t60

Data memory

  1. 0x1003a[0]
  2. 0x1041a[1]
  3. 0x1084a[2]
  4. 0x10c1a[3]
  5. 0x1105a[4]
A working RV32I core running sum on {3, 1, 4, 1, 5}. The highlighted program line is the next instruction; the panel on the right shows what the last cycle did, stage by stage. Registers read in that cycle are amber and the register written is teal.

Clock through the first loop iteration and watch for these things:

  • jal ra, sum does two jobs at once. It saves the address of the instruction after it (0x00c) in ra, then jumps. ret at the end jumps back to whatever ra holds. That is the entire hardware mechanism behind a function call.
  • lw a3, 0(a0) uses the ALU to compute an address (a0 + 0), then reads memory there. Loads and stores always compute addresses this way: base register plus a 12-bit signed offset.
  • bne a0, a1, .loop compares two registers and, if they differ, sets the next PC to its own address minus 12. The loop is nothing more than a branch with a negative offset.
  • x0 never changes. When li a2, 0 (really addi a2, zero, 0) reads it, it gets 0, which is how RISC-V gets a "load constant" instruction for free.

Run to the end and the machine halts after 30 cycles with 14 in a0. Three instructions in main set up the call, four at the top of sum prepare the loop, five iterations take four each, two more return, and ebreak ends it: 30 instructions, 30 cycles.

Check yourselfHow many times does the bne instruction at 0x02c execute while summing the five-element array, and how many of those are taken?

Level 04/09Machine

The datapath, wire by wire

The simulator's step() function is a few dozen lines of TypeScript with a switch on the opcode. Hardware has no switch statement and no notion of "first do this, then that". It has wires, and circuits that compute a new output whenever their inputs change. The arrangement of those circuits that carries out instructions is called the The part of a processor that moves and transforms data: registers, ALU, multiplexers, memories and the wires between them. The control unit tells it what to do each cycle..

A datapath needs three kinds of parts:

  • State elements that remember: the PC, the register file (two read ports and one write port, so an add can read two registers and write a third in the same cycle), the instruction memory and the data memory.
  • Combinational logic that computes: an adder for PC + 4, another for branch targets, the ALU, the immediate generator that reassembles those scrambled immediate bits, and Multiplexer: a circuit that picks one of several inputs and passes it to its output, according to a select signal. that choose between alternatives.
  • Control: a block that looks at the opcode and function fields and sets the select lines and write enables for everything else.

The simplest arrangement is a single-cycle design, the machine the simulator imitates. On each rising edge of the clock, the PC, the destination register and any memory write all update at once. Between edges, the new PC value ripples through the logic from left to right until every wire has settled, ready for the next edge. Pick an instruction to see which wires it uses. The values are taken from the second trip through the loop, computed by the same simulator.

Single-cycle RV32I datapath. The program counter feeds the instruction memory and an adder that computes PC + 4. The instruction's fields go to the control unit, the register file and the immediate generator. Register values and the immediate feed the ALU, whose result goes to data memory or straight to the write-back multiplexer, which writes the destination register. A second adder computes branch and jump targets, and a multiplexer picks the next PC. Wires used by the selected instruction are highlighted.01PC+4InstructionmemoryaddrControlRegistersrs1rs2rdwrite datadata 1data 2Imm gen01ALU=0+branch?Datamemoryaddrwriteread012
Control signals for the selected instruction
RegWriteALUSrcALUOpMemReadMemWriteWbSelPCSel
A single-cycle RV32I datapath, simplified. Highlighted wires carry values the selected instruction needs; dashed tags show what the control unit sets. On a narrow screen, scroll the diagram sideways.

Click through the six and something odd stands out: the hardware does almost everything, every cycle. It reads two registers even for jal, which uses neither. It computes PC + 4 even when a branch will throw it away. The immediate generator produces a value from whatever bits are in the immediate positions, even for an R-type instruction that has no immediate. Hardware is parallel by default. "Not doing" something means ignoring its result: a multiplexer picks a different input, or a write enable stays low.

In hardware, every circuit computes all the time. The control signals do not start or stop work; they decide which results get kept.

The control unit is a lookup table

The control unit sounds like the clever part, but for a single-cycle machine it is a fixed function from a handful of instruction bits (the 7-bit opcode, funct3, and one bit of funct7) to a handful of signals. You could write it as a truth table with a row per instruction, and hardware tools turn exactly such a table into gates. The table under the diagram shows one row of it at a time.

The trouble with one cycle

The clock cannot tick until the slowest instruction has settled. Suppose, for illustration, that each block takes this long:

InstructionInstr. memoryRegister readALUData memoryRegister writeTotal
lw200 ps100 ps200 ps200 ps100 ps800 ps
sw200 ps100 ps200 ps200 ps700 ps
add, addi200 ps100 ps200 ps100 ps600 ps
bne200 ps100 ps200 ps500 ps

These are round textbook numbers, not measurements of any chip, but the shape is right: memory accesses are slow and loads touch memory twice. With one cycle per instruction the clock period must be 800 ps (1.25 GHz in this example), and three of the four instructions in our loop spend part of every cycle doing nothing, waiting for a deadline set by lw. Worse, each block is busy for only a slice of the cycle. While the ALU works, the instruction memory sits idle. The next level puts that idle hardware to work.

Level 05/09Machine

Pipelines and hazards

The single-cycle machine finishes one instruction before it starts the next, so most of its hardware is idle most of the time. The fix is the same one a laundromat uses.

A classic RISC pipeline cuts the datapath into five stages, one per column of the diagram above: IF (fetch), ID (decode and read registers), EX (ALU), MEM (data memory) and WB (write back). Between stages sit Banks of flip-flops between pipeline stages. Each clock edge, every instruction's values and control signals move one stage to the right. that capture each instruction's values and control signals at the clock edge and hand them to the next stage. Five instructions are in flight at once, each in a different stage.

The clock now only has to cover the slowest stage, 200 ps in our illustrative numbers, rather than the slowest instruction (800 ps). Each instruction still takes five stages, 1,000 ps from fetch to write back, longer than before. Pipelining does not make any one instruction faster; it lets the machine finish one per cycle. The ideal speedup here is 4×, not 5×, because the stages are unequal: register access needs only 100 ps but still gets a whole 200 ps slot.

Hazards

The single-cycle machine never had to think about the instruction before or after. A pipeline overlaps them, and three kinds of conflict follow.

  • Structural hazards: two instructions want the same hardware in the same cycle. Separate instruction and data memories (in practice, split L1 caches) and a register file that writes in the first half of a cycle and reads in the second avoid them in this design.
  • Data hazards: an instruction needs a value that an earlier, still-running instruction has not written yet. In our loop, add a2, a3, a2 needs the a3 that lw is loading.
  • Control hazards: the pipeline must fetch the next instruction before it knows where the branch goes. bne is decided in EX, two cycles after the fetch stage needed the answer.

The chart below schedules three iterations of the loop through the pipeline. The timing model is computed, not drawn: each instruction enters EX only when its operands can be ready, and a wrong branch guess flushes the instructions fetched behind it. Flip the switches and watch the cycle count.

Loop body order
Forwarding
Branch guess

Pipeline timing: one row per instruction, one column per clock cycle
  • IF fetch
  • ID decode, read registers
  • EX ALU
  • MEM data memory
  • WB write register
  • stall
  • operand forwarded
  • fetched, then flushed
Three iterations of sum's loop plus the return, scheduled on a five-stage pipeline. Each row is an instruction and each column a clock cycle. Read a column top to bottom to see what every stage is doing in that cycle.

Forwarding

With forwarding off, a dependent instruction waits in decode until the producer has written the register file, one or two cycles of stalls (the register file writes in the first half of a cycle and reads in the second, which saves one). But the value existed long before that: an addi result is sitting in the EX/MEM pipeline register right after EX. Also called bypassing: multiplexers in front of the ALU that take an operand straight from a later pipeline register instead of the register file, when register numbers match. adds multiplexers in front of the ALU and a small comparator that notices "the instruction ahead of me writes the register I am about to read" and routes the value straight across. With forwarding on, the compiled loop runs without a single stall.

A load is the exception. Its value appears only at the end of MEM, and an instruction right behind it needs that value at the start of its own EX, in that same cycle. No wire can carry a value backwards in time, so the hardware inserts one bubble. Choose "Use the load at once" to see it. The compiled order hides this A stall caused when an instruction uses a register loaded by the instruction immediately before it. by placing addi a0, a0, 4 between the load and the add. Compilers schedule instructions exactly to fill slots like this.

Check yourselfForwarding is on and the loop uses the load right away. Why does add a2, a3, a2 still stall for one cycle?

Guessing branches

With the guess set to "not taken", the pipeline keeps fetching the next sequential instructions after bne. When EX discovers that the branch is taken, the two instructions fetched behind it (here mv and ret) are flushed and fetch restarts at .loop. Each wrong guess costs two cycles. Loops make "taken" the better guess: switch it and only the final exit is wrong. A correct "taken" guess costing nothing assumes fetch already knows the target address in the cycle after the branch, which is what the branch target buffer described below provides.

Real processors do not use one fixed guess. A Hardware that predicts, at fetch time, whether a branch will be taken and where it goes, using the history of that branch and of recent branches. remembers what each branch did before. The classic scheme keeps a 2-bit saturating counter per branch, so one surprise (like a loop exit) does not flip the prediction. A branch target buffer remembers where taken branches went, so fetch can redirect in the very cycle it fetches the branch. Modern predictors combine many histories of different lengths and are right well over 95% of the time on typical code. They have to be: a misprediction on a modern core throws away around 15 to 20 cycles of work, and with several instructions fetched per cycle, that can be a hundred instructions.

Pipelining raises throughput, not speed: each instruction takes as long as ever, but one finishes every cycle as long as the pipeline is kept fed. Forwarding, scheduling and prediction exist to keep it fed.

Level 06/09Machine

Caches and the memory wall

The pipeline gives the MEM stage one 200 ps slot to read data memory. That was the biggest lie so far. Main memory is DRAM: separate chips on a separate bus, and on current hardware a read takes something like 80 to 100 ns. At 4 GHz that is several hundred cycles, during which a naive pipeline would simply stop. Processor speed raced ahead of DRAM latency for decades, a gap known as the The growing gap between how fast a processor can execute instructions and how long it takes to fetch data from main memory..

The answer is a hierarchy of A small, fast memory close to the core that keeps copies of recently used data from a larger, slower memory.: small, fast memories next to the core that keep copies of recently used data. Small memories are fast because signals travel short distances and decode fewer address bits; big memories are dense and cheap but slow. You cannot have one memory that is both, so you stack several.

  1. Register32 × 4 bytes in RV32I~0.25 ns · within the cycle · under 1 s
  2. L1 data cache32–64 KiB per core~1 ns · ~4–5 cycles · 4 s
  3. L2 cache0.5–3 MiB per core~3.5 ns · ~12–18 cycles · 14 s
  4. L3 cache8–100+ MiB, shared~15 ns · ~40–80 cycles · 1 min
  5. DRAMGigabytes~90 ns · ~300–400 cycles · 6 min
  6. NVMe SSD readTerabytes~50 µs · ~200,000 cycles · 2.3 days
Rough load-to-use latencies on a recent desktop core at about 4 GHz, on a logarithmic scale. Exact figures vary by chip and generation; the orders of magnitude are what matter. The last column rescales time so that one 0.25 ns clock cycle lasts one second.

Caches work because programs are predictable in two ways. Temporal locality: something used recently is likely to be used again soon (the loop's instructions, the variable s). Spatial locality: something near a recent access is likely to be next (a[1] after a[0]). Caches exploit the second by never fetching a single word. They move whole The unit a cache stores and transfers: 64 bytes on most current processors, 128 on Apple's M-series., typically 64 bytes, so one miss brings in the next fifteen ints for free.

Where does an address go?

The simplest organisation is direct-mapped: every address can live in exactly one cache line, chosen by a few of its bits. Split the address into three fields:

  • Offset, the lowest bits: which byte within the line.
  • Index, the next bits: which line of the cache to look in.
  • Tag, everything above: stored alongside the line to record which of the many addresses that share this index is actually there.

A lookup reads the indexed line and compares its stored tag with the address's tag. Equal and valid means a hit; anything else is a miss, and the whole line is fetched from the next level, evicting whatever was there. The toy cache below has 8 lines of 16 bytes: 4 offset bits, 3 index bits and 25 tag bits.

Access pattern

Cache contents: 8 lines of 16 bytes
IndexValidTagHolds bytes
0000––
0010––
0100––
0110––
1000––
1010––
1100––
1110––
Accesses
0
Hits
0
Misses
0
Hit rate
–
    A direct-mapped cache with 8 lines of 16 bytes (128 bytes in total), driven by real address arithmetic. Try the three patterns, then any address of your own.

    Summing a 16-word array hits 75% of the time: each miss loads 16 bytes, four ints, so one miss is followed by three hits. Touching every 16th byte defeats spatial locality and every access misses. The third pattern is the nasty one. The two arrays sit exactly 128 bytes apart, the size of the whole cache, so their elements map to the same lines and evict each other on every access. Six lines sit empty while two thrash. These are conflict misses.

    Real caches reduce conflicts with An N-way set-associative cache lets each address live in any of N lines of its set, chosen by a replacement policy such as least-recently-used.: the index picks a set of, say, 8 or 12 lines, and the data may live in any of them. A 48 KiB L1 data cache might be 12-way associative with 64-byte lines. They also prefetch: hardware notices that sum walks memory upwards and fetches the next lines before the loop asks for them, which is why a simple array walk usually runs at close to cache speed even when the data starts in DRAM.

    Kind of missCauseRemedy
    CompulsoryFirst touch of a lineBigger lines, prefetching
    CapacityThe working set is bigger than the cacheBigger cache, or tiling your loops
    ConflictToo many hot lines share a setMore associativity, padding data structures

    The payoff is easy to estimate. Average memory access time is hit time plus miss rate times miss penalty. With a 1 ns L1, a 5% miss rate and a 90 ns trip to DRAM, the average is 1 + 0.05 × 90 = 5.5 ns. Halve the miss rate and the average drops by about 40%, from 5.5 to 3.25 ns. That is why, on modern chips, caches take up a large share of the die, and why data layout often matters more to performance than instruction count.

    Check yourselfIn the toy cache (16-byte lines, 8 lines), which line does address 0x1a4 map to, and what is its tag?

    Level 07/09Silicon

    Adders from logic gates

    So far the ALU has been a box that adds. Time to open it. Everything in the datapath that computes rather than remembers (the ALU, the adders, the multiplexers, the comparator, the control unit's lookup table) is Logic whose outputs depend only on its current inputs, with no memory of the past. Change an input and, after a short delay, the outputs follow., and all of it is built from a few kinds of logic gate.

    Inside the chip a bit is a voltage on a wire: close to the supply voltage (around a volt or less on a modern chip) means 1, close to 0 V means 0. Everything in between is forbidden territory that circuits pass through quickly on their way to one side or the other. That margin is what makes digital circuits reliable: a little noise on a wire does not change which side it is on, and every gate restores a clean level at its output.

    NOT Y = ¬A

    Y 0
    NOT truth table
    AY
    0
    1

    AND Y = A · B

    Y 0
    AND truth table
    ABY
    00
    01
    10
    11

    OR Y = A + B

    Y 0
    OR truth table
    ABY
    00
    01
    10
    11

    XOR Y = A ⊕ B

    Y 0
    XOR truth table
    ABY
    00
    01
    10
    11

    NAND Y = ¬(A · B)

    Y 0
    NAND truth table
    ABY
    00
    01
    10
    11
    Five basic gates. Click A and B to change the inputs; the active row of each truth table is highlighted. A green wire carries a 1.

    AND, OR and NOT are enough to build any Boolean function at all: write down the truth table, then OR together an AND term for every row that should output 1. NAND alone is enough too, since NOT, AND and OR can all be made from NANDs. That turns out to matter a great deal at the next level down.

    Adding in binary

    Take the addition the datapath did in the second loop iteration: 3 + 1. In binary that is 0011 + 0001, and you add the columns right to left, exactly as on paper:

    • Bit 0: 1 + 1 = 10 in binary. Write 0, carry 1.
    • Bit 1: 1 + 0 + carry 1 = 10. Write 0, carry 1.
    • Bit 2: 0 + 0 + carry 1 = 1. Write 1, no carry.
    • Bit 3: 0 + 0 = 0.

    The result is 0100, which is 4. Every column does the same job: take three bits (a, b and the carry in) and produce two (the sum bit and the carry out). The sum bit is 1 when an odd number of the inputs are 1, which is exactly XOR: sum = a ⊕ b ⊕ cin. A carry comes out when at least two inputs are 1: either a and b are both 1 (the column generates a carry, g = a · b), or exactly one of them is 1 and a carry arrives to be propagated ((a ⊕ b) · cin).

    A circuit that does one column is a A circuit that adds three bits (a, b, carry in) and outputs a sum bit and a carry-out bit. Five gates in the version shown here.: two XORs, two ANDs and an OR. (Without the carry input it would be a half adder: one XOR for the sum, one AND for the carry.) Chain four full adders, each one's carry out feeding the next one's carry in, and you have a 4-bit adder. The interactive below simulates it gate by gate, with every gate taking one unit of time to respond.

    A
    B
    Operation

    FAbit 3a3b3s3FAbit 2a2b2s2FAbit 1a1b1s1FAbit 0a0b0s0carryincarryout
    Open the full adder for
    abcarry inpgp·csumcarry out

    Sum = a ⊕ b ⊕ carry in. Carry out = a·b + (a ⊕ b)·carry in. A dashed wire still holds an old value that is about to change.

    A 4-bit ripple-carry adder, simulated gate by gate with one unit of delay per gate. It starts at 3 + 1, the same addition as add a2, a3, a2 in the second loop iteration. Toggle any input bit and the change ripples through; scrub the time slider to replay it.

    Try 0111 + 0001, or subtract 0001 from 0000. The sum bits on the right settle quickly, but each carry has to wait for the one before it. The carry out of bit i can need about 2i + 3 gate delays, so a 32-bit adder built this way would need around 65 gate delays in the worst case: far too slow to fit in one stage of a multi-gigahertz pipeline. The adder is the longest path in the ALU, and the carry chain is the longest path in the adder.

    Real ALUs use Adders that compute every carry in parallel from the generate (a·b) and propagate (a⊕b) signals of groups of bits, using a tree. Kogge-Stone and Brent-Kung are well-known designs. instead. They compute the generate and propagate signals of each bit (the g and p wires in the full adder above), then combine them in a tree: "does this group of 2 bits generate a carry, does this group of 4, of 8…". All 32 carries are ready after about log232 = 5 levels of combining instead of 32 steps in a row, at the cost of more gates and wires. Trading area for speed like this happens everywhere in a processor.

    Subtraction comes free

    Switch the adder to subtract. Computers store negative integers in The standard encoding of signed integers: the negative of x is the bitwise inverse of x plus one, so subtraction is addition of an inverted operand with a carry in of 1., where −B equals the bitwise inverse of B plus one. So A − B = A + ¬B + 1: invert B with a row of XOR gates (one input of each tied to a "subtract" control line) and set the carry in to 1. The same adder now subtracts, and that is how sub works. It is also how bne works in the datapath from earlier: the ALU subtracts the two registers and a 32-input NOR checks whether every bit of the result is 0.

    The multiplexers in the datapath are gates too. A 2-input mux is (a · ¬sel) + (b · sel): two ANDs, an OR and an inverter per bit. The control unit is a larger version of the same thing, a sum of products derived from its truth table.

    An adder is just the pencil-and-paper column method, wired up. Its speed is set by how fast carries can cross from bit 0 to bit 31, which is why real adders compute carries in a tree.

    Check yourselfIn the 4-bit ripple-carry adder, which output can be the last to settle after the inputs change?

    Level 08/09Silicon

    The transistor as a switch

    One level remains: what is a gate made of? In every modern processor the answer is the Metal-oxide-semiconductor field-effect transistor: a device in which the voltage on a gate terminal controls whether current can flow between its source and drain terminals., and for digital logic it is enough to think of it as a switch with three terminals. Two of them, the source and the drain, are the ends of the switch. The third, the gate, decides whether the switch is closed.

    • An NMOS transistor conducts when its gate is high (1). It is good at pulling a wire down to 0 V.
    • A PMOS transistor is its mirror image: it conducts when its gate is low (0), and it is good at pulling a wire up to the supply. The little circle on its gate in the symbols below means "active when low".

    Physically, the gate is a conductor separated from the silicon by an insulating layer only a nanometre or two thick. Put a positive voltage on an NMOS gate and its electric field draws electrons into a thin layer of silicon just under the insulator, forming a conducting channel between source and drain. Remove the voltage and the channel disappears. No steady current flows into the gate itself; it behaves like a tiny capacitor that has to be charged and discharged. Keep that in mind for the next level.

    CMOS: always a pair

    The trick that dominates chip design is Complementary MOS: every gate has a pull-up network of PMOS transistors and a mirror-image pull-down network of NMOS transistors, so exactly one of them conducts for any input., complementary MOS. Every gate gets two networks: PMOS transistors that can connect the output to the supply (VDD), and NMOS transistors that can connect it to ground. They are built as mirror images, series in one where the other has parallel, so that for every possible input exactly one network conducts. The output is always firmly driven to 1 or 0, and there is never a direct path from supply to ground. Toggle the inputs and follow the paths.

    CMOS inverter 2 transistors

    VDDGNDPMOSNMOSAY

    CMOS NAND 4 transistors

    VDDGNDABABmiddle nodeY

    Two CMOS gates with live inputs. Solid channels are transistors that conduct; dashed ones are off. Green wires are at the supply voltage (1), blue wires at ground (0), and a dashed grey wire is floating, connected to neither.

    Because one network is always off, a CMOS gate that is not switching draws almost no current. Power is spent mainly when outputs change, charging or discharging the wires and gates they drive. That property, more than speed, is why CMOS replaced every earlier logic family and became the way essentially all digital chips are built.

    Look at the NAND's structure: the NMOS pair is in series, so only A = 1 and B = 1 pulls the output down. Notice also that a single CMOS stage is always inverting: an NMOS turns on when its input goes high and drags its output low. That is why NAND and NOR, at four transistors each, are the natural building blocks, and AND costs six (a NAND followed by an inverter). It is also why the universality of NAND from the previous level matters: you can build the whole processor out of the gate the transistors make most cheaply.

    CircuitTransistorsNotes
    Inverter2One PMOS, one NMOS
    NAND, NOR (2 inputs)4The cheapest two-input gates
    AND, OR (2 inputs)6NAND or NOR plus an inverter
    Full adder28The common static CMOS "mirror adder"
    SRAM bit (cache cell)6Two cross-coupled inverters plus two access transistors
    Intel 4004, 1971About 2,300The first commercial single-chip microprocessor
    Large chips of the 2020sTens of billionsApple quoted 134 billion for the M2 Ultra
    Check yourselfIn the NAND gate, A = 1 and B = 0. Which transistors conduct, and what is Y?

    Level 09/09Silicon

    Clocks, power and the modern core

    We have reached the switch at the bottom. Two questions are left over from the way down, and answering them explains why the processor in your laptop looks so different from the one in the simulator. Where does memory come from, if gates only compute? And what sets the speed of the clock that every level so far has relied on?

    Feedback makes memory

    Connect two inverters in a loop, each one's output driving the other's input. If the first outputs 1, the second outputs 0, which keeps the first at 1: the pair holds its value for as long as it has power. That loop, plus two transistors to read and write it, is the six-transistor SRAM cell that makes up caches. Add a little gating and you get a latch; put two latches back to back and you get a A storage element that copies its D input to its Q output only at the rising edge of the clock and holds that value until the next edge., which samples its input only at the instant the clock rises. The PC, the pipeline registers and every other "register" in this dive are rows of flip-flops (large register files are often built as small SRAM-like arrays instead).

    The clock itself is a square wave, generated from a crystal oscillator, multiplied up on chip by a phase-locked loop and distributed through a tree of wires and buffers to every flip-flop. Its edges are the beat everything else keeps time to: flip-flops launch new values on one edge, logic computes in between, and the next edge captures the results.

    ClockRegister A outputold valuenew valueLogic output = register B inputstableclk→Qlongest logic pathsetupclock period T
    One clock cycle between two registers. The period must cover the flip-flop's clock-to-output delay, the slowest path through the logic, and the setup time the next flip-flop needs. In a real chip, clock skew between the two flip-flops eats into the budget too.

    That is the whole story of clock speed: T ≥ tclk→Q + tlogic + tsetup, for the worst path anywhere on the chip, the The slowest register-to-register path through combinational logic. It sets the shortest clock period the design can use.. Pipelining shortens tlogic by cutting paths in pieces. Parallel-prefix adders shorten it by replacing a 32-step carry chain with a 5-level tree. Smaller, faster transistors shorten every gate.

    Every edge costs energy

    Recall that a transistor's gate behaves like a tiny capacitor, and so does every wire. Each time a node switches from 0 to 1, the supply charges its capacitance; each time it goes back to 0, that charge is dumped to ground as heat. The energy for one full charge-and-discharge is about C·V². Multiply by how often it happens and you get the classic estimate for dynamic power:

    P ≈ α · C · V² · f

    Here α is the fraction of nodes that switch in a cycle, C the total switched capacitance, V the supply voltage and f the clock frequency. The catch hides in V. Transistors switch faster at higher voltage, so running at a higher clock usually also means raising V, and power grows much faster than speed. Try it.

    Dynamic power from P ∝ V²·f, relative to 1.0 V at 3 GHz. The model chip's top frequency rises roughly in step with voltage, and settings beyond it are flagged. The operating points are illustrative; every chip has its own voltage-frequency curve, and leakage power adds to these numbers.

    For about three decades, a rule known as Dennard scaling hid this problem. Each new process generation shrank transistors, lowered their capacitance and voltage, and power per square millimetre stayed roughly constant while clocks climbed from megahertz to gigahertz. Around the mid-2000s it broke down: voltages could not keep falling without transistors leaking too much current when off. Clock speeds levelled out at a few gigahertz, where they still are, and a chip's power budget, not its transistor count, became the limit on performance.

    The industry's answer was to spend the ever-growing number of transistors on doing more work per cycle instead of more cycles per second, and on doing the same work with less energy: more cores, wider vector units, bigger caches, and much smarter cores.

    The modern core

    A high-performance core today keeps the contract from level two (instructions appear to execute one at a time, in order) while doing nothing of the kind internally.

    1. Front end in order

      • Branch predictorGuesses the next fetch address every cycle, long before branches execute
      • FetchReads instruction bytes from the L1 instruction cache
      • DecodeSeveral instructions per cycle, roughly 4 to 10 on recent big cores
    2. Rename in order

      • Register renamingMaps the 32 architectural registers onto hundreds of physical ones, removing false dependences
      • Reorder bufferTracks every in-flight instruction in program order; hundreds of entries
    3. Execute out of order

      • SchedulersHold instructions until their operands are ready, then issue the oldest ready ones
      • Execution unitsSeveral ALUs, branch units, load and store pipes, vector and floating-point units, all working in parallel
      • Load/store queuesLet loads run ahead of older stores while preserving memory ordering
    4. Retire in order

      • CommitMakes results architecturally visible in program order, so the contract still holds
    A simplified modern out-of-order core. Instructions enter and leave in program order; in the middle, they execute in whatever order their operands become ready. Figures are rough ranges for recent high-end designs and vary widely.
    • Superscalar: it fetches, decodes and executes several instructions per cycle, with several ALUs and load/store pipes side by side.
    • Out of order: an instruction runs as soon as its inputs are ready, not when its turn comes. A load that misses the cache no longer stalls everything behind it; independent work flows around it.
    • Register renaming: our loop writes a0 in every iteration. Renaming gives each new value of a0 its own physical register, so the next iteration's pointer increment can run while the previous iteration's load is still waiting.
    • Speculation: the branch predictor guesses far ahead, and the core executes down the predicted path. The reorder buffer holds the results until everything older is known to be correct, and discards them on a misprediction or exception. To software, nothing ever happened out of order.

    Put sum on such a core and the picture from level three changes completely. The predictor learns that bne is taken, the prefetcher streams the array into the L1 ahead of the loads, and renaming lets several iterations overlap. The one dependence that cannot be overlapped is s += a[i] itself: each add needs the previous one's result. With single-cycle adds, a modern core can approach one iteration per clock cycle. With vector instructions, which a compiler at higher optimisation levels will often use for a loop like this, it handles several array elements per instruction.

    The simulator in this diveA recent high-end core
    Instructions per cycle1, alwaysSeveral on good code, far less when waiting on memory
    PipelineNone (or 5 stages)Roughly 15 to 20 stages
    Execution orderProgram orderDataflow order, retired in program order
    Registers32 architectural32 architectural, hundreds of physical
    MemoryEvery access takes one cycleThree levels of cache, prefetchers, hundreds of cycles to DRAM
    BranchesResolved when executedPredicted far ahead, executed speculatively
    Result of sum on {3, 1, 4, 1, 5}1414

    That last row is the point of the whole stack. Every layer down here, from the encoder to the transistor, is free to be as clever as it likes, as long as the 14 comes out. The instruction set is the promise that keeps software and silicon independent: compilers can target RV32I without knowing about reorder buffers, and chip designers can reinvent the reorder buffer without breaking a single compiled program.

    A processor is a loop that fetches and executes instructions, built from gates, built from switches. Everything else, from pipelines to caches to out-of-order engines, exists to run that loop faster without breaking the contract.

    End of Microprocessor · 9 levels, Idea to Silicon

    Where to next

    Browse all 34 divesAll topics