techtud's picture

Pipelining: Processor Pipelining, Stalls, Dependencies and Hazards.

Pipelining

Pipelining is an implementation technique where multiple instructions are overlapped in execution. The computer pipeline is divided in stages. Each stage completes a part of an instruction in parallel. The stages are connected one to the next to form a pipe - instructions enter at one end, progress through the stages, and exit at the other end.
Pipelining does not decrease the time for individual instruction execution. Instead, it increases instruction throughput. The throughput of the instruction pipeline is determined by how often an instruction exits the pipeline.
Because the pipe stages are hooked together, all the stages must be ready to proceed at the same time. We call the time required to move an instruction one step further in the pipeline a machine cycle . The length of the machine cycle is determined by the time required for the slowest pipe stage.
Speed up = Time taken without pipelining / Time taken with pipelining
Speed up = m* Efficiency ; m is the number of phases.

0Comment
Pipelining in a Processor
Content covered: 

Pipelining in a Processor

More Less
1Comment
Processor Pipeline Stalls
Content covered: 

Processor Pipeline Stalls

More Less
0Comment
Dependencies and Hazards
Content covered: 

Dependencies and Hazards

More Less
0Comment
Data Dependencies
Content covered: 

Data Dependencies

More Less
2Comments
Control Dependencies
Content covered: 

Control Dependencies

More Less
1Comment
Consider a 4-stage pipeline processor

Consider a 4-stage pipeline processor. The number of cycle needed by the four instruction l1, l2, l3, l4 in stages S1, S2, S3, S4 is show below

  S1 S2 S3 S4
l1 2 1 1 1
l2 1 3 2 2
l3 2 1 1 3
l4 1 2 2 2

The number of cycles needed to execute the following loop is ____________.

for(i=1 to 2)
{     l1; l2; l3; l4;
}

for i = 1,

Clock Cycle 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
l1 S1 S1 S2 S3 S4                      
l2 - - S1 S2 S2 S2 S3 S3 S4 S4            
l3 - - - S1 S1 - S2 - S3 - S4 S4 S4      
l4 - - - - - S1 - S2 S2 S3 S3 - - S4 S4  

So, total 15 clock cycles are required for i = 1
Hence, it should take 15 clock cycles for next iteration for i = 2; hence total cycles should be 15x2 = 30.
But it is not the case.
2ns execution of the loop will start with l1 which needs S1. The stage S1 will be free to use on 7th clock cycle after l4 releases it. Hence, we can extend the above pipeline execution diagram which will give us the required clock cycle as 23 cycles.

Clock Cycle 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
l1 S1 S1 S2 S3 S4                                    
l2 - - S1 S2 S2 S2 S3 S3 S4 S4                          
l3 - - - S1 S1 - S2 - S3 - S4 S4 S4                    
l4 - - - - - S1 - S2 S2 S3 S3 - - S4 S4                
l1 - - - - - - S1 S1 - S2 - S3 - - - S4              
l2 - - - - - - - - S1 - S2 S2 S2 S3 S3 - S4 S4          
l3 - - - - - - - - - S1 S1 - - S2 - S3 - - S4 S4 S4    
l4 - - - - - - - - - - - S1 - - S2 S2 S3 S3 - - - S4 S4

7Comments
Effective CPI

Consider a pipelining with m stage and n instructions. The probabilities that a instruction will be conditional is 'p' and it will evaluates to be true is 'q'. What can be effective CPI ?
(A) 1+pq(n-1)
(B) 1+pq(m-1)
(C) 1+mpq(n-1)
​(D) 1+npq(n-1)

 

Total number of conditional branch instructions= np
Total number of instructions which actually branch = npq
Total number of instruction which will not branch = n-npq = n(1-pq)
Effective CPI = (m*npq+n(1-pq))/n
=mpq+(1-pq)
=1+pq(m-1)

0Comment

  • This quiz contains 5 questions on the topic Pipelining.
  • Lean well before you attempt the quiz.
  • You can attempt the quiz unlimited number of times.

Difficulty Level:  basic
No. of Questions:  5
Shivesh Kumar Roy shiveshroy 6 Jan 2017 01:04 am

I would like to request the admin to please correct the answer of question no. 5 of the quiz, The answer for that question should be (B).

Here is the explanation link

http://gateoverflow.in/447/gate2008-36

Pages