Make one CPU core faster

Idle hardware

In Unit 2's multicycle machine, only one instruction is active. While it uses the ALU, the fetch hardware sits idle; while it reads memory, the ALU sits idle. Could the fetch hardware start the next instruction instead? In the picture, follow cycle 2: the first instruction is in decode while the second is already in fetch. By cycle 5, five independent instructions occupy five different stages. We assume each uses all five stages so the scheduling idea is easy to see.

Five stages, and the registers between them

That overlap needs a way to keep the instructions apart. Between stages sit pipeline registers. At every clock edge, each stage hands its instruction's intermediate values and control bits to the next. The pipeline registers also carry each instruction's PC and destination register number. For an instruction that writes a register, the destination number identifies which architectural register receives its result at writeback. A valid bit marks whether a slot holds a real instruction or a bubble, an empty slot used when the pipeline must wait. There is no longer one "current instruction": up to five instructions can be in flight, each at a different stage.

Try it: fill, flow, drain

The utilization picture compares the pipeline with Unit 2's multicycle machine. This explorer compares it with Unit 2's idealized single-cycle machine: five 1 ns pieces of logic in one 5 ns cycle, with no registers between the pieces. The pipeline puts registers between them, so each cycle can be shorter but pays register overhead. Adjust the instruction count and timing, then move the cycle slider to see what each stage holds.

Latency, throughput, and the empty ends

The timing diagram can make the pipeline look five times faster. Faster in which sense? Separate the time for one instruction from the rate at which a stream finishes:

• Latency: how long one instruction takes from start to finish. Here that's 5 × 1.1 = 5.5 ns, longer than the single-cycle baseline's 5 ns because of the interstage registers.
• Throughput: how much work completes per unit time. Once the pipe is full, one instruction per 1.1 ns.

For N independent instructions in an ideal K-stage pipeline, the total is N + K − 1 cycles. The first instruction finishes at the end of cycle K; each of the remaining N − 1 finishes one cycle later, so the last finishes in cycle K + N − 1. For example, four instructions in five stages take 4 + 5 − 1 = 8 cycles. This count includes the empty start and the final drain; do not add either again. A short program cannot get close to the ideal K× speedup:

Draw a five-instruction timeline by hand, including the empty start and end. Explain why better throughput didn't improve the latency of any single instruction.

A dependency is in the program; a hazard is in the schedule

Lesson 8 let a new instruction enter every cycle because the instructions were independent. Now put add x6, x5, x9 immediately after a load into x5. The add needs the value produced by this load rather than the value previously stored in x5. That need is a dependency, a fact about the program. The attempted schedule creates a hazard when the needed value has not arrived. Other hazards arise when hardware or a branch decision is missing. Ask what the machine is waiting for:

When is a value ready, and when is it needed?

For a data hazard, compare when the producer has a value with when the consumer needs it. In our model, an ALU result exists at the end of E, but loaded data exists only at the end of M. A consumer needs its operands at the start of its own E. In the figure, compare the arrows for an add and a load: which one reaches the next instruction in time? Forwarding gives a result a direct route from the producer's pipeline register to the consumer's ALU input, instead of making it wait to be written to and reread from the register file. Without forwarding, the value must reach W first. We assume W writes early enough that D can read it later in the same cycle.

Take a load followed immediately by an add that uses it. The load goes through F in cycle 1, D in 2, E in 3 and M in 4. The add would enter E in cycle 4, before the load's data exists. The hazard unit therefore holds the add in D for cycle 4, freezes the younger fetch behind it, and sends an invalid bubble into E. The older load keeps moving. In cycle 5, the add enters E and receives the value forwarded from the load's M/W pipeline register. The bubble costs one cycle, but no instruction is skipped or executed twice.

Try it: stalls and forwarding paths

Structural hazards

Suppose instruction fetch and data access shared one single-ported memory. A load reaching M in cycle 4 would collide with a later instruction trying to fetch in cycle 4. The memory can serve only one request in cycle 4, so instruction fetch waits until cycle 5. Forwarding cannot resolve this conflict because both accesses need the memory port. Separate L1 instruction and data caches let these accesses use different ports.

So the first diagnostic question is what is missing: a value, a resource, or a decision? Forwarding helps the first only after a value exists; another port helps the second. Prediction will address the third. Our timing model assumes the load's data is ready at the end of a single M cycle. A longer memory access delays that result and can extend the dependent instruction's stall. The next lesson examines how caches reduce memory-access time.

Before inserting a stall, mark when the producer creates the value and when the consumer needs it. Decide whether forwarding can deliver it by then; if it cannot, hold the consumer until it can.

Why a hierarchy

Forwarding cannot help an add until the load has received its data. If every load had to go all the way to main memory, many instructions would spend far longer waiting than executing. Fast memory is small and expensive per bit, while large memory is slower, so machines stack several kinds: registers, then one or more cache levels, then DRAM, then storage. Read the figure from top to bottom: the farther the data is, the more there is of it, but the longer the trip. L1, L2 and L3 simply name cache levels; their sizes and policies vary by design.

Temporal and spatial locality

A small cache helps only if it tends to hold the next bytes the program wants. Programs often reuse a value soon after reading it: temporal locality. They also often read nearby addresses, as in an array scan: spatial locality. That is why a cache fetches a whole line (often 64 bytes) on a miss. If an array of 4-byte integers begins at a 64-byte line boundary, one line holds its first 16 elements; the first access can miss and the next 15 can hit, provided the line remains in cache. In the plot, look for repeated heights (temporal reuse) and steadily rising addresses (spatial reuse).

How a cache finds a line

Once a cache has fetched a line, how does it find that line again? We'll use a tiny, fully traceable cache: 8-bit addresses, 16-byte lines, 64 bytes of data (4 lines). A hit means the requested line is present and valid; a miss means the cache must fetch it from the next level, possibly replacing another line. To locate and identify a line, split each address into three fields:

• offset: which byte within the 16-byte line (4 bits).
• index: which set the line must live in.
• tag: the rest of the address, stored alongside the line to identify which block is there.

How many index bits there are depends on the organization. Direct-mapped has 4 sets of 1 line, so 2 index bits: each block has exactly one possible home. 2-way set-associative has 2 sets of 2 lines, so 1 index bit: two possible homes. Fully associative has 1 set of 4 lines and no index bits: a block can go anywhere. The capacity is the same in every case. What changes is the placement flexibility, which costs extra tag comparisons.

For a direct-mapped lookup of byte address 0x4C, first identify its 16-byte line, 0x40–0x4F. The low hex digit C is the offset within that line. Line number 4 maps to set 4 mod 4 = 0; the remaining upper bits give tag 1. Look only in set 0: a valid line tagged 1 is a hit, and offset C selects the requested byte. An invalid line or a different tag is a miss. On a miss the cache fetches the whole 16-byte line, so a later read of 0x4D can hit if the line has not been evicted.

Try it: a cache you can trace by hand

Try "3 blocks, 1 set" in all three organizations. Direct-mapped and 2-way both miss every time. Two ways cannot hold three blocks that all compete for one set, and LRU evicts the block needed next. Fully associative has room for all three. Now try "scan ×2 (too big)": the scan touches eight 16-byte lines, but the cache holds only four. On the second pass, the first access to each line misses again even in the fully associative cache: those are capacity misses. The following access within that newly fetched line can still hit through spatial locality. "Too big" does not mean every byte access misses.

Writes

Stores add two separate policy choices:

Hardware can also prefetch, fetching lines it predicts you'll need. Good prefetches hide waiting. Wrong ones waste bandwidth and evict useful data.

A first cache performance model

For a simple blocking, one-level cache, the average memory access time is AMAT = hit time + miss rate × miss penalty. Every access pays the hit lookup time; only the fraction that misses pays the additional miss penalty. With the default numbers below, that is 2 ns + 0.10 × 40 ns = 6 ns per access on average. This is an average across hits and misses, not a promise that any individual access takes 6 ns.

Overlapping misses: memory-level parallelism

The AMAT calculation treated each miss as an added cost. Can a core make progress while a miss is outstanding? A nonblocking cache keeps a small table of outstanding misses (often called miss-status holding registers, MSHRs). It can serve hits and send further misses while an earlier one is still in flight. Overlapping misses is memory-level parallelism (MLP). The number of miss-tracking entries and memory bandwidth limit it, but so does the program: a second miss cannot start until its address is known. In the figure, compare two known addresses with a pointer chase whose second address comes from the first load.

Never call an access a hit until you've found its set and compared the valid tags there. Explain the difference between capacity and placement flexibility.

We have treated an address such as 0x4C as if it directly named a memory byte. A real process normally uses a virtual address. Logically, the machine must also establish which physical bytes the process means and whether it may access them; the next lesson follows that decision.

Every program gets its own view of memory

The cache trace treated an address as the same physical location for everyone. But what if two programs both use pointer 0x1234? They should not accidentally read each other's bytes. With virtual memory, both instruction fetches and load/store accesses begin with virtual addresses. Hardware translates them to physical addresses using mappings controlled by the operating system. Virtual memory is divided into fixed-size pages; physical memory into equally sized frames. A mapping places a process's virtual page in a physical frame, without requiring the two numbers to match. Follow 0x1234 through both processes in the figure: the same virtual address reaches different physical bytes. An unmapped or disallowed access raises a fault. This private, protected view is useful even when nothing is swapped to disk.

Splitting an address: page number + offset

Our teaching system uses 16-bit virtual addresses and 256-byte pages. The top 8 bits are the virtual page number (VPN) and the bottom 8 bits are the offset within the page. Translation replaces only the page number. The offset passes through unchanged.

The mapping also says what the process may do. A page-table entry holds permission bits (readable, writable, executable, user-accessible) and a present bit. Finding a physical frame does not make every kind of access legal. In the explorer below, every mapped page is readable, and only write permission is checked.

The page table itself lives in ordinary memory. Reading it for every instruction fetch and data access would add memory work just to find the address. A TLB (translation lookaside buffer) therefore caches recent translations and their permissions. It holds mappings, never the program's data: a TLB hit answers "which frame and is this allowed?", while a data-cache hit answers "are those bytes already nearby?"

For example, virtual address 0x1234 splits into page number 0x12 and offset 0x34. If page 0x12 maps to physical frame 0xA0 and the access has permission, the resulting physical address is 0xA034. A TLB hit supplies that frame number quickly. On a TLB miss, the processor consults the page table and can then cache the translation. The data cache checks whether it holds the line containing physical address 0xA034. The diagram places this check after translation to show the logical decisions; real hardware can overlap parts of the cache lookup with translation.

Try it: follow one access through translation

Before choosing a scenario, predict which question should fail: translation lookup, permission, or data lookup. The highlighted path then shows the decisions made. The TLB fills as you go, so an address that missed in the TLB can hit there on the next try; that alone does not decide the data-cache result.

Three different events, three different questions

The TLB and data cache perform different lookups. An access can hit one and miss the other, hit both, or miss both. A page fault doesn't always mean disk I/O. Depending on the mapping, the OS can allocate a new page filled with zeros, create a private copy of a shared page when the process first writes to it (copy-on-write), or load a page from storage. If the access is invalid, it can terminate the process with a segmentation fault. On a TLB hit, the processor still checks the entry's cached permission bits.

For any access, answer three questions separately: which physical bytes? (translation), is it allowed? (permissions), and where is a copy? (caches).

Address translation tells fetch where an instruction lives. It still cannot tell fetch which instruction comes after a branch whose result is not known yet.

The problem: fetch can't wait

Translation can tell fetch where an instruction lives, but a conditional branch must first choose which instruction comes next: the sequential one or one at a target address. The choice may depend on a value an earlier instruction has not produced yet. In our five-stage pipeline, the branch decides at the end of E. If fetch waits for every decision, it leaves two slots empty per branch. In an otherwise ideal run of 100 instructions with 20 branches, that is 40 extra cycles: about 140 cycles instead of 100, or CPI ≈ 1.4.

So the processor guesses both which way the branch will go and, if taken, where it will go. A direction predictor estimates taken or not taken; target information supplies the destination address. Fetch continues speculatively, before the guess is confirmed. For example, a branch at 0x100 might be predicted not taken, so fetch reads 0x104 and 0x108. If E later finds the branch taken to 0x140, those younger instructions are squashed (marked invalid), and fetch restarts at 0x140. The guess affects wasted work and timing; it must not change the program's accepted results.

Try it: a 2-bit saturating counter

A loop branch often goes back many times, then falls through once on exit. A predictor should learn the usual direction without reversing its guess after that single exit. This teaching model keeps a 2-bit counter for each branch. States 0–1 predict not taken and 2–3 predict taken. The predictor reads the state before the branch runs; after learning the true outcome, it increments toward 3 for taken or decrements toward 0 for not taken, stopping at either end. From strong-taken state 3, one unexpected not-taken result moves to weak-taken state 2, which still predicts taken next time. A second not-taken result moves to state 1 and changes the guess.

How much does accuracy matter?

A simple long-run estimate is CPI ≈ base CPI + (branches per instruction) × (fraction of branches mispredicted) × (penalty per miss in cycles). With the default values below, one in five instructions is a branch, one in ten of those is mispredicted, and each miss wastes two cycles: the added CPI is 0.2 × 0.1 × 2 = 0.04, for a total of 1.04. The estimate treats penalties as separate and ignores fill and drain.

Keep four things distinct: the predicted direction, the actual direction, speculative execution, and architectural acceptance.

Prediction keeps fetch supplied with instructions, but a scalar pipeline can still start at most one per cycle. A superscalar core can start several independent instructions from the same thread in one cycle. Fetch and decode in the front end supply them; execution ports in the back end do the work. The core has different widths at these points, so a narrow stage or an incompatible port can limit the rate. Several instructions in one core are still not several cores or several software threads. (Unit 4 adds simultaneous multithreading, which may fill slots from more than one thread.)

Try it: width meets dependencies

All four instructions are already decoded and waiting. The model issues in program order, up to W per cycle. An add takes 1 cycle and its result is usable the next cycle; two instructions issued together cannot use each other's new results. There are W ALU ports but only one load port, and loads take 3 cycles. Thus W = 4 can start four independent adds together, but a chain of four adds still starts one per cycle, and four independent loads still start on four successive cycles. Width, dependencies and port type are three separate limits.

The amount of available ILP depends partly on how the program expresses its work. In a sum with one accumulator, sum += a[i] must wait for the preceding update to sum. With four partial sums, one add can update s0 while other adds update s1, s2 and s3; only at the end must those four results be combined. That creates independent adds for a wide core to use. For floating-point numbers, regrouping additions can change rounding, so a compiler must respect the program's numerical rules.

Measuring it

IPC = retired instructions ÷ cycles. Its reciprocal is CPI, when both are measured over the same instructions and the same interval. The explorer above only shows the execution window. It leaves out fetch, decode and retirement, so it isn't a whole-program IPC.

Each load has a latency of 3 cycles: the time from starting the load to obtaining its result. The load unit's initiation interval is 1 cycle: because it is pipelined internally, it can accept another load every cycle. So four loads start in cycles 1, 2, 3 and 4 and finish in cycles 3, 4, 5 and 6, with up to three in flight at once. A single port limits the start rate, not the number outstanding.

Before predicting IPC, name three things: which width you mean, which ports are compatible with the instructions, and which operands are ready.

Data dependencies and name dependencies

The Lesson 13 explorer issued in order. If I1 is a slow load and I2 needs its result, I2 blocks the issue slot even when a younger I3 is ready. In the figure, I1 writes x1, I2 reads it, and I3 writes x1 again. Allowing I3 to execute first requires keeping the two versions of x1 separate: I2 must read the value produced by I1, even if I3 has already produced a newer x1 value.

Read after write (RAW) is the real flow of a value from I1 to I2; I2 must wait for it. Write after read (WAR) is the apparent conflict between I2's read of x1 and I3's later write. Write after write (WAW) is the conflict between I1 and I3 writing the same name. WAR and WAW are name dependencies: if the two x1 values can live in different storage locations, I3 can make its new value without disturbing the old one I2 needs.

Renaming: names become versions

The core has many more physical registers than the ISA's 32 architectural names. A rename map records the physical register assigned to the latest version of each architectural register. The producing instruction may still be waiting to execute; a ready bit indicates whether its result is available. For each instruction, in program order:

1. Look up each source in the map and record its physical-register tag. This identifies the version the instruction must read, whether or not that value is ready yet.
2. Take a free physical register for the destination, and update the map so later readers find it.

The order of those two steps matters: source tags are recorded before the destination is remapped. Step through the example (M[x10] = 7, x11 = 20, x12 = 5):

I1 remaps x1 to p20, so I2 records p20 as the source for both of its operands. Later I3 remaps x1 to p22. That map change affects instructions renamed after I3, including I4; it does not change the sources already recorded for I2. I2 can therefore wait for the load while I3 produces a different x1 value. In program order, the final x1 is I3's 24, while I2 still computes 7 + 7 = 14.

Out-of-order issue: go around the blocked load

Renaming removes the name dependencies by assigning separate storage to different versions of a register. It does not itself decide when work runs. The issue queue holds each renamed instruction and the physical-register tags of its inputs. When a producer finishes, its result becomes ready and waiting consumers of that tag can wake up. The scheduler can then choose a ready instruction even if an older instruction is still waiting for an operand. A consumer still cannot issue before its actual producer has made the value available.

In the comparison below, all five instructions have been renamed before cycle 1. One instruction may issue per cycle; the out-of-order scheduler picks the oldest ready instruction rather than stopping at the first blocked one. The load issues in cycle 1 and supplies its value at the end of cycle 4. Adds take one cycle, and a result is usable the next cycle. Before reading the lower timeline, find a place for I3 and I4 while I2 waits for the load.

The issue slot is idle in cycle 4 of this model: I2 still needs the load's p20, and I5 needs I2's p21 as well as I4's p23. The load is still in progress and becomes ready only at the end of cycle 4, so I2 can issue in cycle 5 and I5 in cycle 6. Out-of-order issue filled two cycles of the load wait with useful work; it did not shorten the load itself or remove its true dependencies.

What new state this takes

Extra physical registers don't give software more register names. They let more versions be in flight at once. Instructions still wait for their actual inputs, and memory bandwidth still limits how quickly data can arrive. The core can track only a finite number of instructions at once; this set is its instruction window. If an instruction queue is full or no physical register is free, the core must stop admitting instructions that need those resources. Independent work beyond that limit cannot yet be scheduled.

The old physical register for x1 (p1) cannot be freed as soon as x1 is remapped. Older instructions may still need to read it, and recovery may need to restore the old mapping.

Rename a sequence that reuses a destination register, and prove that every consumer still reads the right version of its input.

Computed is not the same as accepted

In Lesson 14, I3 and I4 finished before the older load I1. Now suppose I1 faults. If I3's x1 = 24 had already changed the committed register state, the fault handler would see an effect from an instruction after the fault. The core therefore separates completion—producing a result or detecting an exception—from retirement (also called commit)—committing an instruction's effects to architectural state in program order.

The reorder buffer (ROB) makes that separation possible. Instructions enter this queue in program order as they are renamed, and leave from its head in the same order. I3 may finish and leave 24 in a speculative physical register while I1 still waits; its ROB entry records "done", but I3 cannot retire yet. Only a completed, fault-free instruction at the head can retire. Once I1 completes, the head may advance through the waiting results. If I1 faults or a branch reveals a wrong path, the younger results can instead be discarded before software sees them.

This gives precise exceptions. If an instruction faults, the handler sees a machine where every older instruction has taken effect and neither the faulting instruction nor anything younger has, even if younger instructions already computed their results.

Try it: watch the ROB

This uses the out-of-order schedule from Lesson 14. Retirement is one per cycle, at the start of a cycle, using results completed by the end of the previous cycle. Committed registers x1–x4 start at 0. Select Load faults and advance to cycle 5. Check that I3 and I4's completed results are discarded while the committed registers retain their values from before I1.

In the successful run, I1 finishes at the end of cycle 4 and retires at the start of cycle 5. I2 cannot retire until cycle 6, even though I3 and I4 already finished earlier. Then I3 retires in cycle 7 and I4 in cycle 8. This delay is intentional: if the load had faulted instead, the younger values would have been discarded, leaving the handler the exact state before I1.

Notice two views of "x1". The committed x1 is 7 after I1 retires, then 24 after I3 retires. Meanwhile the speculative map already said x1 → p22 from the moment I3 was renamed, because any newly renamed instruction must read the newest version. Recovery from this fault copies the committed map back over the speculative one: every in-flight instruction is squashed, so none of their mappings are needed.

Recovery from a mispredicted branch is different. Instructions older than the branch are still valid even if they haven't retired, so the core must keep their mappings. A common approach is to checkpoint the speculative map when the branch is renamed and restore that checkpoint on a misprediction; copying the committed map instead would throw away the older instructions' mappings. The capstone shows this with real register names.

A retirement map records committed register mappings; a branch checkpoint saves speculative mappings for branch recovery. A core may use both. Cores also differ in where they store committed values. Some copy retiring results into a separate architectural register file. Others keep committed and speculative values in one physical register file and track which physical register holds each committed value. BOOM's documentation describes both storage arrangements. Both must preserve precise, in-order architectural effects: when an instruction faults, all older instructions have taken effect, and the faulting instruction and younger instructions have not.

Memory dependencies: the one renaming can't see

Register dependencies are visible in the instruction bits. Memory dependencies aren't. Whether a store and a later load touch the same bytes depends on addresses computed at run time. Take a single thread with M[A] = 3. The listing is schematic, not assemblable RISC-V: in real RV32I the store would be sw x6, 0(x10) (store x6 = 9 at the address in x10 = p) and the load lw x7, 0(x11).

If p turns out to equal A, L2 must see the store's 9. The core could make L2 wait for every older store address to become known, or it could guess that the addresses do not overlap and check later. Step through p = B and p = A. In which run can L2 keep its early read of 3?

If p = B, L2's early read of A was correct and the dependent add can keep its result 4. If p = A, L2 must obtain 9 from the older store, so its early result of 3 is incorrect. The store queue holds the older store's address and buffered data; the load queue records where the early load read. When the store's address becomes known, the core detects the overlap and squashes the load, the dependent add and anything younger. On replay, store-to-load forwarding can supply the buffered 9 directly from the older store queue entry; L2 and I3 then produce 9 and 10. This does not require the store to have updated the cache. Neither wrong value retires.

For the fault example, identify which completed values are discarded and why the committed register state survives. For a branch misprediction, explain why recovery must preserve mappings from older instructions that have not yet retired. Then explain how an incorrectly executed load and its dependent add are replayed before either can retire.

Now several mechanisms meet in one short run: a load misses, an independent instruction can proceed, and a branch waits on the missing value while fetch follows a guess. Draw cycles 1–7 before opening the answer.

Mark: waiting for the load, useful independent work, speculative work, branch execution, the squash, and retirement. State the committed x5, x6, x7 after I3 retires. Explain why I2 can execute during the cache miss, which instructions must wait for I1, and when retirement can begin.

A map of the state this unit added

The table summarizes the delays each mechanism addresses. Pipelining overlaps stages from different instructions. Forwarding allows an instruction to use a completed result before it is written back to the register file. A cache hit can supply a memory operand sooner than fetching it from the next memory level. Translation identifies and protects the physical bytes being requested. If fetch lacks the next PC, prediction lets it proceed speculatively. Width provides more instruction slots, and renaming with out-of-order issue finds ready work when an older instruction is waiting.

Those mechanisms leave a final obligation: speculative, out-of-order work must produce the program's promised architectural results. The ROB retires instructions in order, while the load and store queues catch memory conflicts that register renaming cannot identify. That is why I4's computed 4 in the capstone could be thrown away without changing the committed x6 = 3.

You're ready for the next unit when you can explain this table with examples, without mistaking overlapping instructions for extra threads, or a cached translation for cached data. Unit 4 will add multiple cores, cache coherence, memory ordering, hardware multithreading and vectors.