The Gateway to Computer Science Excellence
+31 votes
7.7k 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?

$$\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$
in CO and Architecture by Veteran (105k points)
edited by | 7.7k 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

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

Correct Answer: $B$

by Veteran (431k points)
edited by
+3

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

0

@Arjun sir

what about WAW dependency between t1(DIV) and t3(SUB) the question haven't mentioned anything about register renaming.

Can we take register renaming by default !?

Am I missing something? 

0
What is the issue with WAW dependency - it only matters if we do out of order execution.
0
sorry sir i was mistaken. thanks sir.
0

@Arjun @Bikram @habedo007 

I have understood the Operand Forwarding & Spilt Phase and have done Previous year questions as well. Just wanted to confirm that, Can we use Split Phase if we have Operand Forwarding from MA (Memory access) to EX (Execute) Stage i.e. between Write and Read (for any Stage to any Stage), irrespective of it is given in Question or not?

And someone in the comments section has written that, Use Split Phase only when we are given Operand Forwarding from Stage to Stage. Is it true?

Please reply.

0
0
0
0

 

Can someone tell me that why OF for I2 is being placed during the 4th cycle?

I mean the PO operation for  I1 is not yet over then if we perform OF of  I2 then the buffer for the OF stage  will be over written with that value computed by OF of the 2nd instruction right?

should'nt the below table be the answer?

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I1 IF ID OF PO PO PO WO                
I2   IF ID X X OF PO PO PO PO PO PO WO    
I3     IF X X ID X X X X X OF PO WO  
I4           IF X X X X X ID OF PO WO

 

0
0
0
@Arjun @Bikram

Why is the clock not considered to be the equal to that of the number of clocks taken by the longest instruction here?  each stage of pipeline takes Uniform clocks right?
0

@Arjun sir @Bikram sir

when OF is performed for I3 in cycle 7 & PO in cycle 13....does that mean R2 data is fetched in cycle 7 & R5 data is directly available in cycle 13 for PO operation?????

0

@Shaik Masthan

Instead of using the method mentioned by Arjun sir, can we go with split-phase b/w PO and OF stages?

Please verify.

0

In this answer, OF for Instruction 3 is done in t7. (Multiple stage buffer is not assumed)

@Arjun Sir, here you have mentioned the following:
"Multiple stage buffer - use it when there is a use :) That is if it can imporve the no. of cycles required use it unless otherwise stated in question or choice given otherwise."

Generally, what is the procedure that we should follow?

+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

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
50,737 questions
57,293 answers
198,232 comments
104,916 users