edited by
26,160 views
81 votes
81 votes
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 _________.
edited by

4 Answers

Best answer
119 votes
119 votes

$$\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

edited by
10 votes
10 votes

answer = $15$ cycles

6 votes
6 votes
 

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

 
–1 votes
–1 votes

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
Answer:

Related questions

38 votes
38 votes
5 answers
2
36 votes
36 votes
6 answers
3
go_editor asked Feb 13, 2015
15,514 views
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.