yeolyi.comSeongyeol's CS

Pipelining

Right now the computer handles one instruction from start to finish in a single clock. So the time between clocks can’t be shorter than the time it takes to process one instruction.

Processing one instruction can be split into three stages. It fetches the instruction the PC points to from memory (Fetch), the control unit decodes the operation number (Decode), and the registers and the ALU execute it (Execute). The CPU repeats this instruction cycle endlessly.

During one long clock, the PC and memory work only at the start, in Fetch, and then wait for decoding and executing to finish. Couldn’t we fetch the next instruction ahead of time while they wait?

Three baskets of laundry

Say we do three baskets of laundry by washing, drying, and folding, in that order. If each stage takes an hour, putting in the next basket only after the previous one is folded takes 9 hours.

Hours123456789
Basket 1WDF
Basket 2WDF
Basket 3WDF

All 3 baskets are done in 9 hours.

If we put the second basket into the washer as soon as the first one moves to the dryer, the three jobs run at the same time and everything is done in 5 hours. Splitting work into stages and overlapping the stages like this is called a pipeline.

The instruction pipeline

Fetch uses the PC and memory, Decode uses the control unit, and Execute uses the ALU and registers. Each stage uses different parts, so we can fetch the next instruction while decoding the current one. Let’s put registers between the stages to hold their results, and move forward one stage per clock.

Clock 1
FetchLDI R0, 2
F/D registerEmpty
DecodeIdle
D/E registerEmpty
ExecuteIdle

Each time you press next, the values in the registers move down one stage.

In the table below, let’s say each stage takes 1ns (a billionth of a second).

Time (ns)123456789101112131415
0: LDI R0, 2F D E
1: LDI R1, 3F D E
2: ADD R0, R1F D E
3: ADDI R0, 1F D E
4: STORE 15F D E

5 instructions take 5 clocks of 3ns, 15ns in total.

With a shorter clock and overlapping stages, work that took 15ns finishes in 7ns. One instruction still takes 3ns from start to finish. But once the pipeline is full, one instruction finishes on every clock. A pipeline doesn’t shorten the time for a single instruction; it increases the throughput, the number of instructions finished in a given time.

Jumps and the pipeline

Things don’t always flow this smoothly. Jumps are the classic case. A jump changes the PC in the Execute stage, and JZ also decides whether to jump only then, by looking at the Zero Flag.

FetchJUMP 3
DecodeIdle
ExecuteIdle

Clock 1. JUMP 3 hasn't reached Execute yet, so the PC points to the next slot.

Clock123456
0: JUMP 3F

Press next until JUMP 3 reaches Execute.

By the time JUMP reaches Execute, the CPU has already fetched and is decoding the next two instructions. When it jumps, these two must be thrown away and fetching starts again from the jump address. Neither has reached Execute, so neither has changed any register or memory; it’s enough to replace the two in the registers between stages with an instruction that does nothing.

Let’s run the program from the Jump post that adds 1 through R0, with R0 = 2.

Time (ns)123456789101112131415161718192021222324252627282930
0: LDI R0, 2F D E
1: ADD R1, R0F D E
2: SUBI R0, 1F D E
3: JZ 5F D E
4: JUMP 1F D E
1: ADD R1, R0F D E
2: SUBI R0, 1F D E
3: JZ 5F D E
5: MOVE R0, R1F D E
6: STORE 15F D E

10 instructions take 10 clocks of 3ns, 30ns in total.

With the pipeline, the struck-through rows after JZ and JUMP are instructions that were fetched and thrown away.

We lose what we throw away, but the pipeline is still much faster.

Wrapping up

A pipeline overlaps stages to raise throughput without adding parts. But this calculation assumes that reading memory also finishes in a single clock. From the next post, let’s look at the memory side.

Challenge

Laundry goes through a washer, a dryer, and folding, in that order. There is one washer, one dryer, and one person folding, and each handles only one basket at a time. Washing takes 1 hour, drying 2 hours, and folding 1 hour. With the stages overlapped, what is the minimum number of hours until all four baskets are folded? Answer with a number.