What is parallelism and pipelining in computer Architecture?

Parallelism

Pipelining

Pipelining is a method where the work of one instruction is split into stages, and many instructions are in different stages at the same time. Each stage has its own hardware. Like a car assembly line, a new instruction enters the pipeline in every clock cycle, while older ones move forward.

A simple instruction pipeline has these stages:

• IF: instruction fetch.
• ID: instruction decode and register read.
• EX: execute in the ALU.
• MEM: memory access.
• WB: write back the result.

The diagram shows that in clock cycle 5 five different instructions are being worked on, one in each stage. Without pipelining, the next instruction would have to wait until the whole of the earlier one finishes.

Speedup. Let $k$ be the number of stages, $n$ the number of instructions and $t_p$ the clock time of one stage. Then:

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

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

$$S = \frac{n,k,t_p}{(k + n - 1),t_p} = \frac{nk}{k + n - 1}$$

When $n$ is very large, the speedup tends to $k$. So a five-stage pipeline can be at most about five times faster.

Problems. Pipelines lose speed because of hazards:

• Structural hazard: two stages need the same hardware at once.
• Data hazard: an instruction needs a result that an earlier one has not produced yet.
• Control hazard: a branch changes the flow, so the fetched instructions may be wrong.

These are handled by stalls, forwarding (bypassing) and branch prediction.

Difference. Parallelism is the wider idea of many things happening together. Pipelining is one way to get it, using overlapped stages inside one processor. Pipelining does not shorten the time of one instruction, but it raises the throughput, that is, the number of instructions finished per second.

Example. Take a five-stage pipeline and 100 instructions, with the same clock time for every stage. Then the speedup is:

$$S = \frac{nk}{k + n - 1} = \frac{100 \times 5}{5 + 100 - 1} = \frac{500}{104} \approx 4.81$$

This is close to the ideal value of 5.

Types of parallelism in short. Instruction-level parallelism overlaps instructions inside one CPU, for example pipelining and superscalar issue. Thread-level parallelism runs different threads on different cores. Data-level parallelism applies one operation on many data items together, as in vector processors and GPUs. A real computer today often uses all three.

Where pipelining is used. Besides the instruction pipeline, there are arithmetic pipelines, for example for floating point addition, which split the work into stages such as exponent compare, align, add and normalize.