6. Pipelining

Pipelining

Instruction-level pipelining

Some CPUs perform instruction-level pipelining where they divide the [[FDE Cycle]] into smaller steps, and then execute these steps in parallel.\

Link to original

Consider an FDE cycle broken down into 6 stages:

1. Fetch instruction
2. Decode opcode
3. Calculate effective address of operands
4. Fetch operands
5. Execute instruction
6. Store result

These can be used in order in a six-stage pipeline. For every clock cycle, one small step is carried out and the stages are overlapped.

Theoretical Speed-up

The theoretical speed-up offered by a pipeline can be found as follows:

• Each instruction represents a task, $T$, in the pipeline.
• Let $N$ be the number of tasks (instructions) in the program.
• Let $t_p$ be the time per stage.
• Let $K$ be the number of stages in the pipeline.
• The first task $T_1$ requires $K{t}_p$ time to complete.
• The remaining $(N-1)$ tasks emerge from the pipeline one per cycle.
• So the total time to complete the remaining tasks is $(N-1)t_p$.

The time to complete $N$ tasks using a $K$-stage pipeline is:

$$\begin{array}{rl}T& =K{t}_p+(N-1)t_p\\ & =(K+N-1)t_p\end{array}$$

To compute the speed gain, we compare $T$ with the time taken to run the same program without pipelining, the time taken to run one task without pipelining is $K{t}_p$, hence we can find the time to do $N$ tasks to be $T^{\prime }=NK{t}_p$.

The fractional speed up is then given by:

$$S=\frac{T^{\prime }}{T}=\frac{NK{t}_p}{(K+N-1)t_p}$$

If we take the limit as $N\to \infty$ then $(K+N-1)\to N$. This results in a theoretical speedup of:

$$S_{\infty }=\frac{K{t}_p}{t_p}=K$$

These equations assume that:

• the architecture supports fetching instructions and data in parallel
• the pipeline can be kept filled at all times

Pipeline hazards are thongs that can cause a pipeline to stall, or be flushed for any reason such as: Resource conflicts, data dependencies, or conditional branching.