Tue, 28 Apr 2009, 22:05

A student writes:

	
	
	Dr. Patt,

	In class you mentioned data dependencies and control dependencies. You
	said there are several kinds of data dependencies, and that a flow
	dependency is one of these. I don't think you explained what the other
	kinds are. But I might have missed that.



No, I generally discuss them all in the context of data flow, and we have not
gotten there yet.  Since you asked, let me do it here.

First control dependencies:  Suppose you have the code:

		...
		BRn A
		ADD R1,R2,R3
	   A    LD R4,B
		...

The ADD instruction is control dependent on the BRn instruction.  That is,
whether or not the ADD executes is dependent on whether or not the conditional 
branch is taken.

Note that the LD instruction is not dependent on BRn, since the LD instruction
gets executed regardless.  We say the LD is control-independent of the BRn
instruction.

Next data dependencies.  There are three.  Some people refer to them as 
hazards, a term I do not like, because if you design properly, there is never
a problem.  Since so many people use the term hazards in this ill-conceived
way (in my view), I will give you both sets of terminology.

a. Flow dependency (also called Read-after-Write (RAW) Hazard).  Best shown
by an example:  X + YZ.  That is, the sum of X and the result of multiplying
Y and Z.  One can not do the Add until AFTER one does the multiply.  The
result of the multiply is needed as a source of the add.  The machine language
code would cause the computer to write the result of the multiply into a 
register BEFORE that register was read to get a source for the add.  So, the
write has to be done before the read.  Ergo RAW.  It is a "flow dependency"
in the sense that the result of the multiply flows into the source of the add.
This is part of the code and must be obeyed.   ...although it is certainly
true that one could rewrite the code.

b. Write dependency (also called Write-after-Write WAW Hazard).  

This is most notable in code involving I/O devices or I/O control blocks.
Simple example: code that writes to R0 which is then written to the screen.
Suppose the program wishes to write: "You have mail" by writing the successive
characters to R0 and after each, calling the TRAP handler to write the 
next character to the screen.  You would be unhappy with: "Yuo emahv ila."
There is an output dependency between successive writes to R0.  This is never
a problem in out-of-order machines because one would assign different tags for
different instances of R0.  

c. Finally, anti-dependency (also called WAR Hazard).  This is the case 
where a dependency does not really exist, and is never a problem with o-o-o
implementations because different tags are assigned to different instances
of a register.  Again, an example is illuminating.

		...
		ADD R1,R3,R2
		ADD R2,R4,R5
		...

The anti-dependency says that you have to read R2 for the first add BEFORE
you write R2 in the second add.  You might say, obviously!  If I wrote R2
before reading R2, I would be reading the wrong value for R2.  As I said,
tags guarantee that.

But suppose I did not have tags, and somehow my implementation stalled the
first add (maybe R3 was the result of a LD that took a cache miss) and I did
not read R2 until after I read R3 (after the LD completed), and suppose for
some reason I let the second add complete and write to R2 before the LD 
completed.  Then I would be reading the value in R2 produced by the second
add, when I should have been reading the value in R2 that was there before 
the second add completed.  Ergo, antidependency.  Easy to make sure this
never happens by sourcing the registers in the front end in-order part of
every pipeline.

OK?  Bottom line is that the tagging gets rid of the problem for 
antidependencies and write dependencies, and provides the mechanism to 
ensure that flow dependencies are dealt with properly.

Hope this helps.

Good luck on the exam tomorrow.

Yale Patt

	
	
	"Data dependency (Flow dependency)" is listed as a buzzword. But these
	are not the same. As I said above, a flow dependency is a type of data
	dependency. Right?

	The buzzwords from Fall 2005 and Spring 2007 say that a data
	dependency is "one of the three data dependencies: flow, anti, write".
	However, write dependencies are not explained anywhere in the
	buzzwords. Can you please explain that?

	An in-order pipelined machine has to handle control dependencies and
	flow dependencies. Are write dependencies and anti dependencies a
	problem is such machines?

	Does an out-of-order machine have to handle all of the dependencies
	mentioned above?

	Thanks,
	<<name withheld to protect the student inundated with dependencies>>