Instruction pipelining

Why it exists

In the instruction cycle a processor fetches, decodes, executes and writes the result of one instruction, then starts the next. While the ALU is executing, the instruction memory sits idle and the decoder sits idle. Pipelining puts every part of the hardware to work at once: it splits the instruction into stages, gives each stage its own hardware, and lets several instructions be in different stages in the same clock cycle, like cars on an assembly line. One instruction is no faster, but one finishes every cycle. GATE asks for the number of cycles, the speedup, the clock period of a pipeline and what limits it; the next page does the full arithmetic, and the hazard pages deal with what goes wrong.

Prerequisites

You need the steps of the instruction cycle, which become the pipeline's stages.

Precise definitions

Pipeline. A processing unit divided into $k$ stages. A pipeline register (latch) between consecutive stages holds the results of one stage while the next one uses them. On each clock cycle every instruction moves one stage forward and a new instruction enters the first stage.

The classic five stages (the textbook teaching pipeline):

Other splits are common in questions: a 4-stage pipeline (fetch, decode, execute, write back), or the six-stage one used in some books (fetch instruction, decode instruction, calculate operands, fetch operands, execute, write operand). Always use the number of stages the question gives.

Space-time (pipeline) diagram. A table with a row per instruction and a column per clock cycle; each cell names the stage the instruction occupies. It is the main tool for counting cycles. In a diagram without stalls, instruction $i$ ($i = 1, 2, \ldots$) is in stage $s$ ($s = 1, \ldots, k$) during cycle $i + s - 1$.

Fill, steady state and drain. For the first $k - 1$ cycles the pipeline is filling: some stages are idle. From cycle $k$ on, every stage is busy and one instruction completes per cycle. After the last instruction is fetched the pipeline drains.

Latency and throughput.

• The latency of one instruction is the time from entering the first stage to leaving the last: $k$ cycles. Pipelining does not shorten it (and with register overhead it lengthens it).
• The throughput is the number of instructions completed per unit time: ideally one per cycle.

Clock cycle. All stages share one clock, so the period must cover the slowest stage plus the delay of the pipeline register (setup time and clock-to-output delay):

$\tau_{pipe} = \max_s(\text{stage delay}_s) + d_{reg}.$

If the stages are unequal, the fast stages wait for the slowest one (waste). Balancing the stages, by moving work between them or splitting the slowest one in two, shortens the clock but adds a stage and a register.

What the pipeline registers carry. Everything later stages need: the instruction fields, the register values read, the ALU result, the data loaded, and the control signals for the remaining stages. The control information travels with its instruction, so each stage knows what to do for the instruction currently in it.

Why RISC pipelines well. Fixed-length instructions make the fetch and decode stages uniform; simple instruction formats let decoding and register reading happen together; loads and stores are the only instructions that access memory, so the MEM stage is used predictably; and each instruction needs each stage at most once and in the same order. Instructions of widely different lengths and complexity (many CISC instructions) leave stages unbalanced and some instructions needing a stage several times, which is why they are translated to simple internal operations before pipelining.

Stall (bubble). A cycle in which an instruction is held in its stage, or in which a stage does nothing useful, because the instruction cannot proceed. Stalls lower throughput below one instruction per cycle; their causes are the subject of pipeline hazards.

How it works

The first animation is the baseline: three instructions on a machine without a pipeline. One instruction runs through all five stages before the next starts, so at any moment four of the five stages are idle.

The second animation is the same hardware pipelined. Step through it and watch the fill (cycles 1 to 4), the full pipeline (cycle 5 onward: five different instructions in five different stages) and the drain. Six instructions finish in $k + n - 1 = 10$ cycles, against 30 without the pipeline.

The third animation shows what a stall does to the diagram. It is the subject of the next pages; for now notice that a held instruction blocks all those behind it, and every extra cycle is paid by everything after it.

Worked examples

#include <stdio.h>
 
int main(void) {
    int k = 5;
    long ns[5] = {1, 2, 6, 100, 1000000};
    for (int i = 0; i < 5; i++) {
        long n = ns[i];
        long plain = n * k, piped = n + k - 1;
        printf("n = %7ld: without pipeline %7ld cycles, with %7ld cycles, speedup %.3f\n", n, plain, piped, (double)plain / (double)piped);
    }
    return 0;
}

n =       1: without pipeline       5 cycles, with       5 cycles, speedup 1.000
n =       2: without pipeline      10 cycles, with       6 cycles, speedup 1.667
n =       6: without pipeline      30 cycles, with      10 cycles, speedup 3.000
n =     100: without pipeline     500 cycles, with     104 cycles, speedup 4.808
n = 1000000: without pipeline 5000000 cycles, with 1000004 cycles, speedup 5.000

Cheat box

Traps and GATE patterns

Connections

The stages come from the instruction cycle and the hardware in each is the datapath cut by pipeline registers. A regular instruction set (ISA design) is what makes the stages uniform. The exact speedup arithmetic is on pipeline speedup and CPI, and the causes of stalls are in pipeline hazards.

PYQs

Suppose the functions F and G can be computed in
5 and 3 nanoseconds by functional units UF and UG,
respectively. Given two instances of UF and two
instances of UG, it is required to implement the
computation F(G(Xi)) for 1 ≤ i ≤ 10. Ignoring all
other delays, the minimum time required to
complete this computation is
nanoseconds.

Consider the following reservation table for a
pipeline having three stages S1, S2 and S3.

The minimum average latency (MAL) IS

Consider a 4 stage pipeline processor. The number of
cycles needed by the four instructions I1, I2, I3, I4 in
stages S1, S2, S3, S4 is shown below.

What is the number of cycles needed to execute the
following loop?
For (i = 1 to 2) {I1; I2; I3; I4;}

Self-check

Revision card

References