Chapter 3: How an instruction runs — five steps, and the assembly line

← Back to the Fundamentals home Chapter 3: Part 1 · Taking the machine apart

Chapter 3　How an instruction runs — five steps, and the assembly line

The aim of this chapter. In the previous chapter, the parts came together, one round. In this chapter we look at how a single instruction is actually executed using those parts. There are two handholds. One: a single instruction is completed by carrying out a fixed five steps. The other: when you overlap those steps and run them, the CPU gets much faster — this is called the assembly line (pipeline). No hard formulas appear.

3.1 A single instruction is made of five steps

Take, for example, the single instruction “add x1 and x2, put it in x3.” Even this doesn’t finish in one instant, snap. A CPU carries out the following five steps, always in the same order, to complete one instruction.

① Fetch. Read the next instruction to execute from memory. The step of bringing “which instruction” to hand.
② Decode. Decode what the instruction directs “to do,” and prepare the values to use from the registers.
③ Execute. In the ALU, actually do the computation, such as addition.
④ Memory access. Depending on the instruction, read or write data memory (many instructions don’t need this extra step).
⑤ Write-back. Save the computation’s result to a register. With this, one instruction is complete.

One instruction is completed by carrying out these five steps in order, top to bottom. When it finishes, the next instruction starts again from ①. Per step, roughly one clock beat.

3.2 Why can it proceed only in this order?

These five can’t have their order swapped. Because you can’t start the next step until the previous step’s answer is out. You can’t execute ③ before decoding the instruction at ②. You can’t save the result at ⑤ before computing at ③. It’s the same as cooking: you can’t stir-fry before cutting the ingredients, and you can’t plate before stir-frying. Since there’s an order to what must be done, it always proceeds from ① to ⑤.

3.3 Here, you notice something wasteful

Proceeding in order is fine, but there’s one wasteful point. While one instruction is doing ② “decode,” the part in charge of ① “fetch” has already freed its hands. The next instruction hasn’t been touched yet, and a perfectly good part is idle. — So, let that freed-up part already start the next instruction’s “fetch.” Think this way, and the CPU’s speed multiplies several times over.

3.4 The assembly line (pipeline) — the factory assembly line

This way of “overlapping steps and proceeding” is called the assembly line (pipeline). What to picture is a factory’s car assembly line. On the line, while car 1 is at the “painting” stage, car 2 is at “fitting parts,” car 3 at “making the body”… — each stage’s worker is always working on a different car. No one has stopped their hands.

A CPU is the same. The workers of the five steps each advance different instructions at the same time. Even though there are five steps, if it flows well, instructions are completed one after another, at a pace of roughly one per beat. Let’s see it in the table below.

Horizontal is time (the clock’s beats). Looking down orange time 5, instruction 1 is at step ⑤, instruction 2 at step ④, instruction 3 at step ③, instruction 4 at step ②. Four instructions are each advancing a different step at the same time. This is what the assembly line’s speed really is.

3.5 But — the steps must be of even length

For this assembly line to work well, there’s one condition. Each step must finish cleanly, in roughly the same time. If every instruction is simple and the steps are even in length, the line flows smoothly. But if just one oddly time-consuming instruction is mixed in, the line stops at that step, and the ones behind back up.

So making instructions simple, with even-sized grains, works in your favor. This idea leads into the next Chapter 4, “CISC and RISC” — the story of how much work you pack into a single instruction.

3.6 Summary

A single instruction is completed in five steps. Fetch → decode → execute → memory access → write-back. Since the previous step’s answer sets the next, the order can’t be changed.
Overlapping the steps and proceeding is the assembly line (pipeline). Since each step’s worker advances a different instruction at the same time, if it flows well, roughly one instruction is completed per beat.
The condition for flowing well is that the steps be of even length. So instructions are better simple — continued in Chapter 4.

Which decision is this knowledge for. Once you understand the assembly line, you gain an eye for choosing, for your own chip’s core, “into how many stages to split the steps.” Split shallowly, and the build is small and low-power, but the speed is modest. Split deeply, and it’s fast, but the circuit grows — this is the judgment of the balance between speed and area/power. Further, when a dev board won’t run well, it also becomes a clue for isolating which step an instruction tripped at. This is the groundwork for choosing the number of stages in “Brain,” and for the final “Verification,” on the preface’s “decisions map.”

Chapter 2: The blocks that make up a CPU Chapter 4: CISC and RISC