Re: Definition of Data Dependence Distance

[From comp.parallel. -John]


pugh@cs.umd.edu (Bill Pugh) writes:
>HOWEVER, coming to the defense of the first definition is the following example:


>for i := 0 to 10
> for j := i to 10 by 3
> a[i,j] := a[i-1,j+2] + b[i,j]


>Using the first definition gives a dependence distance of (1,-2). However,
>it isn't clear if the dependence distance is even defined if we use the
>second definition.


Well, since what you are interested in is *dependence*, and since each
iteration of the 'j' loop does not depend on previous 'j' iterations,
then there shouldn't be a dependence distance for the 'j' loop, i.e.,
the second definition wins again. However, there is a "forward"
dependence, where if you try to parallelize the 'j' loop, you have to
make sure the a[x,y] value is read before it is written by the y+3'rd
iteration of the 'j' loop. Neither of your dependence definitions
really works in this case, but I think a modification of the second
definition is what one would want.
--
Greg Frazier frazier@CS.UCLA.EDU !{ucbvax,rutgers}!ucla-cs!frazier


--

Return to the comp.compilers page.
Search the comp.compilers archives again.