edited by
17,281 views
71 votes
71 votes

An instruction pipeline has five stages where each stage take 2 nanoseconds and all instruction use all five stages. Branch instructions are not overlapped. i.e., the instruction after the branch is not fetched till the branch instruction is completed. Under ideal conditions,

  1. Calculate the average instruction execution time assuming that 20% of all instructions executed are branch instruction. Ignore the fact that some branch instructions may be conditional.
  2. If a branch instruction is a conditional branch instruction, the branch need not be taken. If the branch is not taken, the following instructions can be overlapped. When 80% of all branch instructions are conditional branch instructions, and 50% of the conditional branch instructions are such that the branch is taken, calculate the average instruction execution time.
edited by

8 Answers

2 votes
2 votes

Part A:

suppose total instructions = n

time for each stage = 2 ns , CPI=stall + 1

average instruction execution time = ([no branch instrution * cpi * stage time] + [branch instrution * cpi *stage time])/total instruction

for branch instruction :

no. of stall = 4 , so, CPI=stall+1= 5

20 % of  total instructions are branch instructions = n * 0.2 

for no branch instruction :

no. of stall = 0 , so; CPI=stall + 1= 1

80 % of  total instructions are no branch instructions = n * 0.8

average time = ([n * 0.2 * 5 * 2]+[n * 0.8 * 1 * 2])/n = 3.6 ns

 

Part B:

this will be the graph to understand better :

this will be little hard to solve in terms of n , so take total instruction n= 100

then no branch instn= 80 , branch instn(conditional branch=16(branch taken=8 , branch not taken=8) , unconditional branch=4)

average instruction execution time = ([80*1*2]+[8*5*2]+[8*1*2]+[4*5*2])/100 = 2.96 ns

2 votes
2 votes

People who are still facing difficulty in understanding the question.Refer this I hope it will remove all your doubts.

a )Read the line very carefully "the instruction after Brach is not fetched till the branch is completed"

See the diagram below Considering there are 100 instructions.

20 % are branch means there are 20 branch and 80 instructions without any branch.

Solution 1-Consedering the case where every 5 the instruction is branch .

In that case 1st instruction takes 10ns and from 2nd to 5th it takes 2*4=8ns(following concept of pipelne).

So in total 5  instruction takes 18ns.

There are in total 20 sets of 5  instruction so total time is 20*18 =360ns.

Average time=360/100=3.6ns.

Solution -2 for part a

Considering all non branch instructions are executed in at once and all branch instructions at once.

Time for 80 instructions (non-branch)

10+79*2=168ns

Time for 20 instructions (branch)

20*10=200ns(as till branch is not completed another branch cannot fetched).

So total time=168+200=368ns

Average=368/100=3.68ns.

Solution 3 for part a-refering to Arjun sir solution

What sir has assumed is that is that the all non branch instruction takes=80*2 and not 10+79*2 reason being we can neglect the first instruction time as it will not affect much.

Total time for non branch=2*80=160ns

Non branch=20*10=200ns

Total time =200+160=360

Average time =360/100=3.6ns

Hope you now can do b part on your own.Still having issues comment.

2 votes
2 votes

 

 

I hope the solution is more clear now, I hope you got why we are taking 4 stalls.

As it is mentioned in the question itself that next instruction fetch is after the complete execution of the previous branch instruction.

 

Thanks

0 votes
0 votes

Execution time formula T1= $\frac{N*S}{R}$

Where N = dynamic instruction count

             S = Avg no. Of cycles to fecth and execte one instruction

            R = clock rate in cycles per second

 

Avg execution time T = $\frac{T1}{N}$

                                   T= $\frac{S}{R}$

 

Now according to question R = $\frac{1}{2 ns}$

So T = S *2 ns

For ideal pipelines S = 1

For non-ideal pipelines S = 1 + S' ( stall)

 

Now according to question when branch instruction is fetched next instruction is not fetched until after it's completion which means there is a stall of 4 cycles.

 

A).     20% instructions are branch instructions so 

            S' = 0.2*4 = 0.8

           S =1 + 0.8 = 1.8

 

So     T =1.8 * 2 ns

             =3.6 ns    (Ans)

 

B).      For Conditional Branch

                Branch prediction = Not taken

                If prediction true = overlapping done 

          This case gives us 0 stall.

                Prediction false = no overlapping

           This case gives us 4 stalls.

                S' = 0.2 * 0.8 *0.5 *4  ( 20 % branch instruction, 80% Conditional Branch , 50% branch taken giving false prediction)

                 S'  = 0.32

 

           For unconditional branch

                S' = 0.2 * 0.2 * 4

                    = 0.16

 

          So S = 1+0.32+0.16 = 1.48

 

              T = 1.48*2 ns

                 =2.96 ns (Ans)

       

   

 

edited by

Related questions

35 votes
35 votes
4 answers
1
Kathleen asked Sep 14, 2014
11,382 views
Comparing the time T1 taken for a single instruction on a pipelined CPU with time T2 taken on a non-pipelined but identical CPU, we can say thatT1 ≤ T2T1 ≥ T2T1 < T2T...