Now, let's discuss the relationship between the dependencies we have seen and
what we call hazards in our pipeline. A dependence is the property of
the program alone. We can just check whether two instructions have
a dependence between them without any regard to what the pipeline looks like.
In a particular pipeline, some dependencies will cause problems, potentially,
and some dependencies can not cause problems no matter what.
Let's look at an example of this. Let's say we have the classical five stage
pipeline with fetch, decode, ALU, memory, and write stages. And
let's consider two instructions like this that have an output dependence.
In this particular pipeline, I will show you that this output dependence is
never a problem. The ADD will move through this pipeline, until the right stage,
and that is when it will update R1. So let's look at the cycle while the ADD is
here, and the multiply is following behind it. At this point,
the multiplication has been fetched, has been decoded, and read R4 and R5.
If you read the correct value, because these are not affected by the ADD. And
now, it's just sitting in a MEM stage, because it's not a memory operation.
It has the value that it will deposit in R1. When the ADD leaves the pipeline in
the next cycle, the multiply will get here and have its write of R1.
So, as you can see, these instructions always write to R1 in the correct order.
So the fact that there is this output dependence doesn't mean that we have to
worry about it in this pipeline. This dependence will be naturally satisfied in
this pipeline because the writes by different instructions are always
occurring in program order in this pipeline.
Now let's consider a write after read dependence. Let's say that there is
a subtract instruction here that overwrites R4 that was read by the multiply.
At the point where the multiply reads R4, the subtract is being fetched.
So the multiply reads the value of R4, that was not affected by the subtract.
Later on when the multiply is done, the subtract will finally write to R4. And
that again means that the fact that there is a dependence between the read and
the write in the consecutive instructions. Is never a problem for
our pipeline because the read of R4 in the multiply
occurs many cycles before the subtract overrides that value.
So again, we have a dependence that cannot become a problem in our pipeline.
Now let's look at what happens when there is a true dependence in this pipeline.
In this case R4 here should be used by the next instruction.
The divide is reading R4 in a cycle where the subtract is here. Clearly,
at that time subtract didn't put its R4 value in the register R4.
It is actually just computing that value so
when the divide reads register four it's reading a stale value for
four that existed before the subtract. Several cycles later when the subtract
is writing to that register the divide has already computed its value and
the next cycle divide will write that bogus value into the register. So
pretty much it divide, read the wrong value R4, computed with that wrong value,
and then eventually deposits that wrong value into a register. So
clearly, this true dependence here is a problem in our pipeline.
If we just let things go and flow through the pipeline,
we will have the wrong result deposited into R10 by the divide. The situation
when our dependence can cause a problem in a pipeline is called a hazard. So
a hazard occurs when a dependence results in incorrect execution of one or
more instructions. Hazards are a property of both the program,
because you cannot have a hazard unless you have a dependence, but also
of the pipeline itself. How the dependence is interacting with the pipeline. So
for example we have seen that output and anti-dependencies in this particular
pipeline cannot become hazardous. But true dependencies can.
Now I will show you that not all true dependencies are hazards in this pipeline.
In this case, we have seen that a dependence between consecutive instructions
creates a hazard in this pipeline. Let's say that the write to R7 occurs
in this multiply instruction, and that we now have an XOR that uses R1 and
R7. Let's now see whether there is a dependence between the ADD and XOR.
Yes, there is. R1 produced by the ADD should be used by the XOR. And
there is also dependence between the multiply and the XOR.
But let's see if these dependencies are hazards in this particular pipeline.
When the XOR is in the decode stage, the divide is in the ALU stage,
the subtract is in the MEM stage, and the multiply is in the write stage, and
the ADD has left the pipeline. It was writing to R1 in the previous cycle.
So as you can see, the dependence between the ADD and
the XOR is not a hazard in this pipeline. Pretty much in this pipeline,
if there are three or more instructions between the producing and
the consuming instruction, then the consuming instruction reads the register
after the producing one has already written it. However, the dependents on
R7 between the multiply and XOR is potentially a problem in this pipeline,
because the XOR is reading R7 in the cycle during which multiply is writing it
to the register. So if this write completes near the end of the clock cycle and
this read is happening near the beginning of the clock cycle,
the XOR will not read the R7 produced by the multiply. In this pipeline we
can tell that a true dependence is not a hazard if there is three or
more instructions between the producing and consuming instruction. But
it is a hazard if there is fewer then three instructions between them.
In this case there are only two instructions in between and
that is why we still have a hazard.