The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+23 votes
5.8k views

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?

Instruction    Meaning of instruction
$t_0: \text{MUL} \:\text{R}_2,\text{R}_0,\text{R}_1$ $\text{R}_2  \gets \text{R}_0*\text{R}_1$
$t_1: \text{DIV}\: \text{R}_5,\text{R}_3,\text{R}_4$ $\text{R}_5 \gets \text{R}_3 / \text{R}_4$
$t_2: \text{ADD}\: \text{R}_2,\text{R}_5,\text{R}_2$ $\text{R}_2 \gets \text{R}_5 + \text{R}_2$
$t_3: \text{SUB} \:\text{R}_5,\text{R}_2,\text{R}_6$   $\text{R}_5 \gets \text{R}_2 - \text{R}_6$
  1. $13$
  2. $15$
  3. $17$
  4. $19$
asked in CO & Architecture by Veteran (112k points)
edited by | 5.8k views
0
Can anybody could explain, why are we not considering WAW dependency between t1 and t3 (due to R5). Untill t1 WO operation performed how can t3 perform OF operation, as it could lead to wrong result.

I understand the Operand forwarding for t1 - t2.Also operand forwarding for t2- t3. Why are we ignoring WAW between t1 and t3

2 Answers

+42 votes
Best answer

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

answered by Veteran (370k points)
edited by
0
Why is OF of instruction(t2) at t7 and not t12?
0
@Sumaiya23 Because (OF) stage was available at t7.
0
Yes, but instruction(t2) reads R5 which is written by instruction(t1), this operation PO completes at t12. Even if OF stage is available t7, the execution of PO stage will be completed only at t12, so the (updated and correct)value of R5 will be available at t12 and not at t7.
0
Operand forwarding is used. Generally operand is forwarded in EX-EX stage (unless stated otherwise), so the pipeline here is deliberately letting (OF) of T2 fetch the wrong value because the updated value will be automatically provided after the (PO) of T1.
0

So operand forwarding is done from t12 to t13. I get it!

But is it wrong to say OF (of instruction t2) takes place at t12? If so why? And, is this the default behavior when operand forwarding is mentioned? Because I remember a certain similar problem of previous GATE, where the selected answer had shown the stage (similar to the image attached in this comment) at the end of the previous stage of the previous instruction, (though I don't remember the year and question number).

0
OF at t7 or at t12 will not affect the final answer, but I wonder which one would be more appropriate and why.
0
Are you sure that question of yours had OF stage at t12 (assume)? It may be that stage was in use by previous process till t11. You should check out that question again.
0

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

Going by the operand forwarding logic, ID of I3 should have been in C4 instead of C6, but C4 and C5 have been shown as stalls.

0

It is given in that question that operand forwarding is being done in EX-ID stage. The result of MUL is produced in 6th cycle, that is why ID is present at 6th cycle instead of 4th.

+2

This the design issue. It will be more appropriate to say t6 of MUL and t12 ADD are OF because OF may be in use by previous instruction for EX OR It is a possibility too that OF before would alter them.

So, this follow solution from G4G would be more appropriate

+6 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

answered by Active (2.4k points)
reshown by
0

Why PO of I2 and OF of I3 in the same column???

 OF stage of i3 has to wait till PO stage of i2 is finished to get its input nah??

0
moral of the story ::

when in pipelining the dependency in previous cycle and upcoming cycle is remain till thn put stall .
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,510 questions
49,966 answers
165,818 comments
65,915 users