edited by
21,793 views
47 votes
47 votes

A $5-$stage pipelined processor has Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Write Operand (WO) stages. The IF, ID, OF and WO stages take $1$ clock cycle each for any instruction. The PO stage takes $1$ clock cycle for ADD and SUB instructions, $3$ clock cycles for MUL instruction and $6$ clock cycles for DIV instruction respectively. Operand forwarding is used in the pipeline. What is the number of clock cycles needed to execute the following sequence of instructions?

$$\begin{array}{|c|l||} \hline  \textbf {Instruction} &  \textbf{Meaning of instruction}  \\\hline  \text{$t _0$: MUL $R _2$,$R _0$,$R _1$} & \text{R}_2  \gets \text{R}_0*\text{R}_1\\\hline  \text{$t _1$: DIV $R _5,R _3,R _4$} & \text{R}_5 \gets \text{R}_3 ∕ \text{R}_4\\\hline   \text{$t _2$: ADD $R _2,R _5,R _2$} & \text{R}_2 \gets \text{R}_5 + \text{R}_2 \\\hline t_3: \text{SUB} \:\text{R}_5,\text{R}_2,\text{R}_6 & \text{R}_5 \gets \text{R}_2 - \text{R}_6  \\\hline\end{array}$$

  1. $13$
  2. $15$
  3. $17$
  4. $19$
edited by

3 Answers

Best answer
76 votes
76 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{MUL}&\text{IF}&\text{ID}&\text{OF}&\text{PO}&\text{PO}&\text{PO}&\text{WO}\\
\textbf{DIV}&&\text{IF}&\text{ID}&\text{OF}&\color{red}{-}&\color{red}{-}&\text{PO}&\text{PO}&\text{PO}&\text{PO}&\text{PO}&\color{green}{\boxed{\text{PO}}}&\text{WO}\\
\textbf{ADD}&&&\text{IF}&\text{ID}&\color{red}{-}&\color{red}{-}&\text{OF}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}
&\color{blue}{\boxed{\color{green}{\boxed{\text{PO}}}}}&\text{WO}\\
\textbf{SUB}&&&&\text{IF}&\color{red}{-}&\color{red}{-}&\text{ID}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}
&\text{OF}
&\color{blue}{\boxed{\text{PO}}}&\text{WO}\\
\hline\end{array}$

Operand forwarding allows an output to be passed for the next instruction. Here from the output of PO stage of DIV instruction operand is forwarded to the PO stage of ADD instruction and similarly between ADD and SUB instructions. Hence, $15$cycles required.

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

Correct Answer: $B$

edited by
7 votes
7 votes

Let IF=F, ID=D, OF=O, PO=P, WO=W

   

I1 FDOPPPW 

I2 HFDO--PPPPPPW

I3 HHFD-------OPW   

I4 HHHFD-------OPW

(I3 depends upon R5 n R2, n using operator forwarding we can use R5 value directly when PO of I2 completes). Same happens for I4. So the total time taken until I4 completion is 15. (B) would be correct answer

reshown by
0 votes
0 votes

It is very easy.

Hope my solution makes you understand

Answer:

Related questions

37 votes
37 votes
5 answers
3
73 votes
73 votes
10 answers
4
go_editor asked Apr 21, 2016
26,929 views
A hash table of length $10$ uses open addressing with hash function $h(k) = k \: \mod \: 10$, and linear probing. After inserting $6$ values into an empty hash table, the...