GATE CSE 2021 Set 2 | Question: 53

Question

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 _____________

Comments

IIUC, the reason why split-phase technique hasn’t been considered in the official answer key is particularly because of the following sentence in the question:-

Assume that the \(ID\) stage merely decodes the instruction and the register read is performed in the \(EX\) stage.

We all know that split-phase might not be possible for \(EX-EX\) when considering operand forwarding (the actual execution of the \(EX\) stage might not finish within a phase (three phases) of a (two) clock cycle(s) for the \(ADD\) (\(MUL\)) instruction). A similar argument can be used to justify why split-phase might not be possible for \(WB-EX\) when we do not take operand forwarding into consideration (because for split-phase to be possible for \(WB-EX\), the actual execution of the \(EX\) stage of \(ADD\) must finish within a phase of the clock cycle, and the actual execution of the \(EX\) stage of \(MUL\) must finish within three phases spread over two clock cycles, which might not be possible, and which shouldn’t be assumed, since nothing like that is mentioned in the question).

---

@Ray Tomlinson Don't wry I will make sure no one will upvote it except u, especially for putting up this comment as a bill board.

---

My Observation -> when they mention it is RISC pipeline then consider split stage  ,otherwise not consider 

Important Comment Of  @Abhrajyoti00 

Answer 1

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$

Comments

BUT split phase is done here in without operand forwarding, if split phase were not done, the ID phase(operand fetch) would be done on the next cycle of WB, and execution will start after 2 cycles of previous instructions EX

---

It is mentioned in question that operand fetch is done EX stage

---

If 2nd stage of the pipeline was Operand Fetch(OF), instead of Instruction decode ( which means Instruction Fetch & Decode done in single stage - the 1st stage ). Then the flow chart of without operand forwarding would differ right, by taking OF stage of each instruction after WB stage of previous instruction right.... I m just asking to reconfirm with what I have previously studied.

Answer 2

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

Comments

let answer key come

---

@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.

---

@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!

Answer 3

Ans is Option D

 

Answer 4

without operand forwarding  when instruction j depends on instruction i then 

1^st 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