1
$\begingroup$

Given below is a question from $\text{GATE } 2015 \text{ CS}$ paper,

Consider the sequence of machine instruction given below: \begin{array}{ll} \text{MUL} & \text{R5, R0, R1} \\ \text{DIV} & \text{R6, R2, R3} \\ \text{ADD} & \text{R7, R5, R6} \\ \text{SUB} & \text{R8, R7, R4} \\ \end{array}

In the above sequence, $R0$ to $R8$ are general purpose registers. In the instructions shown, the first register shows the result of the operation performed on the second and the third registers. This sequence of instructions is to be executed in a pipelined instruction processor with the following $4$ stages: $(1)$ Instruction Fetch and Decode $(IF)$, $(2)$ Operand Fetch $(OF)$, $(3)$ Perform Operation $(PO)$ and $(4)$ Write back the result $(WB)$. The $IF, OF$ and $WB$ stages take $1$ clock cycle each for any instruction. The $PO$ stage takes $1$ clock cycle for $ADD$ and $SUB$ instruction, $3$ clock cycles for $MUL$ instruction and $5$ clock cycles for $DIV$ instruction. The pipelined processor uses operand forwarding from the $PO$ stage to the $OF$ stage. The number of clock cycles taken for the execution of the above sequence of instruction is _________.

[Discussions on the above question can be found here.

I tried out myself at first and the answer came just the same as the first alternative of the accepted answer in link given above.

\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{I1}&\text{IF}&\text{OF}&\text{PO}&\text{PO}&\text{PO}&\text{WB}\\ \textbf{I2}&&\text{IF}&\text{OF}&\color{red}{-}&\color{red}{-}&\text{PO}&\text{PO}&\text{PO}&\text{PO}&\color{green}{\boxed{\text{PO}}}&\text{WB}\\ \textbf{I3}&&&\text{IF}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{green}{\boxed{\text{OF}}}&\color{blue}{\boxed{\text{PO}}}&\text{WB}\\ \textbf{I4}&&&&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\text{IF}&\color{red}{-} &\color{blue}{\boxed{\text{OF}}}&\text{PO}&\text{WB}\\ \hline\end{array}

What I did is that, when the question says that there is operand forwarding from the $PO$ stage to the $OF$ stage I assume that the $ALU$ calculates the results and the same results are latched by the latch following ALU in the last cycle of the $PO$ and from this latch the result is available to the input of the $OF$ stage at the beginning of the next cycle and in this next cycle the $OF$ decides to chose among the register file or from the inputs available in the latch. This gives me $15$ cycles.

But after the official answers keys were released the answer accepted was $13$ and hence the author of accepted answer here made a modification and the modification was as follows:

\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}}\\ \hline \textbf{I1}&\text{IF}&\text{OF}&\text{PO}&\text{PO}&\text{PO}&\text{WB}\\ \textbf{I2}&&\text{IF}&\text{OF}&\color{red}{-}&\color{red}{-}&\text{PO}&\text{PO}&\text{PO}&\text{PO}&\color{green}{\boxed{\text{PO}}}&\text{WB}\\ \textbf{I3}&&&\text{IF}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{green}{\boxed{\text{OF}}}&\color{blue}{\boxed{\text{PO}}}&\text{WB}\\ \textbf{I4}&&&&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\color{red}{-}&\text{IF}&\color{blue}{\boxed{\text{OF}}} &\text{PO}&\text{WB}\\ \hline\end{array}

Here they are assuming split phase. The $ALU$ executes and finds outs the results and writes it to the latch following the $OF$ phase in half of its last cycle and then the $OF$ performs it operation the last half of the cycle. (this concept is not know to me.)

Many of the comments in the site here say that the question setter meant to do something like the figure $(1)$ but actually ended up accepting the way given in figure $(2)$ :

  1. enter image description here $\quad\quad\quad$ 2. enter image description here

There was an exactly same question which was not clearly explained however, but there was an answer here. Where the author of the answer says that forwarding only makes sense from "perform operation" to "operand fetch". But I have read Computer Organization and Design: The Hardware Software Interface (3rd Ed.) , by Patterson et. al where they show how the operands are forwarded from various stages following the $EX$ phase to the inputs of the $ALU$ using $MUX$. $\text{(pgs 405,408,409)}$. The convention used in the Patterson book is clearly explained.

enter image description here The different dependencies being shown

enter image description here The dependencies resolved by operand forwarding

enter image description here The hardware showing how the operand forwarding is actually done

What is creating problem here is that the question says $PO$ to $OF$, which makes me naturally feel that we give the output of the $ALU$ to the inputs of the $OF$ (literal meaning guessed from the question and from how the operand forwarding is dealt with in the Patterson text).

Now in the solution to the question they are using some sort of split phasing which is used in Patterson, only for the register read phase and the register write back phase, to prevent structural hazard. How is the operand forwarding from the $PO$ phase to the $OF$ phase being executed? As the author here says that the data from the $ALU$ is written to the latch following the ALU and also to the latch following the $OF$ stage in a single cycle.. The effect being similar to the result of $ALU$ being forwarded to the inputs of the $ALU$. (The case explained in Patterson, though the hardware implementation is actually different.)

From the convention used in Patterson, what I felt after reading the question is, the output of the $ALU$ is being sent to the input of $OF$ stage and in the next clock cycle there is simultaneous $WB$ of the value to the register file and at the same time we can read the operand (if required) from the latch following the $ALU$ in the $OF$ stage. And this made me get $15$ cycles.(As already stated previously). Now as per the author here, Operator forwarding means that in the same cycle, the data can be sent both to the register where it should be stored, AND to the operand that needs it. I am wrong (and it contradicts as what I have read from Patterson text).

I do not quite get it as to when to apply what and it is getting quite confusing. Could you please provide the source from where develop my concepts or at least those which shall help me remove all my confusions easily. There are many probably many conventions and hardware implementations in practice this is what I feel.

In a comment to this question here the author asks what if in a question it is not specified the stages involved in operand forwarding and what is the default to consider, the author here replies that the question is highly imprecise in that case, but check this question here and if you follow the assumption in Patterson text then it comes out to be the answer accepted officially.

I am utterly confused. Please help me out!!!

$\endgroup$
1
  • $\begingroup$ If my question is not clear then please do point it out, so that I can improve it. Please do help me out with the concept. $\endgroup$ – Abhishek Ghosh Nov 20 '20 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.