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

Since it is branch taken we will directly execute I9 once we get the target addres at I4, and that is done at execution stage (EI)

So for I1 TO I4:

K + N -1 (APPLY THIS FORMULA TO FIND NO OF CLOCK CYLES REQUIRED FOR A PIPELINE ONLY WHEN THERE IS NO HAZARD OTHERWISE DRAW AND SEE!)

Now, using this we can say that 5+4-1= 8 cycles but also note that we have to stall starting I9 until EI that is the 4th stage hence we'll have 3 stall cycles too as we know that for k stages we need k-1 stall cycles.

So, we can start I9 in the 8th cycle only so from there on again apply the formula of k+n-1 for I9 to I12:

we get 8 cycles from 8 that is total 15 cycles are required.

And we know that for pipeline no of cycles x cycle time which is simply max(stage delay + register delay)  that is 10+1 =11 ns

So 15 x 11 = 165

---

Why we require only 3 stalls ??

Reference : Carl Hamcher & Patterson Davie 

Assume "predict-not-taken" strategy 

==> The processor continues to fetch instructions sequentially ($I_1, I_2, I_3, \dots$) until a branch instruction evaluates its outcome and target address.

==>  In a standard 5-stage pipeline—Fetch Instruction (FI), Decode Instruction (DI), Fetch Operand (FO), Execute Instruction (EI), and Write Operand (WO), branch conditions are evaluated and target addresses are computed during the Execute Instruction (EI) stage.

==>  Once the branch is confirmed taken at the end of the EI stage, all instructions fetched  after the branch instruction must be flushed (discarded) from the pipeline. The time lost during this flushing process represents the branch penalty.

Understand through visualization :

The branch instruction $I_4$ enters the pipeline's FI stage at cycle $t_4$. Because the branch outcome isn't known until $I_4$ completes the EI stage at $t_7$, the FI stage cannot fetch the correct target instruction ($I_9$) during:

1) Cycle $t_5$ (while $I_4$ is in DI)

2) Cycle $t_6$ (while $I_4$ is in FO)

3) Cycle $t_7$ (while $I_4$ is in EI)

That's why 3 stall cycle required ($t_5, t_6, t_7$).

$\text{Branch Penalty} = \text{Stage Index of Resolution} - 1 = 4 - 1 = 3 \text{ cycles}$

Note :  Must read the answer given by Arjun sir 

---

Given that branch is taken after execution stage so extra stalls in I4 is 3 so total cycles required=(5(initial instrn )+7(remainig instr)+3(stall))=15cycles,
cycles time is 10(max stage)+1(buffer)=11ns
total time =15*11=165ns

Answer 1

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 $10$ ns. Buffer delay given is $1$ ns. So, each stage takes $11$ ns in total.

FI of $\text{I9}$ can start only after the EI of $\text{I4}.$ So, the total execution time will be
$$15 \times 11 = 165$$
$$\small \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
&\bf{t_1}&\bf{t_2}&\bf{t_3}&\bf{t_4}&\bf{t_5}&\bf{t_6}&\bf{t_7}&\bf{t_8}&\bf{t_9}&\bf{t_{10}}&\bf{t_{11}}&\bf{t_{12}}&\bf{t_{13}}&\bf{t_{14}}&\bf{t_{15}}\\
\hline
\textbf{I1}&\text{FI}&\text{DI}&\text{FO}&\text{EI}&\text{WO}\\
\textbf{I2}&&\text{FI}&\text{DI}&\text{FO}&\text{EI}&\text{WO}\\
\textbf{I3}&&&\text{FI}&\text{DI}&\text{FO}
&\text{EI}&\text{WO}\\
\textbf{I4}&&&&\text{FI}&\text{DI}&\text{FO}&\text{EI}&\text{WO}\\
&&&&&\color{red}{\text{stall}}\\
&&&&&&\color{red}{\text{stall}}\\
&&&&&&&\color{red}{\text{stall}}\\
\textbf{I9}&&&&&&&&\text{FI}&\text{DI}&\text{FO}&\text{EI}&\text{WO}\\
\textbf{I10}&&&&&&&&&\text{FI}&\text{DI}&\text{FO}&\text{EI}&\text{WO}\\
\textbf{I11}&&&&&&&&&&\text{FI}&\text{DI}&\text{FO}&\text{EI}&\text{WO}\\
\textbf{I12}&&&&&&&&&&&\text{FI}&\text{DI}&\text{FO}&\text{EI}&\text{WO}\\
\hline\end{array}$$

Correct Answer: $B$

Comments

@pranavbhosle_
I don't its nessesary true that uncoditional gets resolved in decode stage only, in decode stage we get to know if the instruction we have is branch type or not.

Suppose in ID stage of I4 it did get resolved still we will get 13 clock cycles = 13*11 ns = 143 ns (none options are matching)
Since it said branch is resolved during the executation of instruction we have these possibility 
after ID stage -> 13cc = 143ns
after FO stage->14cc=154 ns 
after EX stage->15cc=165 ns( option B)
after WB stage -> 16cc = 176ns  ( But if happens to be this, then the line given If the branch is taken during the execution of this program gets violated so this can't be it)

+ after IF stage can branch be resolved?? No cause we haven't even decoded it yet so 12cc=132ns is out of picture (if someone is confused)
Hence option B
Correct me if i am wrong :)  

---

@pranavbhosle_

Yes, for unconditional branch during decode stage we can know that it is unconditional branch, also branch target address can be calculated by using adder here.

For conditional branch, even if we use comparator in ID phase to check condition, for some condition we may need to checks flag and use ALU(like greater than) which is done in EX phase.

Also, for unconditional, it is not necessary that it will be PC relative mode (only common in RISC) where using Adder in ID we were able to get branch target address, for other architecture we can use multiple addressing modes, so for EA of branch we may need to use EX phase.

So, we are more inclined to wait till EX stage if no information is given.

Please correct me if there are any gaps in my understanding.

---

@divine_paragon can you bring the source pls

Answer 2

answer = option B

cycles in pink are stall cycles, at EI-4 it was notified to the system that instruction 9 has to be loaded next. 
We have completed execution in a total of 15 cycles where each cycle was (10+1)ns long,

Hence, answer = $15 \times 11 = 165$ns

Comments

How do you know that
at EI-4 it was notified to the system that instruction 9 has to be loaded next.  
Plz explain.

---

@Rajendra Dangwal Most satisfactory explanation. Thanks!

---

here 8 not consider bec , here branch prediction is not present so processor will not know that he have branch in 4 , so its keeps fetching instructions sequentially : 1 2 3 4 5 6 7 ... 

and the The branch is resolved in the Execute Instruction (EI) stage.
So when I4 reaches EI, the processor finally knows that the branch is taken and branch target is 9 .

At that instant: 

• 5 is already in FO
• 6 is already in  DI
•  7 has already in FI
   

  These are wrong path (stalls) . so They are immediately flushed  . so Before the processor could fetch 8 the processer already discover his terget is 9 ,  thats why 8 is not fetch

Answer 3

Clock Time = max stage delay + Buffer Delay

 = 10+1= 11ns

I1 - Finish at 5th clock

I2 - Finish at 6th clock

I3 - Finish at 7th clock

I4- Finish at 8th clock

Due to branching at I4 pipelining halts and starts after  EI stage of I4 and performs FI of I9 at 8th clock.

I9 - Finish at 12th clock

I10 - Finish at 13th clock

I11- Finish at 14th clock

I12 - Finish at 15 clock

Total time to complete program = 11*15= 165 ns

Comments

Nice logic.No confusion.

---

Short Trick : 

Branching descion will be taken in Execute Instruction (EI) phase (4th phase) so there will be 3 stalls

first I1 will complete in 5 cycles + (I2,I3,I4,3 STALLS,I9,I10,I11,I12) WILL TAKE ONE-ONE CYCLE=15 CYCLE

cycle time=(largest cycle time + buffer delay)=10+1=11

Execution time =11*15=165

Answer 4

.......

 

Comments

Which instruction is not executed out of 12 instructions?

---

how branch penalty is 3?

---

it is wrong solution ...total instruction to be executed is given to be 12....not 11

and also this is not the way to solve this question

Answer 5

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 6

1) Total Cycles if there were no stalls or branching = k + (n-1) = 5 + ( 12-1) = 16 cycles

where k = number of stages in pipeline and n = total number of instructions

2) Due to branching, we jump over/skip I5, I6, I7, I8; four instructions are skipped; updated number of cycles = 12 cycles

3) Branch is resolved at 4th stage (EI) Therefore,

number of stalls = 4-1 = 3 cycles 

Final number of cycles = 12 + 3(stalls) = 15 cycles

Cycle time = 10 + 1= 11ns

Execution time = cycle time * number of cycles = 11 ns * 15 = 165 ns