# what is the dependence vector

## Eric Fisher <joefoxreal@gmail.com>Thu, 4 Jun 2009 06:21:41 +0000 (UTC)

From comp.compilers

Related articles
what is the dependence vector joefoxreal@gmail.com (Eric Fisher) (2009-06-04)
Re: what is the dependence vector xueyunzhi@gmail.com (yunzhi) (2009-06-05)
Re: what is the dependence vector joefoxreal@gmail.com (Eric Fisher) (2009-06-08)
| List of all articles for this month |

 From: Eric Fisher Newsgroups: comp.compilers Date: Thu, 4 Jun 2009 06:21:41 +0000 (UTC) Organization: A poorly-installed InterNetNews site Posted-Date: 04 Jun 2009 15:47:35 EDT

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

Post a followup to this message