Lesson 33 · Build a processor

Pipeline hazards

A pipeline overlaps instructions, one per stage, so a new one can start every clock cycle. That breaks when an instruction needs something that is not ready yet. Using the course CPU TINY-8, watch OUT r0 try to read r0 before ADD r0, r1 has written its 5, and fix it two ways: stall with bubbles, or forward the result straight back. Then see why a late JNZ decision fetches the wrong instructions, how flushing and branch prediction deal with it, and why one shared memory causes a structural hazard.

12 min10 steps5 questionsIntermediate

Fig 33 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01In a five-stage pipeline without forwarding, ADD r0, r1 is followed at once by OUT r0. Why can OUT not simply go on?

OUT reads r0 in decode in cycle 3, but ADD only writes the 5 back in cycle 5. Reading then would give the old 2: a data hazard.

02With forwarding, how does OUT r0 get the 5 from ADD r0, r1 without waiting?

The 5 exists as soon as ADD leaves execute. Forwarding feeds it back to the ALU input, so OUT uses it the very next cycle with no bubble.

03In this lesson's pipeline, JNZ 12 checks the zero flag in execute and the jump is taken. What happens to the two instructions fetched behind it?

They came from addresses 16 and 18 but the program goes back to 12, so they must not run. Flushing them costs two cycles per taken jump.

04JNZ 12 jumps back to address 12, which is behind it. With the rule "a jump backwards is taken", what does fetch do right after JNZ?

That is branch prediction: fetch guesses taken and carries on. In this loop JNZ runs 3 times, so the guess is right twice and wrong once, and only the wrong guess is flushed (2 lost cycles instead of 4).

05TINY-8 keeps the program and the data in one memory. Which hazard can that cause in a pipeline?

Two instructions want the same hardware at once, so fetch must wait. Separate instruction and data memories (or caches) remove the clash.

Key terms

Glossary

Pipeline: A processor design that splits each instruction into stages, so several instructions are worked on at once, each in a different stage.
Hazard: A situation where the next instruction cannot safely go on in the next clock cycle. The three kinds are data, control and structural hazards.
Data hazard: An instruction needs a value that an earlier instruction still in the pipeline has not written yet, such as OUT r0 right after ADD r0, r1.
Stall: Holding an instruction in its stage for one or more cycles until what it needs is ready.
Bubble: An empty slot (a no-op) that travels through the pipeline during a stall or after a flush and changes nothing.
Forwarding: Also called bypassing: a wire that carries a fresh result straight back to the execute stage, so the next instruction need not wait for write back.
Control hazard: The pipeline does not yet know which instruction comes next because a jump has not been decided.
Branch prediction: Guessing whether a jump will be taken so fetch can carry on; a wrong guess is flushed.

Fine print

Notes and sources

The five stages, fetch (IF), decode (ID), execute (EX), memory (MEM) and write back (WB), are the classic pipeline of Patterson and Hennessy, Computer Organization and Design, section 4.6, and of Harris and Harris, Digital Design and Computer Architecture, section 7.5.
The register file is written in the first half of a clock cycle and read in the second half, so without forwarding an instruction that needs the result of the one just before it waits two cycles (Patterson and Hennessy, section 4.8).
Forwarding (bypassing) feeds a result from the pipeline register after execute straight back to the ALU input. A load followed at once by an instruction that uses its value still needs one bubble, because the value only exists after the memory stage (Patterson and Hennessy, section 4.8; Harris and Harris, section 7.5.3).
In this lesson's pipeline JNZ checks the zero flag in execute, so a taken jump flushes the two instructions fetched behind it. Real pipelines often decide branches earlier and predict them; backward-taken, forward-not-taken is one simple static rule (Hennessy and Patterson, Computer Architecture: A Quantitative Approach, appendix C).
TINY-8 numbers come from the course simulator: ADD r0, r1 with r0 = 2 and r1 = 3 gives 5; JNZ 12 sits at address 14 and runs 3 times, jumping back twice; memory past the program holds 0, which decodes as HALT.
TINY-8 has one 256-byte memory for program and data, so a store in MEM and a fetch in IF would need it in the same cycle. Pipelined processors avoid this structural hazard with separate instruction and data memories or caches (Patterson and Hennessy, section 4.6).

Quiz Unlocks after the last step.