GATE Overflow Test Series | Computer Organization and Architecture | Test 1 | Question: 18

Question

Consider a $5$-stage pipeline - IF (Instruction Fetch), ID (Instruction Decode and register read), EX (Execute), MEM (Memory) and WB (Write Back). All register reads take place in the second phase of a clock cycle and all register writes occur in the first phase. Consider the execution of the following instruction sequence:

• $I_1: R_1 \leftarrow R_2 + R_3$
• $I_2: R_3 \leftarrow R_1 - R_2$
• $I_3: M[R_1+1000] \leftarrow R_1$
• $I_4: R_2 \leftarrow R_3 * R_1$

If the number of RAW (Read after write) hazards is denoted by $A,$ WAR (Write after read) hazards by $B$ and WAW (Write after write) hazards by $C,$ then $A+B+C = $_____

Comments

fo all of those who are like me and have wrong concept about hazard and dependency

dependency is a property of program whereas hazard means dependency result in incorrect execution(when a dependence can cause a problem in a pipeline is called a hazard). 

src:https://www.youtube.com/watch?v=F0-hW8nc6es&t=289s

Answer 1

$$\begin{array}{|c|c c c c c c c c|}
        \hline
        &1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
        \hline
        I_1&\text{F}&\text{D}  &\text{E} &\text{M} &\textbf{W} & & &   \\
        I_2&&\text{F}  &\boxed{\text{D}} &\text{E} &\text{M} &\textbf{W} & &    \\
        I_3&& &\text{F} &\boxed{\text{D}} &\text{E}  &\text{M}  &\text{W} & \\
        I_4&& & & \text{F}   &\boxed{\text{D}} &\text{E}  &\text{M} &\text{W} \\
        \hline
    \end{array}$$
RAW (Read After Write) Dependencies are: $I_1\rightarrow I_2,I_1\rightarrow I_3,I_1 \rightarrow I_4,I_2 \rightarrow I_4.$

Of these $4$ dependencies, only $I_1 \rightarrow I_4$ is not a hazard, as the order of R/W here follows the same as in a non-pipelined sequential execution. ($W$ of $I_1$ is happening in first phase of the cycle and $R$ of $I_4$ is happening in the second phase). Thus, we have $3$ RAW hazards here. So, $A = 3.$
    
The given pipeline is the simplistic one -- where each stage is used only for one cycle -- and in such a pipeline with inorder execution we can never have WAR or WAW hazards. So, $B = C = 0.$
    
Thus, $A +B+C = 3.$

Comments

Since WAR and WAW dependencies did not stall the pipeline, they are not hazards and hence we didn’t consider them. WAR and WAW are a problem only in concurrent execution where 2 or more instructions can be executed at the same time. Eg: superscalar processors

In above problem, it is not possible for $I_{i+1}$ to write to a register before $I_i$ writes or reads the same register because we execute instructions sequentially. Hence, we only have to look out for RAW hazards

https://en.wikipedia.org/wiki/Hazard_(computer_architecture)#Write_after_read_(WAR)

---

If I2: M[R1 + 100] ← R4 then I2 is truly dependent on I1, because I2 is reading R1 for address calculation.

Is it correct?

---

@Pascua but question isn’t asking about stalls but number of hazards, so why aren’t we considering WAR and WAW hazards here?