hamburger

Instruction Pipelining Study Notes

By BYJU'S Exam Prep

Updated on: September 25th, 2023

Parallel processing provides simultaneous data processing tasks for the purpose of increasing the computational speed of a computer system rather than each instruction is processed sequentially, a parallel processing system is able to perform concurrent data processing to achieve faster execution time and increase throughput.

There are more advantages with parallel processing but it has some issues also. Due to parallel processing, the number of hardware increases and the cost of the system increases. Parallel processing is established by distributing the data among the multiple functional units.

Flynn’s Classification

Flynn introduced the parallel processing classification. This classification considers the organization of a computer system by the number of instructions and data items that are manipulated simultaneously.

  • The sequence of instructions read from the memory constitutes an instruction stream.
  • The operations performed on the data in the processor constitutes a data stream.

Flynn’s Classification: Flynn’s classification divides a computer into four major groups as follows

  • Single Instruction stream, Single Data stream (SISD)
  • Single Instruction stream, Multiple Data stream (SIMD)
  • Multiple Instruction stream, Single Data stream (MISD)
  • Multiple Instruction stream, Multiple Data stream (MIMD)

SISD: It represents the organization of a single computer containing a control unit, a processor unit and a memory unit. Instructions are executed sequentially.

image001

SIMD: It represents an organisation that includes many processing units under the supervision d a common control unit. All processors receive the same instruction from the control unit but operate on different items of data.

image002

MISD: Its architecture contains n processors unit, each receiving instruction streams and providing the same data stream. MISD structure is only of theoretical interest, since no practical system has been constructed using this organisation.

image003

MIMD: Its organisation refers to a computer system capable of processing several programs at the same time.

image004

The operation of the CPU is usually described in terms of the Fetch-Execute cycle.

image005

In order to appreciate the operation of a computer, we need to answer such questions and to consider in more detail the organization of the CPU.

Pipelining

Pipeline processing is an implementation technique, where arithmetic sub-operations or the phases of a computer instruction cycle overlap in execution. A pipeline can be seen as a collection of processing segments through which information flows.

The overlapping of computation is made possible by associating a register with each segment in the pipeline. The registers provide isolation between each segment.

General Structure of 3-Segment Pipeline

image006

  • Each segment consists of a combinational circuit Si that performs a sub-operation over the data stream flowing through the pipe. The segments are separated by register Ri that hold the intermediate results between the stages.
  • Information flows between adjacent stages under the control of a common clock applied to all the registers simultaneously.
  • The behaviour of a pipeline can be illustrated with a space-time diagram. This is a diagram that shows the segment utilisation as a function of time. The horizontal axis displays the time in clock cycles and the vertical axis gives the segment number.
  • The space-time diagram shows the four-segment pipeline with T1 through T6 six tasks executed.

image007

  • Consider if K- segment pipeline with clock cycle time tp is used to execute n tasks. The first task T1 requires a time = K tp.
  • The remaining (n –1) tasks emerge from the pipe at the rate of one task per clock cycle and they will be completed after a time = (n –1) tp.
  • Therefore, to complete n tasks using a K-segment pipeline requires K + (n – 1) clock cycles.
  • A non-pipeline unit perform the same operation and takes a time of tn to complete each task. The total time required for n tasks in (n tn).
  • The speedup (S) is the ratio of a pipeline processing over an equivalent non-pipeline processing.image008

Special Case: As number of tasks increases, n becomes larger than K – l, then K + n – l is approximately n. Then, speedup becomes

If we assume tn = Ktp then, image009

image010 

When S= K, then maximum speedup is achieved in the system.

Instruction Pipeline

Pipeline processing can occur not only in the data stream but in the instruction stream. An instruction pipeline reads consecutive instructions from memory while previous instructions are being executed in other segments.

  • This causes the instruction fetch and execution phases to overlap and perform simultaneous operations and consider a computer with an instruction fetch unit and an instruction execution unit designed to provide two-segment pipeline.
  • Complex instructions that require other phases, in addition, to fetch and execute to process an instruction completely. The instructions cycle is as follows:
    • Fetch the instruction from memory
    • Decode the instruction
    • Calculate the effective address
    • Fetch the operands from memory
    • Execute the instruction
    • Store the result in the proper place.
Difficulties in Instruction Pipeline
  1. Resource conflicts: It is caused by access to memory by two segments at the same time. Most of these conflicts can be solved by using separate instruction and data memories. This conflict arises when Instruction fetch phase tries to access the memory for reading the code and register write back phase to access the memory to store the results. This conflict is resolved by dividing the main memory into two parts: Code Memory and Data Memory. 
  2. Data dependency conflicts: It arises when an instruction depends on the result of a previous instruction but this result is not yet available. When an instruction is updating some register and next instruction is trying to read the update in decoding phase, but till that time no update is made in the actual register. It can lead to reading Before Write hazard in the system.
  3. Branch difficulties arise: It arises from the branch and other instructions that change the value of the PC. In Some instructions, the result of branch operation is present after the completion of the execution or in some other phase of execution. So, some stalls are created for the successful execution of the program following the sequential flow. 

Stalls: The periods in which the decode unit, execute unit, and the write unit are idle are called stalls. They are also referred to as bubbles in the pipeline.

Hazard: Any condition that causes the pipeline to stall is called a hazard. There are three types of hazards are possible:

  • Data Hazard: A data hazard is any condition in which either the source or the destination operands of an instruction are not available at the time expected in the pipeline. As a result some operation has to be delayed, and the pipeline stalls.
    • There are basically three types of data hazard in the system: Suppose there is two instruction in the program instruction I and instruction J, and instruction j is executing after instruction i.
      • Read Before Write: When Instruction j tries to read a data item before updating it by instruction i. This is also known as True Data Dependency.
      • Write Before Write: When instruction J wants to write a data item before I can update it. This causes the problem because the final reflected update will be of instruction i, not j. This is also known as Output Data Dependency.
      • Write Before Read: When instruction j wants to write/ Update the data item before I can read it. This is also known as Anti Data Dependency
  • Instruction hazards: The pipeline may also be stalled because of a delay in the availability of instruction. For example, this may be a result of a miss in the cache, requiring the instruction to e fetched from the main memory. Such hazards are often called control hazards or instruction hazards.
  • Structural hazard: Structural hazard is the situation when two instructions require the use of a given hardware resource at the same time. The most common case in which this hazard may arise is in access to memory.

Performance

  • Performance = 1 / Execution time
  • Let Machine X is n times faster than Machine Y:
    • Performance of X = n * Performance of Y
    • Execution_time of X = (1/n) * Execution_time of Y
  • CPU Execution_time = (Number of CPU clock cycles required) * (cycle time) OR
  • CPU Execution_time = (Number of CPU clock cycles required) / (Clock rate)

Performance Analysis with stalls

As we know that, CPI for a pipeline system is 1, but due to dependency problem and hazards, some stalls are created in the system.

    So, CPIpipe = 1+ No of stalls/instn 

  Performance Gain= (CPInon-pipe * tp)/(CPIpipe *tp)

                            =K/(1+ No of stalls/instn)

You can follow the detailed champion study plan for GATE CS 2021 from the following link:

Detailed GATE CSE 2021 Champion Study Plan

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU’S Exam Prep Test Series check the following link:

Click Here to Avail GATE CSE Test Series!(100+ Mock Tests)

Get unlimited access to 21+ structured Live Courses all 112+ mock tests with Online Classroom Program for GATE CS & PSU Exams:

Click here to avail Online Classroom Program for Computer Science Engineering

Thanks

The Most Comprehensive Exam Prep App!

Our Apps Playstore
POPULAR EXAMS
SSC and Bank
Other Exams
GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com
Home Practice Test Series Premium