Five people, one sandwich each minute
A sandwich shop has one worker who takes the order, slices, fills, wraps and takes payment. Each customer waits five minutes.
Then the shop hires four more people and gives each one step. Each sandwich still takes five minutes to make. But a finished sandwich now comes off the line every minute. A processor does the same with instructions.
By the end of this lesson
Note
I can say how a pipeline speeds a processor up and what stalls it.
Key words
| Word | What it means | Example |
|---|---|---|
| Pipeline | running the steps of several instructions at once, each in a different stage | |
| Stage | one step of the pipeline, taking one clock cycle | EX |
| Hazard | something that stops the next instruction starting on time | |
| Stall | a cycle where a stage waits and does no useful work | |
| Forwarding | passing a result straight to the next instruction before it is written back | |
| Branch prediction | guessing which way a branch goes before it is worked out |
The cells students fill in are left blank in this preview.
Five stages, five instructions at once
A classic RISC-V pipeline has five stages. IF fetches, ID decodes and reads registers, EX does the arithmetic, MEM reads or writes memory, and WB writes the result back to a register.
Each stage takes one clock cycle. While one instruction is in EX, the next is in ID and the one after that in IF. So up to five instructions are in the processor at once.
Worked example: three instructions, no hazards
| Instruction | Cycle 1 | Cycle 2 | Cycle 3 | Cycle 4 | Cycle 5 | Cycle 6 | Cycle 7 |
|---|---|---|---|---|---|---|---|
| addi t0, zero, 1 | IF | ID | EX | MEM | WB | ||
| addi t1, zero, 2 | IF | ID | EX | MEM | WB | ||
| addi t2, zero, 3 | IF | ID | EX | MEM | WB |
The cells students fill in are left blank in this preview.
Go to the architecture folder
cd ~/archShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Faster without making any instruction faster
One at a time, 100 instructions of 5 cycles take 500 cycles. In a pipeline the first finishes after 5 cycles and one more finishes every cycle after that. So 100 instructions take 5 + 99, which is 104 cycles.
Each instruction still takes 5 cycles from start to finish. What grows is how many finish each cycle. That only holds while nothing makes an instruction wait.
A result that is not ready yet
A hazard is a reason the next instruction cannot go on time. The common one is a data hazard: an instruction needs a register an earlier one has not finished.
With no help, the pipeline stalls until the value is written back. Forwarding saves most of that wait: the answer from EX is passed straight to the next instruction. A load is different. Its value only exists after MEM, so the very next instruction still waits one cycle.
Worked example: stall cycles in our model
| The earlier instruction | How far before the user | Stalls without forwarding | Stalls with forwarding |
|---|---|---|---|
| add or addi | 1 instruction | 2 | 0 |
| add or addi | 2 instructions | 1 | 0 |
| lw | 1 instruction | 2 | 1 |
| lw | 2 instructions | 1 | 0 |
| Any | 3 or more | 0 | 0 |
The cells students fill in are left blank in this preview.
Write a program with a load-use hazard
printf '.globl _start\n_start:\n addi sp, sp, -16\n li t0, 7\n sw t0, 0(sp)\n lw a0, 0(sp)\n addi a0, a0, 1\n li a7, 93\n ecall\n' > hazard.sShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Assemble it
riscv64-linux-gnu-as hazard.s -o hazard.oShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Link it
riscv64-linux-gnu-ld hazard.o -o hazardShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Run it on the emulator
qemu-riscv64 ./hazardShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Read the exit status
echo $?Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Read the machine code
riscv64-linux-gnu-objdump -d hazardShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think a pipeline makes each instruction run faster. It does not: every instruction still goes through all five stages. A pipeline finishes more instructions each cycle. A stall throws some of that gain away, which is why the order of instructions matters.
The compiler fills the gap
A compiler knows the stall rules. When a load is followed by an instruction that needs it, the compiler looks for another instruction that does not, and moves it in between.
The next Runs compile the lab's loop.c for RISC-V. Look at the two summing loops, labelled .L6 and .L9, and find what sits between each load and its add.
Compile loop.c to plain RISC-V assembly
riscv64-linux-gnu-gcc -O2 -march=rv64gc -S loop.cShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
The row by row loop
grep -A 4 'L6:' loop.sShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
The column by column loop
grep -A 4 'L9:' loop.sShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Guessing which way a branch goes
A branch causes a control hazard: until EX works out the test, the pipeline does not know what to fetch next. Waiting would cost cycles on every branch.
So the processor uses branch prediction. It guesses and carries on. A right guess costs nothing; a wrong one throws away the work fetched since and starts again. The bne at the bottom of a loop goes back almost every time, so it is easy to guess.
Going further: reorder to remove stalls
Take this program: lw t0, 0(a0), add t1, t0, t0, lw t2, 4(a0), add t3, t2, t2. Count its stalls with forwarding, using your function.
Then reorder the four lines so the answer stays the same and the count is 0. Say which rule you used to decide that a move was safe.