GATE IT 2004 | Question: 47

Question

Consider a pipeline processor with $4$ stages $S1$ to $S4$. We want to execute the following loop:

for (i = 1; i < = 1000; i++) 
    {I1, I2, I3, I4} 

where the time taken (in ns) by instructions $I1$ to $I4$ for stages $S1$ to $S4$ are given below:

$$\begin{array}{|c|c|c|c|c|} \hline  & \textbf {$S _1$} &\textbf {$S _2$} & \textbf {$S _3$} &  \textbf{$S _4$ } \\\hline \textbf{I1}& \text{$1$} & \text{$2$}  & \text{$1$} & \text{$2$} \\\hline \textbf{I2} & \text{$2$} & \text{$1$} & \text{$2$}  & \text{$1$}\\\hline  \textbf{I3}& \text{$1$} & \text{$1$}  & \text{$2$} & \text{$1$} \\\hline \textbf{I4} & \text{$2$} & \text{$1$} & \text{$2$}  & \text{$1$} \\\hline \end{array}$$

The output of  $I1$ for $i = 2$ will be available after

• A. $\text{11 ns}$
• B. $\text{12 ns}$
• C. $\text{13 ns}$
• D. $\text{28 ns}$

Comments

Best method @Surya013

https://m.youtube.com/watch?v=1CR8dqIaelg&t=3672s&pp=2AHYHJACAQ%3D%3D

Similar Question : https://gateoverflow.in/1512/gate-cse-1999-question-13

---

Ans

---

OG method

Answer 1

$$\begin{array}{|c|c|c|c|c|} \hline \textbf{}  & \textbf {t1} & \textbf {t2} & \textbf {t3} & \textbf {t4} & \textbf {t5} & \textbf {t6} & \textbf {t7} & \textbf {t8} & \textbf {t9} & \textbf {t10} & \textbf {t11} & \textbf {t12} & \textbf {t13}  \\\hline \textbf{I1}& \text{$s _1$} & \text{$s _2$}  & \text{$s _2$} & \text{$s _3$} &  \text{$s _4$} &  \text{$s _4$} \\\hline \textbf{I2} & & \text{$s _1$} & \text{$ s _1$} & \text{$ s _2$}  & \text{$s _3$} & \text{$s _3$} & \text{$s _4$}\\\hline  \textbf{I3}& & & &\text{$s_1$} & \text{$s_2$}  & \text{--}&\text{$s_3$} & \text{$s _3$}  & \text{$s _4$}\\\hline \textbf{I4} & &&&&\text{$s_1$} & \text{$s_1$} & \text{$s_2$} & \text{--} & \text{$s_3$} & \text{$s _3$}& \text{$s _4$}\\\hline \textbf{I5} & &&&&&&\text{$s_1$} & \text{--} & \text{$s_2$} & \text{$s _2$} & \text{$s_3$} & \text{$s _4$}& \text{$s _4$}\\\hline \end{array}$$

So, total time would be $13\;ns$

Option (c).

Comments

You are right.

---

The answer is 13 ns, but in the 2nd time for I1 ,S2 phase will not start at 8th cycle bcz S3 for I4 has not stated yet.So S2 will start at 9th cylcle and so both 9th and 10th cycle will be used by S2 of I1 (in the 2nd time) thus the total clock cycles still remain 13.

1

2

3

4

5

6

7

8

9

10

11

12

13

I1

s1

s2

s2

s3

s4

s4

I2

s1

s1

s2

s3

s3

s4

I3

s1

s2

s3

s3

s4

I4

s1

s1

s2

s3

s3

s4

I1

s1

s2

s2

s3

s4

s4

---

yes, thats correct.

---

@Arjun @Uddipto

I read on some gate question here only that sufficient buffers can be assumed in the pipeline questions. So why can't we start S2 of I1 at 8th cycle?

---

Buffers are considered for operand forwarding.

Since nothing is mentioned about operand forwarding, we don't consider buffers here

---

Why we have put s1 stage of i4 instruction in 6th cycle when i3 instruction is waiting for s3 stage in that cycle Kkk got it as s1 stage  of  i4  depends  on s2 stage of  i3 and It has been  completed

---

Can some one tell me why loop unrolling concepts is not used here like in this one:-https://gateoverflow.in/1314/gate2009-28 .Can some one explain when to use loop enrolling and when not to.Although answer will be same but with loop unrolling for second iteration of I1 it can do work in 8th and 9th clock cycle and not in 9th and 10th clock cycle.Please help here

---

I am not able to understand why S2 started at 9th clock and not at 8th clock, I am not able to understand the reason behind it.

---

In pipeline execution, each stage produces output to a buffer and next stage takes it from there. So, unless the previous instruction goes to the next stage, the current instruction cannot execute a given stage. But this problem can be avoided if multiple buffers are used (or a queue).

---

Thanks Sir, got it now!

---

Sir but why are we not assuming the use of queue as in  https://gateoverflow.in/1314/gate2009-28

---

Because it doesnt make a difference here. As long as all stages are taking same cycles, we dont need a queue.

---

@rahul sharma 5

Even you consider loop level parallelism for it you will still get answer as 13ns.

---

@Arjun sir. In pipelined architecture, don't we consider the slowest stage time as the time fr each stage?

Then why don't we consider in this question that since the maximum time taken by any instruction in any stage is 2 units, therefore every stage will be synchronized with a clock so that each stage takes 2 unit time? I am having a lot of confusion in this subject. Can you please tell me some resource to study this from.

---

@Arjun sir,You mentioned

Because it doesnt make a difference here. As long as all stages are taking same cycles, we dont need a queue.

But here also different stage delays are there.I am getting same answer with both(with and without loop level enrollment),but it will not be same always as in https://gateoverflow.in/1314/gate2009-28

---

same doubt.

as here:https://gateoverflow.in/1512/gate1999_13

---

In the below example, it was said that "multiple stage buffers which can queue the result of the stages"

then in the second iteration s2 should start in 8 clk cycle. Is it ?

https://gateoverflow.in/1314/gate2009-28

---

@Arjun sir, @Shaik Masthan , @sushmita , @Ayush Upadhyaya

When should we consider stage buffers as queue and when not ..because of which answers may be different here it is same but for this https://gateoverflow.in/1512/gate1999-13 

BY DEFAULT ..we should consider a single buffer right not as queue right ???? ..that is unless prev instruction leaves stage and get into next stage current instruction can't enter into that stage

---

yes single stage buffer

Suppose $I_{1}$ Decode stage started, with that $I_{2}$ instruction Fetch stage can start

---

Can someone please tell where to study the concept of multistage bufffer

---

I have the same doubt. Did you get an answer @Rishabh Gupta 2 ? Slowest stage time for each stage is considered in this question: https://gateoverflow.in/1063/gate2004-69. So why are we not doing the same here? Arjun sir also mentioned in a comment for that answer that if no information about clock rate is given, we must assume uniform clock rate. Therefore, clock period for this question should be considered as 2ns. Please correct me if I am wrong

---

@Pascua if your doubt is cleared then please explain.

---

There’s mistake here although this is giving the correct ans but for I5 s2 shd be in t8 and t9 and not in t9 and t10. correct me if i am wrong

---

@ankit3009  if your doubt is cleared then please explain.

---

why was the 5th instruction taken?
please help

---

@Gunda Rama Sravan $I5$ is nothing but $I1$ for iteration $i=2$

---

@MWR  if your doubt is cleared then please explain.

all i get from chatgpt is that if its given fixed clock cycle then we have to use max of stages time and if given variable time of each stages of instructions then use that time for calculation . 

---

Utkarsh singh_1

The pipeline has a stage delay of 2 ns because the maximum time required by any instruction in any stage is 2 ns.So, the pipeline's stage delay is 2 ns.
However, the table gives the actual time that each individual instruction spends performing its operation in each stage. For example, I1 takes only 1 ns in S1 but takes 2 ns in S2.

Pipeline stage capacity = 2 ns

I1 in S1:
|---- 1 ns ----|---- unused 1 ns ----|
|<------------- 2 ns ---------------->|
Since we are only asked the time taken by the instructions...So we take 1ns as base time and plot the pipeline according to the time taken by the instructions

My reasoning on this question is due to this question...
https://gateoverflow.in/1314/gate-cse-2009-question-28
This question also asks the number of cycles so we actually keep 1 cycle as base cycle and plot the pipeline according to the cycles it takes at particular stage

Answer 2

ans) 13

Comments

why have you done I1 I2 I3 I4 and again I1 for each stage.

---

@PAVANCHYTANYA loop hai na bhai 

Answer 3

Silly mistake should be taken care of

Remember we have to find second iteration of Instruction I1 finish time.

Comments

Actually you made a silly mistake here. Check the answers given by others, there will be a stall at 8^th clock cycle when I1 is executing for second time. 

Answer 4

Ans

Answer 5

Option C. 13ns