Pipelining

Overview

Recall questions on pipelining in a processor, throughput once the pipeline is full, counting clock cycles with and without pipelining, jumps and branch prediction, data dependencies that stall a pipeline, and why RISC pipelines well.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is pipelining in a processor?

   Model answer

   Overlapping the stages of the cycle so that they happen at the same time on different instructions. While one instruction is being executed, the next is being decoded and the one after that is being fetched. Separate hardware handles each stage, so all of them can be busy during the same clock cycle instead of two thirds of the processor standing idle.

2. 2

   Once a three-stage pipeline is full, how many instructions complete per clock cycle, and what exactly has improved?

   Model answer

   One instruction completes per cycle, rather than one every three, so throughput is roughly tripled without the clock speed changing at all. What has not improved is latency: any individual instruction still takes three stages to pass through the pipeline. Pipelining increases how many instructions finish per second, not how quickly any one of them finishes.

3. 3

   A three-stage pipeline runs 6 instructions, each stage taking one clock cycle. How many cycles are needed, and how many would be needed without pipelining?

   Model answer

   Without pipelining, each instruction occupies the processor for all three stages, so 6 times 3 is 18 cycles. With pipelining, 3 cycles fill the pipeline and then one instruction completes every cycle thereafter, giving 3 plus 5, which is 8 cycles. The saving grows with the number of instructions, because the cost of filling the pipeline is paid only once.

4. 4

   What happens to the pipeline when the program reaches a jump?

   Model answer

   The instructions already fetched and decoded are the ones physically following the jump in memory, but the jump means those are not the instructions that should run next. They must be discarded, which is called flushing the pipeline, and the pipeline must be refilled from the target address. For the next few cycles no instruction completes, so the cycles spent fetching and decoding the wrong instructions are wasted. Code that branches frequently therefore erodes much of the benefit of pipelining.

5. 5

   How do processors reduce the cost of branches?

   Model answer

   By branch prediction: the processor guesses which way the branch will go, usually from the history of that branch, since for instance the branch at the end of a loop is taken on nearly every iteration. It then speculatively fetches and decodes from the predicted address. If the guess is right the pipeline never stalls; if it is wrong the speculative work is thrown away and the pipeline flushed, so the penalty is paid only on mispredictions.

6. 6

   Other than branches, what else stalls a pipeline?

   Model answer

   A data dependency, where an instruction needs a result the previous instruction has not yet produced, so it must wait and a gap appears in the pipeline. Resource contention, where two stages need the same piece of hardware at the same time. A cache miss, which delays a fetch and holds up everything behind it. And an interrupt, which requires the current state to be saved and the pipeline to be emptied before the service routine runs.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.