Explain the concept of pipelining and also explain types of pipelining.

The space-time diagram shows the stages (space) on one axis and the clock cycles (time) on the other. After the first few cycles, the pipeline is full, and one instruction finishes in every cycle.

Speedup. For $k$ stages, $n$ tasks and a clock time $t_p$:

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

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

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

For a very large $n$, the speedup comes close to $k$. For example, for $k = 4$ and $n = 100$, the speedup is $400/103 \approx 3.88$.

Types of pipelining

• Arithmetic pipeline: the stages of an arithmetic operation are overlapped. For floating point addition, the stages are compare exponents, align mantissas, add mantissas and normalize the result. It is used in vector processors and in floating point units.
• Instruction pipeline: the instruction cycle is split into stages like fetch, decode, operand fetch, execute and write back. A new instruction is fetched while the earlier ones are in later stages.
• Processor pipeline: a stream of data passes through a series of processors, each doing a part of the job. This is less common.
• Linear and non-linear pipelines: in a linear pipeline, data flows from the first stage to the last in one direction. A non-linear pipeline has feedback or feed-forward paths, so a stage may be used more than once.
• Static and dynamic pipelines: a static pipeline does one type of function at a time. A dynamic one can do different functions at different times.
• Unifunction and multifunction pipelines: the first does a fixed function, the second can be set to do several.

Hazards. A pipeline may stall because of three kinds of hazards. A structural hazard is when two stages need the same resource. A data hazard is when an instruction needs a result that is not ready. A control hazard comes from branches. They are solved by stalling, forwarding data and predicting branches.

Advantage. Pipelining raises the throughput without making any single instruction faster. The cost is extra registers between the stages and more complex control.

Example of an instruction pipeline. With four stages (fetch, decode, execute, write back), the first instruction finishes after 4 cycles. After that, one instruction finishes in each cycle. So 10 instructions need $4 + 10 - 1 = 13$ cycles, while without pipelining they need $10 \times 4 = 40$ cycles.