Pipelining

An analogy first - Baking Cakes

Each cake has 20 minute of prep, 20 minutes of cooking, 60 minutes cooling time before being iced for 20 minutes. Following this timing it would take 240 minutes to make 2 cakes, this can be represented by the diagram below. 

A) Prep B) Cooking C) Cooling D) Icing

So what is Pipelining

Pipelining is the concurrent decoding of two or more machine instructions. 

While part of one instruction (for example, an address field) is being decoded, another part of a second instruction (for example, an operation code) may also be decoded, as a means of increasing the speed of execution of a program.

Burdett, Arnold. BCS Glossary of Computing (Kindle Locations 7478-7480). BCS Learning & Development Limited. Kindle Edition. 

The aim of pipelining is to increase throughput - which is the amount of operations that can be completed in a particular amount of time

Back to baking...

One obvious thing would be to try to make 2 cakes at the same time, starting another cake immediately after the prep of the first is complete. This is seen in the diagram below. 

Each cake has 20 minute of prep, 20 minutes of cooking, 60 minutes cooling time before being iced for 20 minutes 

So for 2 cakes it now takes 140 minutes ( a saving of 100 over the first version)

We only have limited resources however, so if we run on the premise that we only have one cake tin then we have to alter this plan so that we need to wait until a cake is out of a tin until we can re-use this tin. This is shown in the diagram below.

Sometimes there are problems in that resources are being used by other processes so we couldn’t use it until another process has finished with it

So for 2 cakes it now takes 160 minutes (a saving of 80 over the first version)

Flushing the pipeline

Sometimes a pipeline will have to be flushed and cleared. For example - it is noticed that after the cake has came out of the oven that salt was used instead of sugar. 

The pipeline would be flushed (cleared) and started again. This is shown to the right.

What does this look like with instructions?

When processing an instruction there are generally a few steps

There are other considerations such as writing the instruction back to memory but we will not consider that at present.

If we fetch and execute 3 instructions immediately after one another it would require 6 clock cycles.

6 cycles to perform 2 instructions

If we implement pipelining we can perform the same step of the next cycle as soon as the part of the cycle has been completed. 

This should allow us to complete more instructions in the same amount of cycles.

6 cycles to perform 4 instructions

Why would the pipeline require flushing?

In an assembly line (our cooking analogy) we assumed that the order of the instructions would be sequential 

In a programming context if there was a branch statement (when a conditional statement would mean that one of a number of statements could be executed

Instructions with pipelining and branching

If we assume that instruction C caused a branch to be executed then that means that instruction D would not have already been fetched - as it is non sequential - so that means it would take an additional 3 cycles until this instruction was executed. This can be shown in the diagram below.

As instruction D was not in a sequential order then the pipeline had to be cleared and started from fresh