Pipelining: Computer Organization and Architecture

Introduction to Pipelining

Before learning pipeline, we have to understand about the Parallel processing.

Parallel processing is the processing of data simultaneously. There are three techniques of parallel processing.

Types of Processing:

1. Vector Processing
2. Array Processing
3. Pipeline Processing(Pipelining)

Flynn’s Classification of Computers

Flynn's gave the classification of computers based on their capability and architecture. He classified computers based on how computers operate.

1. SISD – Single instruction stream, single data stream

These SISD types of computers are a very simple type of computers that will fetch one cycle with one instruction and execute an instruction with one data. So, at a particular time, one data is fetched, and one instruction is executed. For example, Von Neumann computers take one instruction at a time and execute that at a time.  

• SIMD – Single instruction Stream, Multiple data stream.

These computers take single instruction with multiple data streams means the system is taking one input or fetching one instruction, but the execution of instruction will be parallel. One instruction is fetched at one time and send for execution; again, the second instruction is fetched and send for execution parallel with the first one, and it continues. So the instruction is fetched once, and multiple instructions can be executed parallelly, for example, Pipeline processing in which one instruction is fetched at one time. Still, multiple processing of execution of instructions takes place.

• MISD-  Multiple instruction streams, single data stream

In this type of system, multiple instructions are fetched, and only one instruction is executed. Suppose four instructions are fetched together, and one is sent for execution, and in the meantime, three-four instructions are fetched. Now there are a total of 7 instructions piled up, which decrease the performance of the system. So, these kinds of systems are of no use. For example, This is only hypothetical; there are no computers implemented based on MISD.

• MIMD – Multiple instruction streams, multiple data stream

In this type of system, multiple instructions are fetched at a time, and multiple instructions are executed. So, to fetch multiple instructions simultaneously, multiple pipelines are applied. This MIMD has multiple pipelines in the system, and examples of such computers are Superscalar computers having ILP (instruction-level parallelism).

Where pipelining is applicable?

Pipelining is applicable and useful when the same processing is applied over multiple inputs. Pipelining gives a better result on multiple inputs; one same kind of processing is applied every time. For example:- a particular assembly line in manufacturing, in some production unit where car and bike are assembled, so the procedure is same that one part is taken, assembled at a particular place and then other part and then other in a sequence.

Definition: Pipelining is the technique to decompose a sequential process into small- small sub-operations, and sub-operations are performed in segments. There is a separate segment available to perform each sub-operation, and one operation is performed in all the segments called a task.

For example: Suppose there is a manufacturing unit that manufactures the shirts. Only one person manufactures the shirt so, it has to do all the operations like cutting the shirt, stitching the shirt, finishing the shirt and packing the shirt. Still, one task is divided into four subtasks with an increase in orders, and one person is appointed for one particular task (cutting, stitching, finishing and packing). Four hardware are working on small- small sub-operations.

“Each segment can perform its respective sub-operation over different input in parallel to other segments”.

So, if ‘n’ number of inputs are provided in pipelining, the ' n' number of the task will be performed in pipelining.   

Pipelining Cycle time

Pipelining cycle time is the minimum time in which all the segments can perform their respective sub-operation. It is that respective time in which all the stages of pipelining perform their sub-operations.

Pipeline time is denoted as T_p.

Note: Consider a k segment pipeline with clock cycle time =t_p to perform n number of tasks. How much time is required to perform the first task in the pipeline, or how much time pipeline will give the first output?

The time required to perform 1^st task = k * t_p

Time required to perform remaining (n-1) tasks = (n-1) t_p

Time required for all n tasks = (k +n -1) t_p

So, (k +n-1) t_p is the total number of cycles performed.

Note:- Consider a non- pipeline system that takes  t_n time to perform a task

 The time required for n task = n*t_n (because this particular system is a non-pipelined sequential system)

Speed Up Ratio performs a pipeline. Speed up ratio is the result of performance gain (how fast the pipeline system works) as compared to the non- pipeline system. How many times the pipeline is faster than the non- pipeline. If the speed-up ratio is 2, then the pipeline system is two times faster than the non-pipeline system.

 The formula of Speed Up Ratio = Non- pipeline time.

                                                   Pipeline time

                      S =    n * t_n

                            (k +n -1) t_p

• As the number of tasks increases, n" k ( here k-1 is ignored from the formula)         

                     S_ideal = t_n

                                t_p

          So this is the ideal case( because k-1 cycles are ignored to fill the pipe)

                     For 1 input = 1 cycle is required.

          Hence, the total n number of cycles required for n processing so the total time for n number of operations will be S_ideal, and this is also known as maximum speed up  S_max, which can be achieved in an ideal case.

Note:- Special case which is not true always.

Case: Suppose, to perform 1 task, pipeline and non- pipeline system take equal time.

             T_n = k* t_p

             S_ideal = K  (value of speed up is never greater than k ion if it can be less or equal to k).

So, to find the maximum speed up ratio, always use this formula.

Types of Pipeline

1. Hardware pipelining
2. Software pipelining
3. Arithmetic pipelining
4. Instruction pipelining

Hardware pipelining

Hardware pipelining helps designer to manage complexity where the complex task is divided into smaller tasks which are more manageable. It offers a high-performance system.

Software pipelining

Software pipelining helps in handling complex instructions, and it allows programs to be reused.

Arithmetic Pipeline

Arithmetic pipelines are found in very high-speed computers. They are used to perform high-speed floating-point operations like addition, multiplication and division. Multiple ALU's are built into the system to perform arithmetic operations parallelly in various data formats. In arithmetic, pipelining registers are used to store the intermediate results among the operations.

Registers are used for storing the intermediate results between the above operations.

---

Instruction Pipeline

In instruction pipelining, instruction is once fetched one by one, and at one clock cycle, one instruction is read from memory while previous instructions are being executed. Due to this, we can execute multiple instructions simultaneously. Instruction pipelining follows an instruction cycle to execute the instruction consisting of various phases divided into segments of equal duration. Instruction pipelining is further explained in detail on the next page.

Advantages and Disadvantages of Pipelining

Advantages	Disadvantages
Pipelining is widely used in modern systems (processors)	Involvement and adding of hardware increases the cost of the system.
The pipeline helps in reducing the cycle time of the processor.	The instruction latency is more.
Systems become faster and reliable.	It requires complex complication techniques.
Throughput of the system increases, which makes the system more efficient.
Hardware is arranged in such a way that more than one operation can be performed simultaneously.
Useful for application where one task is repeated with a different set of data.