GATE CSE 2015 Set 2 | Question: 44

Question

Consider the sequence of machine instruction given below:
$$\begin{array}{ll} \text{MUL} & \text{R5, R0, R1} \\  \text{DIV} & \text{R6, R2, R3} \\   \text{ADD} & \text{R7, R5, R6} \\  \text{SUB} & \text{R8, R7, R4}  \\ \end{array}$$
In  the above sequence, $R0$ to $R8$ are general purpose registers. In the instructions shown, the first register shows the result of the operation performed on the second and the third registers. This sequence of instructions is to be executed in a pipelined instruction processor with the following $4$ stages: $(1)$ Instruction Fetch and Decode $(IF)$, $(2)$ Operand Fetch $(OF)$, $(3)$ Perform Operation $(PO)$ and $(4)$ Write back the result $(WB)$. The $IF$, $OF$ and $WB$ stages take $1$ clock cycle each for any instruction. The $PO$ stage takes $1$ clock cycle for ADD and SUB instruction, $3$ clock cycles for MUL instruction and $5$ clock cycles for DIV instruction. The pipelined processor uses operand forwarding from the PO stage to the OF stage. The number of clock cycles taken for the execution of the above sequence of instruction is _________.

Comments

@Venkat Sai  -- I am totally confused over this SPLIT PHASE thing. Please, can you provide any reference for reading about the SPLIT PHASE. It's not given in Hamacher or any of the NPTEL lectures (IISC, IIT KGP, IITD).

---

similar

https://gateoverflow.in/3623/gate2006-it-79

https://gateoverflow.in/1235/gate2007-37-isro2009-37

https://gateoverflow.in/2207/

---

From exam pov : (You will not draw that much big table in the exam)

No. of Instructions=n=4

No. of stages=k=4

No. of cycles =k+(n-1) =7 ,

But 2 extra cycles are required for MUL and 4 extra for DIV.Total cycles = 7+2+4=13

Answer 1

$$\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{IF}&\text{OF}&\text{PO}&\text{PO}&\text{PO}&\text{WB}\\
\textbf{I2}&&\text{IF}&\text{OF}&\color{red}{-}&\color{red}{-}&\text{PO}&\text{PO}&\text{PO}&\text{PO}&\color{green}{\boxed{\text{PO}}}&\text{WB}\\
\textbf{I3}&&&\text{IF}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{green}
{\boxed{\text{OF}}}&\color{blue}{\boxed{\text{PO}}}&\text{WB}\\
\textbf{I4}&&&&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\text{IF}&\color{red}{-}
&\color{blue}{\boxed{\text{OF}}}
&\text{PO}&\text{WB}\\
\hline\end{array}$$

It is mentioned in the question that operand forwarding takes place from PO stage to OF stage and not to PO stage. So, $15$ clock cycles.

But since operand forwarding is from PO-OF, we can do like make the PO stage produce the output during the rising edge of the clock and OF stage fetch the output during the falling edge. This would mean the final PO stage and OF stage can be done in one clock cycle making the total number of cycles $=$ $13$. And $13$ is the answer given in GATE key. 

$$\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}}\\
\hline
\textbf{I1}&\text{IF}&\text{OF}&\text{PO}&\text{PO}&\text{PO}&\text{WB}\\
\textbf{I2}&&\text{IF}&\text{OF}&\color{red}{-}&\color{red}{-}&\text{PO}&\text{PO}&\text{PO}&\text{PO}&\color{green}{\boxed{\text{PO}}}&\text{WB}\\
\textbf{I3}&&&\text{IF}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{green}
{\boxed{\text{OF}}}&\color{blue}{\boxed{\text{PO}}}&\text{WB}\\
\textbf{I4}&&&&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\text{IF}
&\color{blue}{\boxed{\text{OF}}}
&\text{PO}&\text{WB}\\
\hline\end{array}$$ Reference: https://web.archive.org/web/20120105062937/http://www.cs.iastate.edu/%7Eprabhu/Tutorial/PIPELINE/forward.html

Comments

http://www.cs.iastate.edu/~prabhu/Tutorial/PIPELINE/forward.html

@Arjun sir this link does not redirect to the relevant page anymore

---

If nothing is mentioned in the question ( whether to use split phase or not) always go for the best possible case 
Here, they didn’t mention, only have written the pipelined processor uses operand forwarding from the PO stage to the OF stage. 
 

So, I have done it by both the methods (keeping split phase under consideration and without split phase) 
you get 15 clock cycles without split phase PO → OF
but if you use split phase , 13 is the answer from PO → OF ( as per qs ). Once again if you see carefully 
split phase is nothing but very similar to full-forwarding leaving no stalls due to any dependency that is PO → PO stage.

1

2

3

4

5

6

7

8

9

10

11

12

13

I1

IF

OF

PO

PO

PO

WB

I2

IF

OF

PO

PO

PO

PO

PO

WB

I3

IF

OF

PO

WB

I4

IF

OF

PO

WB

The above table gives answer as 13 (full-forwarding from PO → PO or by split phase from PO → OF ).

 

---

@rushilKJ Your explanation is great, i just went through a whole revision from every sources, and according to @Deepak Poonia lectures on pipeline on YouTube, he have told to consider not to consider split-phase by default. The answer should have been 15 or the question should have properly mentioned about the way it is operand forwarding according to split-phase. So i think this question is a lot ambiguous.

Answer 2

answer = $15$ cycles

Comments

sir,  lets say OF stage  takes  2 cycle, then also OF would come in 10 th cycle for I3 thereby increasing one more cycle or we can OF in 9th and 10th cycle so that PO phase can be in 11th cycle.

or PO  would be in 12 th cycle then???

---

If anyone is confused by amarvashisth’s explanation , read the comment by Sachin Mittal on the best-chosen answer.

Split phase access has nothing to do with Operand Forwarding. Even if we use split-phase access we will still NEED operand forwarding.

So, the answer is 13 because we are using Operand Forwarding and also assuming that split-phase access is taking place by default.

---

How to know what to assume and what not to? His and every other option suggesting use of split phase is based on the answer given in gate key. There is nothing in the question suggesting that split phase is used. Since the answer is 13, we are coming to the conclusion that split phase is used.

But in exam they won’t provide the answer key. 😢

So, how to proceed with such question?

Answer 3

t1

t2

t3

t4

t5

t6

t7

t8

t9

t10

t11

t12

t13

I1

IF

OF

PO

PO

PO

WB

I2

IF

OF

-

-

PO

PO

PO

PO

PO

WB

I3

IF

-

-

-

-

-

-

OF

PO

WB

I4

-IF

-

-

-

-

-

OF

PO

WB

 

Comments

is this correct ??

if not then why?

---

Yes it is correct..

https://www.cs.uaf.edu/2011/fall/cs441/lecture/09_20_pipelining.html

---

answer is 11 ?
MUL R5, R0, R1
DIV R6, R2, R3 <- here register carring operandsfor both instruction are not same .. so we proceed PO for second intruction at 4 itself and will end WB at 9..

so final answer must be 11 .. kindly crct me if i am wrong ...?

Answer 4

Is it a correct answer ???

	t1	t2	t3	t4	t5	t6	t7	t8	t9	t10	t11	t12	t13	t14	t15
I1	IF	OF	PO	PO	PO	WB
I2		IF	OF	-	-	PO	PO	PO	PO	PO	WB
I3			IF	OF	-	-	-	-	-	-		PO	WB
I4				IF	OF	-	-	-	-	-	-	-	-	PO	WB

Comments

but they have asked to use operand forwarding from po to of.