Pipelining: Processor Pipelining, Stalls, Dependencies and Hazards.

Content: 

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.


Content covered: 

Pipelining in a Processor

Responses

In the above video how throughput becomes 1/4ns? Can any one explain?


Content covered: 

Processor Pipeline Stalls


Content covered: 

Dependencies and Hazards


Content covered: 

Data Dependencies

Responses

akhileshgang's picture

sir if it is mentioned that it is 5 stage pipeline then only possible hazard is RAW . Is it true 

amit17's picture

i dont think so hazards depends upon the instruction , not on # of stages.


Content covered: 

Control Dependencies

Responses

piyushbadkul's picture

?

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;
}
  • Explanation

    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

Responses

More Comments

24 should be the answer

amit17's picture

yes 24 should be the answer bkz in solution I4 in clock cycle 6 s1 cant be there.

why I4 in clock cycle 6 s1 can't be there??

patel512's picture

No 23 is right

An instruction is eligible to run in second iteration of loop if it has completed its execution previous iterations. I1 has completed its first iteration before cycle 6 starts and hence can be executed in cycle 6.

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)

 

  • Explanation

    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)

  • 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

Awesome, you did good to complete todays course.

To continue your preparation while we publish tomorrow’s topic,

please subscribe to our youtube channel.

 

Responses

shiveshroy's picture

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

Enter your search keyword:

Search form

Wait!

Here is a chance to join biggest community of technical Students,
Tutors with FREE learning resources and so much more.
It takes less then 60 seconds.