Short Notes: Instruction Pipelining | Short Notes for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

 Page 1


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 tim e and increase 
throughput.
There are more advantages with parallel processing but it has som e issues also. 
Due to parallel processing, the amount of hardware increases and the cost of 
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 organisation 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 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 (M IM D )
SISD: It represents the organisation of a single computer containing a control unit, 
a processor unit and a memory unit. Instructions are executed sequentially.
Page 2


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 tim e and increase 
throughput.
There are more advantages with parallel processing but it has som e issues also. 
Due to parallel processing, the amount of hardware increases and the cost of 
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 organisation 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 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 (M IM D )
SISD: It represents the organisation of a single computer containing a control unit, 
a processor unit and a memory unit. Instructions are executed sequentially.
IS
SISD computer
SIMD: It represents an organisation that includes many processing units under the 
supervision d a common control unit. All processors receive the sam e instruction 
from the control unit but operate on different items of data.
SIMD computer
MISD: Its architecture contains n processors unit, each receiving instruction 
stream s and providing the sam e data stream. MISD structure is only of theoretical 
interest, since no practical system has been constructed using this organisation.
MISD computer
MIMD: Its organisation refers to a computer system capable of processing several 
programs at the sam e time.
MIMD computer
The operation of the CPU is usually described in term s of the Fetch-Execute cycle.
Page 3


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 tim e and increase 
throughput.
There are more advantages with parallel processing but it has som e issues also. 
Due to parallel processing, the amount of hardware increases and the cost of 
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 organisation 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 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 (M IM D )
SISD: It represents the organisation of a single computer containing a control unit, 
a processor unit and a memory unit. Instructions are executed sequentially.
IS
SISD computer
SIMD: It represents an organisation that includes many processing units under the 
supervision d a common control unit. All processors receive the sam e instruction 
from the control unit but operate on different items of data.
SIMD computer
MISD: Its architecture contains n processors unit, each receiving instruction 
stream s and providing the sam e data stream. MISD structure is only of theoretical 
interest, since no practical system has been constructed using this organisation.
MISD computer
MIMD: Its organisation refers to a computer system capable of processing several 
programs at the sam e time.
MIMD computer
The operation of the CPU is usually described in term s of the Fetch-Execute cycle.
F e tc h -E x e c u te C y cle T h e cy cle ra ises m a n y in tere stin g q u e stio n s, 
e.g.
F e t ch th e In s tr u c tio n W h a t is a n In s tru c tio n ? W h e re is th e 
In s tru c tio n ? W h y d o e s it n e e d to b e fe tc h e d ? 
Is n 't it o k a y w h e re it is? H o w d o e s th e 
co m p u te r k e e p tra c k o f in s tru c tio n s? W h e re 
d o e s it p u t th e in s tru c tio n it h as ju s t fe tc h e d ?
In c re m e n t th e P r o g r a m 
C o u n te r
W h a t is th e P ro g ra m C o u n te r? W h a t d o e s th e 
P ro g ra m C o u n te r c o u n t? In c re m e n t b y h o w 
m u c h ? W h e re d o e s th e P ro g ram C o u n te r 
p o in t to a f te r it is in c re m e n te d ?
D e c o d e th e In s tru c tio n W h y d o e s th e in s tru c tio n n e e d to h e 
d e c o d e d ? H o w d o e s it get d e c o d e d ?
F e tc h th e O p e r a n d s W h a t a re o p e ra n d s ? W h a t d o e s it m e a n to 
fe tc h ? Is th is fe tc h in g d istin c t fro m th e 
fe tc h in g in S te p 1 a b o v e ? W h e re are th e 
o p e ra n d s? H o w m a n y a re th e re ? W h e re do 
w e p u t th e o p e ra n d s a f te r w e fe tc h th e m ?
P e rfo rm th e O p e ra tio n Is th is th e m a in ste p ? C o u ld n 't th e co m p u te r 
sim p ly h a v e d o n e th is p a rt? W h a t p a rt o f th e 
C P U p e rfo rm s th is o p e ra tio n ?
S to re th e resu lts W h a t re su lts? W h e re fro m ? W h e re to ?
R e p e a t fo rev e r R e p e a t w h a t? R e p e a t fro m w h e re ? Is it really 
a n in fin ite lo o p ? W h y ' 7 H o w d o th e s e steps 
e x e c u te an y in stru c tio n s at all?
In order to appreciate the operation of a computer we need to answer such 
questions and to consider in more detail the organisation of the CPU.
Pipelining
Pipeline processing is an implem entation technique, where arithmetic 
suboperations or the phases of a com puter instruction cycle overlap in execution. A 
pipeline can be visualised 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
Input
$ ¦ R , I S ; j-- ? R2 — «-| S3 j-- ? R3
• Each segment consists of a combinational circuit Si that performs a 
suboperation over the data stream flowing through pipe. The segments are 
separated by register Ri that hold the interm ediate 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 tim e. The 
horizontal axis displays the tim e in clock cycles and the vertical axis gives the 
segment number.
Page 4


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 tim e and increase 
throughput.
There are more advantages with parallel processing but it has som e issues also. 
Due to parallel processing, the amount of hardware increases and the cost of 
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 organisation 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 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 (M IM D )
SISD: It represents the organisation of a single computer containing a control unit, 
a processor unit and a memory unit. Instructions are executed sequentially.
IS
SISD computer
SIMD: It represents an organisation that includes many processing units under the 
supervision d a common control unit. All processors receive the sam e instruction 
from the control unit but operate on different items of data.
SIMD computer
MISD: Its architecture contains n processors unit, each receiving instruction 
stream s and providing the sam e data stream. MISD structure is only of theoretical 
interest, since no practical system has been constructed using this organisation.
MISD computer
MIMD: Its organisation refers to a computer system capable of processing several 
programs at the sam e time.
MIMD computer
The operation of the CPU is usually described in term s of the Fetch-Execute cycle.
F e tc h -E x e c u te C y cle T h e cy cle ra ises m a n y in tere stin g q u e stio n s, 
e.g.
F e t ch th e In s tr u c tio n W h a t is a n In s tru c tio n ? W h e re is th e 
In s tru c tio n ? W h y d o e s it n e e d to b e fe tc h e d ? 
Is n 't it o k a y w h e re it is? H o w d o e s th e 
co m p u te r k e e p tra c k o f in s tru c tio n s? W h e re 
d o e s it p u t th e in s tru c tio n it h as ju s t fe tc h e d ?
In c re m e n t th e P r o g r a m 
C o u n te r
W h a t is th e P ro g ra m C o u n te r? W h a t d o e s th e 
P ro g ra m C o u n te r c o u n t? In c re m e n t b y h o w 
m u c h ? W h e re d o e s th e P ro g ram C o u n te r 
p o in t to a f te r it is in c re m e n te d ?
D e c o d e th e In s tru c tio n W h y d o e s th e in s tru c tio n n e e d to h e 
d e c o d e d ? H o w d o e s it get d e c o d e d ?
F e tc h th e O p e r a n d s W h a t a re o p e ra n d s ? W h a t d o e s it m e a n to 
fe tc h ? Is th is fe tc h in g d istin c t fro m th e 
fe tc h in g in S te p 1 a b o v e ? W h e re are th e 
o p e ra n d s? H o w m a n y a re th e re ? W h e re do 
w e p u t th e o p e ra n d s a f te r w e fe tc h th e m ?
P e rfo rm th e O p e ra tio n Is th is th e m a in ste p ? C o u ld n 't th e co m p u te r 
sim p ly h a v e d o n e th is p a rt? W h a t p a rt o f th e 
C P U p e rfo rm s th is o p e ra tio n ?
S to re th e resu lts W h a t re su lts? W h e re fro m ? W h e re to ?
R e p e a t fo rev e r R e p e a t w h a t? R e p e a t fro m w h e re ? Is it really 
a n in fin ite lo o p ? W h y ' 7 H o w d o th e s e steps 
e x e c u te an y in stru c tio n s at all?
In order to appreciate the operation of a computer we need to answer such 
questions and to consider in more detail the organisation of the CPU.
Pipelining
Pipeline processing is an implem entation technique, where arithmetic 
suboperations or the phases of a com puter instruction cycle overlap in execution. A 
pipeline can be visualised 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
Input
$ ¦ R , I S ; j-- ? R2 — «-| S3 j-- ? R3
• Each segment consists of a combinational circuit Si that performs a 
suboperation over the data stream flowing through pipe. The segments are 
separated by register Ri that hold the interm ediate 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 tim e. The 
horizontal axis displays the tim e in clock cycles and the vertical axis gives the 
segment number.
The space-tim e diagram shows the four segment pipeline with T i through T 6 
six tasks executed.
1 2 3 4 5 6 7 s 9
1 T i T a t 3 t 4 t 5 T ®
2 T i T a t 3 t 4 T j T$
3 T i T a t 3 t 4 T i T$
4 T i T : T 3 t 4 T i T ®
• Consider if K- segment pipeline with clock cycle tim e tp is used to execute n 
tasks. The first task Ti requires a tim e = K t p.
• 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 tim e = (n - 1 ) tp.
• Therefore, to com plete n tasks using a K-segment pipeline requires K + (n - 1) 
clock cycles.
• A non-pipeline unit perform the sam e operation and takes a tim e of tn to 
com plete each task. The total tim e required for n tasks in (n tn ).
• The speedup (S) is the ratio of a pipeline processing over an equivalent non­
pipeline processing.
(K + n — l) t p
Special Case: As number of tasks increases, n becomes larger than K - I, then K + 
n - I is approximately n. Then, speedup becomes 
If we assume t n = Ktp then
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 a instruction 
fetch unit and an instruction execution unit designed to provide two-segment 
pipeline.
• Complex instructions that requires other phases in addition to fetch and 
execute to process an instruction completely. The instructions cycle is as 
follows:
° Fetch the instruction from memory 
o Decode the instruction 
° Calculate the effective address 
° Fetch the operands from memory
Page 5


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 tim e and increase 
throughput.
There are more advantages with parallel processing but it has som e issues also. 
Due to parallel processing, the amount of hardware increases and the cost of 
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 organisation 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 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 (M IM D )
SISD: It represents the organisation of a single computer containing a control unit, 
a processor unit and a memory unit. Instructions are executed sequentially.
IS
SISD computer
SIMD: It represents an organisation that includes many processing units under the 
supervision d a common control unit. All processors receive the sam e instruction 
from the control unit but operate on different items of data.
SIMD computer
MISD: Its architecture contains n processors unit, each receiving instruction 
stream s and providing the sam e data stream. MISD structure is only of theoretical 
interest, since no practical system has been constructed using this organisation.
MISD computer
MIMD: Its organisation refers to a computer system capable of processing several 
programs at the sam e time.
MIMD computer
The operation of the CPU is usually described in term s of the Fetch-Execute cycle.
F e tc h -E x e c u te C y cle T h e cy cle ra ises m a n y in tere stin g q u e stio n s, 
e.g.
F e t ch th e In s tr u c tio n W h a t is a n In s tru c tio n ? W h e re is th e 
In s tru c tio n ? W h y d o e s it n e e d to b e fe tc h e d ? 
Is n 't it o k a y w h e re it is? H o w d o e s th e 
co m p u te r k e e p tra c k o f in s tru c tio n s? W h e re 
d o e s it p u t th e in s tru c tio n it h as ju s t fe tc h e d ?
In c re m e n t th e P r o g r a m 
C o u n te r
W h a t is th e P ro g ra m C o u n te r? W h a t d o e s th e 
P ro g ra m C o u n te r c o u n t? In c re m e n t b y h o w 
m u c h ? W h e re d o e s th e P ro g ram C o u n te r 
p o in t to a f te r it is in c re m e n te d ?
D e c o d e th e In s tru c tio n W h y d o e s th e in s tru c tio n n e e d to h e 
d e c o d e d ? H o w d o e s it get d e c o d e d ?
F e tc h th e O p e r a n d s W h a t a re o p e ra n d s ? W h a t d o e s it m e a n to 
fe tc h ? Is th is fe tc h in g d istin c t fro m th e 
fe tc h in g in S te p 1 a b o v e ? W h e re are th e 
o p e ra n d s? H o w m a n y a re th e re ? W h e re do 
w e p u t th e o p e ra n d s a f te r w e fe tc h th e m ?
P e rfo rm th e O p e ra tio n Is th is th e m a in ste p ? C o u ld n 't th e co m p u te r 
sim p ly h a v e d o n e th is p a rt? W h a t p a rt o f th e 
C P U p e rfo rm s th is o p e ra tio n ?
S to re th e resu lts W h a t re su lts? W h e re fro m ? W h e re to ?
R e p e a t fo rev e r R e p e a t w h a t? R e p e a t fro m w h e re ? Is it really 
a n in fin ite lo o p ? W h y ' 7 H o w d o th e s e steps 
e x e c u te an y in stru c tio n s at all?
In order to appreciate the operation of a computer we need to answer such 
questions and to consider in more detail the organisation of the CPU.
Pipelining
Pipeline processing is an implem entation technique, where arithmetic 
suboperations or the phases of a com puter instruction cycle overlap in execution. A 
pipeline can be visualised 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
Input
$ ¦ R , I S ; j-- ? R2 — «-| S3 j-- ? R3
• Each segment consists of a combinational circuit Si that performs a 
suboperation over the data stream flowing through pipe. The segments are 
separated by register Ri that hold the interm ediate 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 tim e. The 
horizontal axis displays the tim e in clock cycles and the vertical axis gives the 
segment number.
The space-tim e diagram shows the four segment pipeline with T i through T 6 
six tasks executed.
1 2 3 4 5 6 7 s 9
1 T i T a t 3 t 4 t 5 T ®
2 T i T a t 3 t 4 T j T$
3 T i T a t 3 t 4 T i T$
4 T i T : T 3 t 4 T i T ®
• Consider if K- segment pipeline with clock cycle tim e tp is used to execute n 
tasks. The first task Ti requires a tim e = K t p.
• 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 tim e = (n - 1 ) tp.
• Therefore, to com plete n tasks using a K-segment pipeline requires K + (n - 1) 
clock cycles.
• A non-pipeline unit perform the sam e operation and takes a tim e of tn to 
com plete each task. The total tim e required for n tasks in (n tn ).
• The speedup (S) is the ratio of a pipeline processing over an equivalent non­
pipeline processing.
(K + n — l) t p
Special Case: As number of tasks increases, n becomes larger than K - I, then K + 
n - I is approximately n. Then, speedup becomes 
If we assume t n = Ktp then
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 a instruction 
fetch unit and an instruction execution unit designed to provide two-segment 
pipeline.
• Complex instructions that requires other phases in addition to fetch and 
execute to process an instruction completely. The instructions cycle is as 
follows:
° Fetch the instruction from memory 
o 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 
sam e tim e. 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 tim e no update is made in the actual 
register. It can lead to Read Before Write hazard in the system.
3. Branch difficulties arise: It arises from branch and other instructions that 
change the value of 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 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 tim e 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 are 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 of 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 problem because 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 w rite/ 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 an 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 sam e tim e. The most 
common case in which this hazard may arise is in access to memory.