in CO and Architecture recategorized by
5,980 views
10 votes
10 votes
Consider a pipelined processor with $5$ stages, $\text{Instruction Fetch} (\textsf{IF})$, $\text{Instruction Decode} \textsf{(ID)}$, $\text{Execute } \textsf{(EX)}$, $\text{Memory Access } \textsf{(MEM)}$, and $\text{Write Back } \textsf{(WB)}$. Each stage of the pipeline, except the $\textsf{EX}$ stage, takes one cycle. Assume that the $\textsf{ID}$ stage merely decodes the instruction and the register read is performed in the $\textsf{EX}$ stage. The $\textsf{EX}$ stage takes one cycle for $\textsf{ADD}$ instruction and the register read is performed in the $\textsf{EX}$ stage, The $\textsf{EX}$ stage takes one cycle for $\textsf{ADD}$ instruction and two cycles for $\textsf{MUL}$ instruction. Ignore pipeline register latencies.

Consider the following sequence of $8$ instructions:
$$\textsf{ADD, MUL, ADD, MUL, ADD, MUL, ADD, MUL}$$ Assume that every $\textsf{MUL}$ instruction is data-dependent on the $\textsf{ADD}$ instruction just before it and every $\textsf{ADD}$ instruction (except the first $\textsf{ADD}$) is data-dependent on the $\textsf{MUL}$ instruction just before it. The $\textit{speedup}$ defined as follows.
$$\textit{Speedup} = \dfrac{\text{Execution time without operand forwarding}}{\text{Execution time with operand forearding}}$$ The $\textit{Speedup} $ achieved in executing the given instruction sequence on the pipelined processor (rounded to $2$ decimal places) is _____________
in CO and Architecture recategorized by
by
2441 3623 5537
6.0k views

2 Comments

Cycles due to Operand forwarding=16

Cycles by not using operand forwarding=37

S=37/16=2.31…
1
1

I think the question setter didn’t want us to solve the question completely but to catch the pattern instead.

Without operand forwarding: 

Points to observe – 

  1. Every MUL will add $4$ cycles to the total number of cycle we have got before that instruction
  2. Every ADD EXCEPT the first one will add $3$ cycles to the total number of cycle we have got before that instruction

(ADD) $5$ cycles (this is first ADD)

(MUL) $+4$ cycles

(ADD) $+3$ cycles

(MUL) $+4$ cycles

(ADD) $+3$ cycles

….

So if there are total $n$ instructions (assuming $n$ to be even), the total number of cycles will be $5 + (n/2)*4 + (n/2 -1)*3 = 2 + 3.5n$

 

With operand forwarding: 

Points to observe – 

  1. Every MUL will add $2$ cycles to the total number of cycle we have got before that instruction
  2. Every ADD EXCEPT the first one will add $1$ cycle to the total number of cycle we have got before that instruction

(ADD) $5$ cycles (this is first ADD)

(MUL) $+2$ cycles

(ADD) $+1$ cycles

(MUL) $+2$ cycles

(ADD) $+1$ cycles

….

So if there are total $n$ instructions (assuming $n$ to be even), the total number of cycles will be $5 + (n/2)*2 + (n/2 -1)*1 = 4 + 1.5n$

 

$\text{Speed Up}$ = $\frac{2 + 3.5n}{4 + 1.5n}$

 

For $n = 4$, speed up = $16/10 = 1.60$ 

For $n = 8$, speed up = $30/16 = 1.88$

For $n = 100$, speed up = $352/154 = 2.28$  

For $n = 500$, speed up = $1752/754 = 2.32$  

 

For this question, we don't have to derive the formula but can directly add the cycles on the go.

5
5

Subscribe to GO Classes for GATE CSE 2022

3 Answers

19 votes
19 votes
 
Best answer

Correct Answer: 1.875


$\text{Speedup(def in question)}=\cfrac{\text{Time without Operand Forwarding}}{\text{Time with Operand Forwarding}}$
Without Operand Forwarding:
$\tiny
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline &1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22&23&24&25&26&27&28&29&30\\\hline \text{ADD}&\text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB}\\\hline
\text{MUL}&&\text{IF}&\text{ID}&&&\text{EX}&\text{EX}&\text{MEM}&\text{WB}\\\hline
\text{ADD}&&&\text{IF}&&&\text{ID}&&&&\text{EX}&\text{MEM}&\text{WB}\\\hline
\text{MUL}&&&&&&\text{IF}&&&&\text{ID}&&&\text{EX}&\text{EX}&\text{MEM}&\text{WB}\\\hline
\text{ADD}&&&&&&&&&&\text{IF}&&&\text{ID}&&&&\text{EX}&\text{MEM}&\text{WB}\\\hline \text{MUL}&&&&&&&&&&&&&\text{IF}&&&&\text{ID}&&&\text{EX}&\text{EX}&\text{MEM}&\text{WB}\\\hline \text{ADD}&&&&&&&&&&&&&&&&&\text{IF}&&&\text{ID}&&&&\text{EX}&\text{MEM}&\text{WB}\\\hline \text{MUL}&&&&&&&&&&&&&&&&&&&&\text{IF}&&&&\text{ID}&&&\text{EX}&\text{EX}&\text{MEM}&\text{WB}\\\hline \end{array}$

$\text{Time taken without Operand Forwarding}=30$


With Operand Forwarding:
$\tiny \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline &1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\\hline \text{ADD}&\text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB}\\\hline
\text{MUL}&&\text{IF}&\text{ID}&\text{EX}&\text{EX}&\text{MEM}&\text{WB}\\\hline
\text{ADD}&&&\text{IF}&\text{ID}&&\text{EX}&\text{MEM}&\text{WB}\\\hline
\text{MUL}&&&&\text{IF}&&\text{ID}&\text{EX}&\text{EX}&\text{MEM}&\text{WB}\\\hline
\text{ADD}&&&&&&\text{IF}&\text{ID}&&\text{EX}&\text{MEM}&\text{WB}\\\hline
\text{MUL}&&&&&&&\text{IF}&&\text{ID}&\text{EX}&\text{EX}&\text{MEM}&\text{WB}\\\hline
\text{ADD}&&&&&&&&&\text{IF}&\text{ID}&&\text{EX}&\text{MEM}&\text{WB}\\\hline \text{MUL}&&&&&&&&&&\text{IF}&&\text{ID}&\text{EX}&\text{EX}&\text{MEM}&\text{WB}\\\hline \end{array}$
$\text{Time taken with Operand Forwarding }= 16$


$\text{Speedup}=\cfrac{\text{Time without Operand Forwarding}}{\text{Time with Operand Forwarding}}=\cfrac{30}{16}=1.875$

edited by

1 comment

Sir , I have written 1.875 as ANS   that's 3 decimal.

but question mentions write up to  2 decimals, will it be considered in final , GO predictor  as well as ME have given marks for it , please clear this sir 

      

 

0
0
2 votes
2 votes

Speed Up = $\frac{23}{16} = 1.437 = 1.44$

by
35 104 555

6 Comments

dependency is between Add to Mul

No dependency between Mul to add.

 

i think it should be 20/16 = 1.25

please check

0
0
Answer should be 30/16 = 1.875 . Please check.
3
3
Using Operand forwarding: 16 cycle

Without Operand forwarding:

Case 1:

 From I2,

If EX is available on WB

Than 23 cycle got.

Speed up = 23/16

Case2:

From I2,

If EX ia available after WB

Than 30 cycle got.

Speed up = 30/16

 

...…

Which case prefer for without operand forwarding....
3
3
let answer key come
0
0
@Hradesh patel, in the first half of th clock cycle WB will write and in the second half of the clock cycle EX will read the operand. After that, it will take 2 EX to execute for MUL.
2
2
edited by

@Shaik Masthan Sir, I got the same answer as yours 23 for non operand forwarding...but as we have used split phase for WB , why in the answer key they haven't used split phase?

Does this means we should not consider split phase by default?

@jatinmittal199510 Sir, please help!

0
0
0 votes
0 votes

without operand forwarding  when instruction j depends on instruction i then 

1st check the status of  WA state, if  WA state status is 1 then ID state read the data from WA state in next cycle so that we got time without operand forwarding technique =23

With operand forward technique :-

value of the data stored  EX state buffer then we can read it form there for  instruction form  so we get 16 cycles

speed up = 27/16

=1.68

 

by
Answer:

Related questions