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 <joefoxreal@gmail.com>
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


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


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.

Eric Fisher

Post a followup to this message

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