GATE CSE 2013 | Question: 45

Question

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

• A.  $132$   
• B.  $165$ 
• C.  $176$
• D.  $328$

Comments

@Ritik Jain RJ because it is the best case, that we come to know about branch decision in EX stage 

---

Always count for branch instruction separately. first instruction=5 Clock, now remaining (I2 I3 I10 I11 I12 I4)=6 clock and at last branch instruction will take 4 clock.

Total=(5+6+4)*11=165 ns

---

Because during execution only we came to know where we have to branch. During execution  effective address for the next instruction will be calculated and loaded into PC

Answer 1

We can determine  if the branch is taken or not after the execution stage  of the instruction I4.So number of stall cycles will be (4-1)=3.

Before the branch is taken total number of instructions is  4 and after branch is taken total number of instructions is 4 .So total number of instructions to be executed is 8.So we can assume the situation as we have total 8 instructions to be executed in pipelined manner without any stall cycles.

There are  5 stages in the pipeline.So the number of cycles needed to execute first instruction is 5.After that in each clock cycle one instruction will be completed.So total number of clock cycles needed is

5+(8-1)=5+7=12.

Due to branching number of stall cycles overhead is 3.

So total number of clock cycles needed=12+3=15.

time required to complete one clock cycle is =max stage delay+buffer overhead=10+1=11

So total time required will be = 15*11=165.

Answer 2

Selected answer is also good ,  

let me give you an alternative approach (short approach):

1 Branch instruction  out of  12 instruction 

1/12 branch instruction out of 1 instruction 

 

# stalls = 3 as branch resolved in 4TH stage i.e. EX stage 

CYCLE per instruction (c.p.i)= average cycle per instruction + (# inst per branch)(#stall per instruction) //          here symbol #   = number of

 

so  c.p.i. = 1+(1/12)(3) 

              = 1.25

total spent cycle = (Total instruction ) * (CYCLE per instruction) 

                            = 12*(1.25)

                           =  15 cycles 

one cycle time = (Max delay stage) + ( corresponding buffer delay )

                        =  10+1=11 ns 

Total spent time =  (total spent cycle  ) * ( one cycle time )  

                           =  15 *11

                           = 165 ns