GATE1999-13

Question

An instruction pipeline consists of $4$ stages – Fetch $(F)$, Decode field $(D)$, Execute $(E)$ and Result Write $(W)$. The $5$ instructions in a certain instruction sequence need these stages for the different number of clock cycles as shown by the table below

\begin{array}{|c|c|c|c|c|} \hline \textbf{Instruction} & \textbf {F} &\textbf {D} & \textbf {E} &  \textbf{W } \\\hline \textbf{1}& \text{$1$} & \text{$2$}  & \text{$1$} & \text{$1$} \\\hline \textbf{2} & \text{$1$} & \text{$2$} & \text{$2$}  & \text{$1$}\\\hline  \textbf{3}& \text{$2$} & \text{$1$}  & \text{$3$} & \text{$2$} \\\hline \textbf{4} & \text{$1$} & \text{$3$} & \text{$2$}  & \text{$1$} \\\hline \textbf{5} & \text{$1$} & \text{$2$} & \text{$1$}  & \text{$2$} \\\hline \end{array}

Find the number of clock cycles needed to perform the $5$ instructions.

Answer 1

Answer: 15 cycles are required.

$$\begin{array}{c|ccccccccccccc}
&t_1&t_2&t_3&t_4&t_5&t_6&t_7&t_8&t_9&t_{10}&t_{11}&t_{12}&t_{13}&t_{14}&t_{15}\\\hline
I_1&\text{F}&\text{D}&\text{D}&\text{E}&\text{W} \\ 
I_2&&\text{F}&-&\text{D}&\text{D}&\text{E}&\text{E}&\text{W}\\
I_3&&&&\text{F}&\text{F}&\text{D}&-&\text{E}&\text{E}&\text{E}&\text{W}&\text{W}\\
I_4&&&&&&\text{F}&-&\text{D}&\text{D}&\text{D}&\text{E}&\text{E}&\text{W}\\
I_5&&&&&&&&\text{F}&-&-&\text{D}&\text{D}&\text{E}&\text{W}&\text{W}\\
\end{array}$$

Comments

I think this is the correct sequence of fetch , unless the previous instruction goes into the next stage (here it is D stage)the current instruction can not enter into F stage.

---

@Arjun Sir then here we have assumed there is no data dependencies in instruction...I am just confused with the Execute of 1st instruction and decode of second instruction executing in the same column please clarify sir

---

yes, no dependency is assumed..

---

@Arjun sir, I have a doubt ,  I think F(fetch) operation of 2nd instruction should have started at 3rd clock cycle, otherwise it will overlap intermediate register's value and D(decode) operation of first instruction will not be executed correctly.

Similarly D(decode) operation of 3rd instruction should have started at 7th clock cycle, instead of 6th otherwise it will effect execution of 2nd instruction.

Please correct me if my understanding is wrong.

Thank you

---

what will be the answer ...if FETCH of instruction 3 ..takes 3 cycle instead of 2 ? plz help  if you can..?

---

Shreya Roy any references????

---

@Bikram  @Arjun

why the fetch operation of 3rd instruction is not starting at 3rd clock cycle?

sameway why fetch of 5th instruction is not starting at 7th clock?

---

thanks sir

---

why the F(fetch) operation of 3rd instruction cannot start with 3rd cycle.....if it would then total 14 cycles will be there...

---

Fetch phase of instruction 3 can be started from 3rd cycle if inter stage buffers are assumed..  in this question answer will remain same (i.e. 15 clock cycles) in both cases.

But number of cycles will depend on whether pipeline buffers are used or not.

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

---

@Arjun sir , its necessary that if in any instruction stall occur  , then in that particular cycle no instruction will execute . like in I4 , D could execute in t7. plz explain sir. 

---

No.

D can be executed in t7 but then stall will be created in $t_{10}$ due to overlapping of E. so answer remains same.

---

thanks @Satbir

---

@shivam001, @Satbir

in T7, Decode phase of I4 can't happen.

why because, I3 doesn't moved to Execute phase, So I3 is in Decode phase. One phase can have atmost one instruction only.

if there is a stall, then in that clock, no further changes.

---

But I3 requires only 1 clock cycle to complete the execute phase which it did in T6 right ?

---

in T6, I3 completes the decode phase but doesn't allowed to enter into Execute phase because of Execute phase is busy with I2.. that's makes a stall... So I3 is present in ID phase at clock 6 and clock 7... So I4 can't be in ID phase at clock 7

---

Ok so it means 1st comment of @shivam001 is correct.right ?

---

Regarding @Shreya Roy's comment, if you follow the pipelining lectures by Prof Matthew Jacob on NPTEL, he mentions that even if the previous instruction is undergoing a stall in that clock cycle, the hardware of that instruction's stage (for e.g., IF) is "occupied" and will be freed only when the instruction goes into the next stage.

So the current instruction is not allowed to do an IF stage in a cycle where the previous instruction is "stalled" in the IF stage.

---

@pritishc 

(I take my words back) but see this answer--

https://gateoverflow.in/1314/gate2009-28?show=7569#a7569

​​​​​

---

@Verma Ashish Okay this is definitely confusing. On that answer I see an instruction running $S_1$ in a cycle where the previous instruction is stalled in the $S_1$ stage. What is the answer if we account for hardware being occupied like in this question?

---

In this question answer will remain same (both the ways)..

Answer 2

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
F	D	D	E	W
	F	-	D	D	E	E	W
			F	-	D	-	E	E	E	W	W
					F	-	D	-	-	E	E	W
						F	-	-	-	D	-	E	W	W

therefore 15 clock cycles needed.

Comments

D of 3rd instruction is missing..

---

oops ... I have edited the answer Please check it again ...

---

please check IF(fetch) of I5. I think, it should be in clock 8 not in 7 as IF is not yet released by I4 .. And if we use the concept of the buffer then I2 and I3 should also use buffer concept  ??

---

yes @vijaycs I5  should be in clock 8

---

In 3rd instruction 1 F is missing

---

This answer has changed the question

Answer 3

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
F	D	D	E	W
	F	-	D	D	E	E	W
		F	F	-	D	-	E	E	E	W	W
				F	-	D	D	D	-	E	E	W
					F	-	-	-	D	D	-	E	W	W

I think this should be correct answer

 

Comments

@mehul vaidya 

​​​​​​instruction 3 -> clock 3 

check again.

---

@mehul vaidya, are you using concept of buffer? Because in question nothing is mentioned like that.

---

@Shubhgupta we can't start decode 7th clock, 4th instruction untill 3rd instruction enters in new phase?

---

yes @manisha11

---

@Shubhgupta

Sorry For Too Late Reply.

But from your comment can I conclude that 

If there are two instruction Inst1 & Inst2 such that inst2 is next to inst1

then inst2 can not enter in particular state , until inst1 has done with that state in last cycle?

---

Yes. correct