GATE IT 2006 | Question: 79

Question

A pipelined processor uses a 4-stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The sequence of instructions corresponding to the statement $X = (S - R * (P + Q))/T$ is given below. The values of variables $P, Q, R, S$ and $T$ are available in the registers $R0, R1, R2, R3$ and $R4$ respectively, before the execution of the instruction sequence.

$$\begin{array}{lll} 
\text{ADD} & R5, R0, R1 & \text{; } R5 \leftarrow R0 + R1 \\
\text{MUL} & R6, R2, R5 & \text{; } R6 \leftarrow R2 \times R5 \\
\text{SUB} & R5, R3, R6 & \text{; } R5 \leftarrow R3 - R6 \\ 
\text{DIV} & R6, R5, R4 & \text{; } R6 \leftarrow R5 / R4 \\
\text{STORE} & R6, X & \text{; } X \leftarrow R6
\end{array}$$

The IF, ID and WB stages take 1 clock cycle each. The EX stage takes $1$ clock cycle each for the ADD, SUB and STORE operations, and $3$ clock cycles each for MUL and DIV operations. Operand forwarding from the EX stage to the ID stage is used. The number of clock cycles required to complete the sequence of instructions is

• A. $10$
• B. $12$
• C. $14$
• D. $16$

Comments

why split-phase implementation is required?

standard forwarding is EX->EX, MEM->EX but EX->ID is special because when previous instruction is in EX then at the same time next instruction is already in ID, so to make this EX->ID possible we have to do the split-phase implementation

in split-phase design, a stage is broken into sub-phases (e.g early and late), so EX finishes its computation in 1st half so that ID can read that result in 2nd half of the same cycle, this makes EX->ID possible

without split-phase EX produces its result only in the end of cycle and ID already read the wrong value at beginning of cycle, so EX->ID is not possible

EX->EX forwarding works without split-phase because when one instruction is in EX (producing the result), the dependent instruction is going to be in EX in the next cycle (consuming the result) → forwarding is naturally possible.

---

12
for STORE R6 is not dependent 

---

Important Note : Read the Important comment of Sachin Sir before moving to my explanation

1) https://gateoverflow.in/1391/gate-cse-2005-question-68?show=95287#c95287

2)https://gateoverflow.in/8218/gate-cse-2015-set-2-question-44?show=91622#c91622

Reference : Patterson Davie 

Simplification of sachin Sir comment :

"Write happens in the 1st half of the cycle, Read happens in the 2nd half."

==>  This is true actually . In Patterson & Hennessy explicitly note that to avoid a structural/data hazard when the Write-Back (WB) stage writes to a register while the Instruction Decode (ID) stage reads from the same register in the same clock cycle, the register file is designed to write during the first half of the clock cycle and read during the second half of the clock cycle.

 "If WB and ID overlap, the ID stage automatically reads the updated register value."

Assume WB-ID happen cycle 5

$\begin{aligned} I_1&: \text{ADD } R_1, R_2, R_3 \quad \text{(Writes to } R_1 \text{ in WB stage during Cycle 5)} \\ I_3&: \text{SUB } R_4, R_1, R_5 \quad \text{(Reads from } R_1 \text{ in ID stage during Cycle 5)} \end{aligned}$

In Cycle 5, $I_1$ is in WB and $I_3$ is in ID. Because $I_1$ writes the new value of $R_1$ during the first half of Cycle 5, $I_3$ reads the newly written $R_1$ value . No stall cycles or extra hardware intervention are required.

"And this has nothing to do with operand forwarding"

==> split phase : An internal timing property of the Register File hardware. It uses clock phases/edges to handle dependencies between WB stage and ID stage 

==> Operand forwarding : In figure we can see that uses external multiplexers and bypass paths around the register file to route ALU or Memory outputs directly to the ALU inputs in the EX stage .

"My clock cycle time is big enough to do read/write in one half..."

==> In modern processors, the Register File  is small  and has an access latency  significantly smaller than the latency of the Main ALU  or Data Memory...This ensures both a write operation and a read operation can comfortably fit sequentially into a single clock cycle divided into two halves.

Answer 1

$$\small \displaystyle \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline &C_1&C_2&C_3&C_4&C_5&C_6&C_7&C_8&C_9&C_{10}&C_{11}&C_{12}\\\hline
\textbf{ADD}&\text{IF}&\text{ID}&{\color{green}{\underset{\boxed{1}}{\text{EX}}}}&\text{WB}&&&&&&&&\\\hline
\textbf{MUL}&&\text{IF}&{\color{green}{\underset{\boxed{1}}{\text{ID}}}}&\text{EX}&\text{EX}&{\color{green}{\underset{\boxed{1}}{\text{EX}}}}&\text{WB}&&&&&\\\hline
\textbf{SUB}&&&\text{IF}&\color{red}{-}&\color{red}{-}&{\color{green}{\underset{\boxed{1}}{\text{ID}}}}&{\color{green}{\underset{\boxed{1}}{\text{EX}}}}&\text{WB}&&&&\\\hline
\textbf{DIV}&&&&&&\text{IF}&{\color{green}{\underset{\boxed{1}}{\text{ID}}}}&\text{EX}&\text{EX}&{\color{green}{\underset{\boxed{1}}{\text{EX}}}}&\text{WB}&\\\hline
\textbf{STORE}&&&&&& &\text{IF}&\color{red}{-}&\color{red}{-}&{\color{green}{\underset{\boxed{1}}{\text{ID}}}}&\text{EX}&\text{WB}\\\hline \end{array} $$

$\color{red}{-}\quad\text{Stalls}$
$\color{green}{\boxed{1}} \quad \text{Operand forwarding from EX-ID using split phase}$

So, answer is 12.

Correct Answer: $B$

For more Clarity see this discussion https://gateoverflow.in/3623/gate-it-2006-question-79?show=138313#c138313

Reference

Comments

Ajinkya9 https://web.archive.org/web/20210506092429/http://web.cs.iastate.edu/~prabhu/Tutorial/PIPELINE/forward.html

Use archived links.

---

Is split phase by default to consider ?

 

Got it. Please ignore this comment.

 

we always do split phase if 1 instruction is writing/computing and other instruction is reading but we will never do split phase if one instruction is computing and other instruction is also computing because ALU for 2 instructions cannot be done in a single clock-cycle.

---

the DIV and STORE instructions have ALU to memory dependency. afaik operand forwarding cannot prevent stalls in such case so 14  should be the correct answer imo. where am I wrong?

Answer 2

answer = option D = $16$ cycles are required

Comments

when to use EX to EX and EX to ED
someone reply fast. Just few hours are left for Gate 19

---

http://web.cs.iastate.edu/~prabhu/Tutorial/PIPELINE/forward.html

For more details

 

---

According to this explanation there will be 18 cycles because you are not considering the cycles due to data hazard caused by last two instructions because operand forwarding cann't remove load and store dependencies.

Answer 3

Hi  , I have a very silly doubt here. 

Can we do the IF stage as I did ? because in other answers I could see , IF is also done after EX

amarVashishth 

srestha goel 

I have the confusion here that , IF stage of I4 instruction , can I start it in clock 4 ? because anyhow , ID should be started at  clock 7. or does IF also needs to start at clock 6 ?

Please clarify this doubt.

(N.B : please bear with my poor , illegible hand-writing )

Comments

Answer given to this question is 14

Answer 4

Hazards in computer architecture are events that cause delays in the pipeline and prevent an instruction from being executed in the designated clock cycle.

If there is no any types of hazard then :-

Number of clock cycles = K+n-1 , where K :  No. of stages, n: No. of instructions

                                       =4+5-1

                                        =8

There are 3 types of hazards in pipeline system : 1.Structural 2.Data 3.Control

Extra cycle due to hazards :-

1.Structural:  MUL and  DIV operations takes 3-1 = 2  extra cycles each i.e 2*2=4.

2.Data :  There is no extra cycles due to data hazard because of operand-forwarding(Given in question)

3.Control : Since, There is no branch instruction therefore no extra cycles due to control hazard

NOW,

The number of clock cycles required to complete the sequence of instructions is = 8+4 = 12.

Comments

but there is data hazard between last two instruction because operand forwarding can't solve the problem for load and store instructions

 

Answer 5

12 clocks

Answer 6

https://youtu.be/IacGo99gEcw?si=vPzQZ92UL7XckzZM