What is pipelining? What are the different stages of pipelining? Explain in detail.

Stages of an instruction pipeline

A common pipeline has five stages.

1. Instruction fetch (IF): the instruction is read from memory using the address in the program counter.
2. Instruction decode (ID): the opcode is decoded, and the source registers are read.
3. Execute (EX): the ALU does the operation, or calculates the address of a memory operand.
4. Memory access (MEM): a load reads data from memory, and a store writes data to memory.
5. Write back (WB): the result is written in the destination register.

In the timing diagram, each row is an instruction and each column is a clock cycle. Instruction 2 starts one cycle after instruction 1. After the pipeline fills in cycle 5, one instruction completes in every clock cycle.

Performance

For $k$ stages, $n$ instructions and a stage time $t_p$:

$$T_{pipelined} = (k + n - 1),t_p$$

$$T_{non\text{-}pipelined} = n,k,t_p$$

The speedup is then:

$$S = \frac{nk}{k + n - 1}$$

For large $n$ the speedup is close to $k$. For example, 100 instructions in a 5-stage pipeline give $500/104 \approx 4.81$.

Hazards. The pipeline cannot always run at full speed.

• A structural hazard happens when two instructions need the same hardware in the same cycle, such as one memory port for both fetch and data.
• A data hazard happens when an instruction needs a result that an earlier instruction has not yet written. It is reduced by forwarding the result directly and by stalling.
• A control hazard happens at a branch, when the next instruction is not known. It is reduced by branch prediction and by delayed branches.

Advantages and limits. Pipelining gives higher throughput and better use of the hardware. It does not reduce the time of a single instruction, and hazards and unequal stage times reduce the gain. RISC designs have simple, equal-length instructions, so they pipeline very well.