edited by
17,342 views
54 votes
54 votes

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

$$\begin{array}{|l|l|} \hline \text{I1:} & \text{sub $r 2,r 3,r 4$} & \text{/*}\quad  r2 \leftarrow r3 - r4 \quad\text{*/} \\\hline \text{I2:} & \text{sub $r 4,r 2,r 3$} & \text{/*}\quad r4 \leftarrow r2 - r3 \quad\text{*/} \\\hline \text{I3:} &  \text{sw $r2,100(r1)$} & \text{/*}\quad\text{$M[r1 + 100]$} \leftarrow \text{r2}  \quad\text{*/}\\\hline \text{I4:} &  \text{sub $r 3,r 4,r 2$} & \text{/*}\quad r3 \leftarrow  r4 - r2 \quad\text{*/} \\\hline\end{array}$$

  1. Show all data dependencies between the four instructions.
  2. Identify the data hazards.
  3. Can all hazards be avoided by forwarding in this case.
edited by

2 Answers

Best answer
54 votes
54 votes

RAW dependencies:

  1. $I_1 \leftarrow I_2$
  2. $I_1 \leftarrow I_3$
  3. $I_1 \leftarrow I_4$
  4. $I_2 \leftarrow I_4$

WAR dependencies:

  1. $I_2 \leftarrow I_1$
  2. $I_4 \leftarrow I_1$
  3. $I_4 \leftarrow I_2$

Consider a normal pipeline execution:

$$\begin{array}{|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}\\\hline
\bf{I_1}& \text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\bf{I_2}&&\text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\bf{I_3}&&&\text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\bf{I_4}&&&&\text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\end{array}$$

So, there are RAW hazards for $I_2$ and $I_3$ with $I_1$ and for $I_4$ with $I_2.$ (Not all dependencies cause a hazard. Only if a dependency causes a stall in the given pipeline structure, we get a hazard) These hazards cause the following stalls in the pipeline:

$$\begin{array}{|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}}\\\hline
\bf{I_1}& \text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\bf{I_2}&&\text{IF}&-&-&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\bf{I_3}&&&-&-&\text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\bf{I_4}&&&&-&-&\text{IF}&-&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\end{array}$$

Now, with operand forwarding from $\text{EX} - \text{EX}$ stage we can do as follows: 

$$\begin{array}{|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}\\\hline
\bf{I_1}& \text{IF}&\text{ID}&\underset{1}{\boxed{\text{EX}}}&\text{MEM}&\text{WB} \\ \hline
\bf{I_2}&&\text{IF}&\text{ID}&\underset{1}{\boxed{\text{EX}}}&\text{MEM}&\text{WB} \\ \hline
\bf{I_3}&&&\text{IF}&\text{ID}&\underset{3}{\boxed{\underset{1}{\boxed{\text{EX}}}}}&\text{MEM}&\text{WB} \\ \hline
\bf{I_4}&&&&\text{IF}&\text{ID}&\underset{3}{\boxed{\text{EX}}}&\text{MEM}&\text{WB} \\ \hline
\end{array}$$

Thus all hazards are eliminated. 

Ref: http://cseweb.ucsd.edu/classes/wi05/cse240a/pipe2.pdf

edited by
60 votes
60 votes

4 RAW

3 WAR 

With operand forwarding:

Without it:
(both tables represent the same pipeline)


 

Related questions

1 votes
1 votes
1 answer
4
Kathleen asked Sep 14, 2014
2,387 views
A low memory can be connected to 8085 by using$INTER$$\overline{RESET\text{ }IN}$$HOLD$$READY$