• edited by
46,824 views
117 117 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 _________.

8 Answers

Best answer
160 160 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
12 12 votes

answer = $15$ cycles

11 11 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

 
Answer:
Position:
Show:

Related questions

79 79 votes
11 answers 11 answers
33.9k
33.9k views
go_editor asked Sep 28, 2014
33,894 views
Consider a $6$-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is exec...
199 199 votes
9 answers 9 answers
78.8k
78.8k views
Kathleen asked Sep 22, 2014
78,754 views
A $5$ stage pipelined CPU has the following sequence of stages:IF – instruction fetch from instruction memoryRD – Instruction decode and register readEX – Execute: ALU op...
74 74 votes
4 answers 4 answers
35.9k
35.9k views
Kathleen asked Sep 12, 2014
35,865 views
Which of the following are NOT true in a pipelined processor?Bypassing can handle all RAW hazardsRegister renaming can eliminate all register carried WAR hazardsControl h...
54 54 votes
7 answers 7 answers
23.5k
23.5k views
go_editor asked Feb 12, 2015
23,457 views
Assume that for a certain processor, a read request takes $50\:\text{nanoseconds}$ on a cache miss and $5\:\text{nanoseconds}$ on a cache hit. Suppose while running a pro...