edited by
47,547 views
96 votes
96 votes

Consider an instruction pipeline with five stages without any branch prediction:

Fetch Instruction (FI), Decode Instruction (DI), Fetch Operand (FO), Execute Instruction (EI) and Write Operand (WO). The stage delays for FI, DI, FO, EI and WO are $\text{5 ns, 7 ns, 10 ns, 8 ns and 6 ns},$ respectively. There are intermediate storage buffers after each stage and the delay of each buffer is $1\ \text{ns}.$ A program consisting of $12$ instructions $\text{I1, I2, I3,}\ldots,\text{ I12}$ is executed in this pipelined processor. Instruction $\text{I4}$ is the only branch instruction and its branch target is $\text{I9}.$ If the branch is taken during the execution of this program, the time (in ns) needed to complete the program is

  1.  $132$   
  2.  $165$ 
  3.  $176$
  4.  $328$
edited by

9 Answers

1 votes
1 votes

.......

 

1 votes
1 votes

No of instructions = 12

each clock cycle takes = 11ns (max(5,7,10,8,6) + 1ns)

I4 is the branch instruction so till I4 , 

I1-I3 will take total time of 11ns to execute so 3 * 11ns = 33ns

I4 

IF ID OF EX WB

So we know the target address of I9 only after completing the execution phase of I4 , but till that point I5 - I8 will already start

their execution , so there will be stalls or wastage of cycle till that point 

 

therefore time taken for I4-I8 to execute is = 5 * 11ns = 55ns (For all I1-I8 , CPI = 1 )

 

Then at I9 , CPI will be 4 ( As that will execute after execution phase so CPI = 4 for I9)

 

So time taken for I9 to execute = 4 * 11 = 44ns (CPI * time taken for each cycle) 

 

Then again from I10 - I12 again they take CPI = 1 , so time taken by them is = 3 * 11ns = 33ns

 

Total time taken to execute this program is = 33ns + 55ns + 44ns + 33ns = 165ns 

1 votes
1 votes

Given stage 1 = FI, stage 2=DI, stage 3= FO, stage 4=EI and stage 5=WO

Cycle time =  max(stage delays)+buffer delay = max(5,7,10,8,6) + 1 = 11ns

Question also mentions I4 is the only Branch Instruction out of I1,I2..I12.

So Branch % fraction = Number of Branch Inst / Total Inst = 1/12 

Question also mentions Branch is taken only after EI stage of I4 

Branch Penalty = Stage n – 1 = 4 – 1 = 3 (Here n =4)

#stalls/inst = Branch% fraction * Branch Penalty = 1/12 * 3 = 0.25

Avg_inst_exec_time = (1 + #stalls/inst)*cycle time = (1+ 0.25) * 11 = 13.75 ns

Total_exec_time =  Total  instructions * Avg_inst_exec_time = 12 * 13.75 = 165 ns = Option B

  Note: Better to follow this formula approach instead of drawing phase time table in GATE so that answer can be obtained under 2 mins without any mistake. These formulas are easy to remember and comes under branched instruction pipelining concept. But using phase time table you can also solve as

 

edited by
0 votes
0 votes
After pipelining we have to adjust the stage delays such that no stage will be waiting for another to ensure smooth pipelining (continuous flow). Since we can not easily decrease the stage delay, we can increase all the stage delays to the maximum delay possible. So, here maximum delay is 1010 ns. Buffer delay given is 1ns. So, each stage takes 1111 ns in total.

FI of I9 can start only after the EI of I4. So, the total execution time will be
 

15×11=165ns
Answer:

Related questions

42 votes
42 votes
5 answers
1
Arjun asked Sep 24, 2014
14,946 views
Consider the following sequence of micro-operations.MBR ← PC MAR ← X PC ← Y Memory ← MBRWhich one of the following is a possible operation performed by this seque...