Pipelining
Let’s start with the three machines we all have in our laundry room …
How long does it take to do a load of laundry?
Total: three hours.
Now, how long does it take to do two loads of laundry?
Total: Six hours?
How about?
Total: Four hours.
Now three loads.
Total: Five hours.
And for the middle hour all three machines were fully utilized.
Pipelining in computer terms means to take a sequential process that needs to be performed repeatedly and to increase the rate at which that process can be completed by overlapping parts that can be done in parallel.
This is a three-stage pipeline.
End-to-end it takes three hours to do a load of laundry, but we can do three loads an hour once we get things going.
In the CPU we can pipeline the Fetch/Decode/Execute cycle and thus execute instructions faster within a single CPU.
Even though fetch/decode/execute sounds like three stages, the classic model breaks the cycle into five parts:
| Instruction fetch | IF | Fetch the instruction from memory |
| Instruction decode | ID | Decode the fetched instruction |
| Execute | EX | Execute the decoded instruction |
| Memory | MEM | Read or write from memory if necessary |
| Write back | WB | Write back to CPU registers |
CPU with 5-stage pipeline
All of the special purpose registers except the PC become data passed along through the phases of the pipeline.
CPU with pipeline and split cache
Separate caches for instructions and data are a win since different pipeline stages executing concurrently care about one or the other.
But there’s no such thing as a free lunch.
The IF stage operates on the assumption that it can go ahead and fetch the next instruction. And then that instruction works its way through the pipeline.
But what happens if an instruction gets to EX and turns out to be a jump that sets the PC to something other than the next instruction?
On a branch we have to throw away the IF and ID phases that have already started working on instructions that aren’t the ones we need.
It’s fine to throw them away from a correctness point of view but that means we now need to wait for the IF phase to fetch the instruction from the address in the newly updated PC and for it to wend its way through the pipeline. So we waste two cycles, slowing down our overall execution rate.
Modern CPUs do branch prediction where the CPU keeps a table of what instruction address was actually executed most often after each branch instruction and the IF phase uses that table to decide what instruction to fetch next rather than just always fetching PC + 1.