what is the dependence vector

Hi


I'm reading the paper "A Data Locality Optimizing Algorithm", by
Michael E. Wolf and Monica S. Lam. In section 2, it describes the
dependence vector as,


>>"
a generalization of distance and direction vectors.


A dependence vector in an n-nested loop is denoted by a vector


d=(d1,d2,...,dn)


each component di is a possibly infinite range of integers, represented
by [di_min, di_max], where


di_min b Z b* {-b}, di_max b Z b* {b} and di_min b $ di_max


<<"
Here, a n-nested loop corresponds to a finite convex polyhedron of
iteration space Zn (n power).


a) What does di mean? Does it mean the dependence of loop i? I think the
dependence should refer to two statements.


>>"
A single dependence vector therefore represents a set of distance
vectors, called its distance vector set:


N5(d)={(e1,...,en) | ei b Z and di_min b $ ei b $ di_max}
"
<<"


b) Here, what does 'N5(d)' mean? What does 'N5' mean?


>>"
The dependence vector d is also a distance vector if each of its
components is a degenerate range consisting of a singleton value, that
is, di_min=di_max.
<<"


c) What does this sentence above mean?


Too more questions about dependence representations.


Cheers
Eric Fisher

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