Re: Definition of Data Dependence Distance

frazier@CS.UCLA.EDU (Greg Frazier)
6 Dec 91 20:15:37 GMT

          From comp.compilers

Related articles
Definition of Data Dependence Distance pugh@cs.umd.edu (1991-12-06)
Re: Definition of Data Dependence Distance maydan@Neon.Stanford.EDU (1991-12-06)
Re: Definition of Data Dependence Distance frazier@CS.UCLA.EDU (1991-12-06)
Re: Definition of Data Dependence Distance grover@brahmand.Eng.Sun.COM (1991-12-10)
| List of all articles for this month |

Newsgroups: comp.compilers
From: frazier@CS.UCLA.EDU (Greg Frazier)
Keywords: parallel
Organization: UCLA, Computer Science Department
References: 91-12-041
Date: 6 Dec 91 20:15:37 GMT

[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


--


Post a followup to this message

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