Loop dependence analysis

Loop dependence analysis

In compiler theory, loop dependence analysis is the task of determining whether statements within a loop body form a dependence, almost always with respect to array access and modification. For a normalized loop:

for i1 from l1 to u1 do for i2 from l2 to u2 do ... for in from ln to un do "body" od od od

where "body" may contain:

S1 a [f1(i1, ..., in), ..., fm(i1, ..., in)] := ... ... S2 ... := a [h1(i1, ..., in), ..., hm(i1, ..., in)]

the scope of the problem is to find all possible dependencies between "S1" and "S2". To be conservative, any dependence which cannot be proven false must be assumed to be true.

In the course of (dis)proving such dependencies, a statement "S" may be decomposed according to which iteration it comes from. For instance, "S" [1,3,5] refers to the iteration where i1 = 1, i2 = 3 and i3 = 5. Of course, references to abstract iterations, such as "S" ["d1"+1,"d2","d3"] , are both permitted and common.

Independence is shown by demonstrating that no two instances of "S1" and "S2" access or modify the same spot in array a. When a possible dependence is found, loop dependence analysis usually makes every attempt to characterize the relationship between dependent instances, as some optimizations may still be possible. It may also be possible to transform the loop to remove the dependence.

Iteration vectors

A specific iteration through a normalized loop is referenced through an iteration vector, which encodes the state of each iteration variable.

For a loop, an iteration vector is a member of the Cartesian product of the bounds for the loop variables. In the nomalized form given previously, this space is defined to be [l1..u1] × [l2..u2] × ... × [ln..un] . As noted, specific (or general) instances of statements may be parameterized by these iteration vectors, and they are also the domain of the array subscript functions found in the body of the loop. Of particular relevance, these vectors form a lexicographic order which corresponds with the chronological execution order.

Dependence

For the normalized form above, a dependence between "S1" and "S2" exists if and only if:

* a and b are two iteration vectors.
* f(a) = h(b).
* a < b
* Either a or b is a write/store

where vector function notation has been used. Without vector notation, the second constraint becomes: f1(a1,a2, ..., an) = h1(b1,b2, ..., bn) and ... and fm(a1,a2, ..., an) = hm(b1,b2, ..., bn).

If a is a write and b is a read, then this is a flow dependence. If a is a read and b is a write, then this is an antidependence.

If a is a write and b is a write, then this is an output dependence

Devices and techniques

Several established devices and techniques exist for tackling the loop dependence problem. For characterizing the nature of a dependence, there are distance vectors, direction vectors and dependence vectors. For determining whether a dependence exists, the GCD test and the Banerjee test are the most general tests in common use, while a variety of techniques exist for simpler cases.

Further reading

*cite book | author=Kennedy, Ken; & Allen, Randy. | title=Optimizing Compilers for Modern Architectures: A Dependence-based Approach | publisher=Morgan Kaufmann | year=2001 | id=ISBN 1-55860-286-0
*

See also

* Dependence analysis
* Loop transformation
* Loop splitting
* Loop fusion
* Loop interchange
* Loop skewing
* automatic parallelization


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Dependence analysis — bzw. die Abhängigkeitsanalyse stellt im Compilerbau die Abhängigkeit zwischen Anweisungen fest. Daraus wird ermittelt wann es sicher ist die Ausführungsreihenfolge von Programmen zu verändern bzw. zu parallelisieren. Allgemein hängt eine… …   Deutsch Wikipedia

  • Dependence analysis — In compiler theory, dependence analysis produces execution order constraints between statements/instructions. Broadly speaking, a statement S2 depends on S1 if S1 must be executed before S2. Broadly, there are two classes of dependencies control… …   Wikipedia

  • Loop optimization — In compiler theory, loop optimization plays an important role in improving cache performance, making effective use of parallel processing capabilities, and reducing overheads associated with executing loops. Most execution time of a scientific… …   Wikipedia

  • Loop interchange — In compiler theory, loop interchange is the process of exchanging the order of two iteration variables. For example, in the code fragment: for i from 0 to 10 for j from 0 to 20 a [i,j] = i + jloop interchange would result in: for j from 0 to 20… …   Wikipedia

  • Normalized loop — In computer science, a normalized loop (sometimes called well behaved loop), is a loop which the loop variable starts at 0 (or any constant) and get incremented by one at every iteration until the exit condition is met. Normalized loops are very… …   Wikipedia

  • Abhängigkeitsanalyse — Dependence analysis bzw. die Abhängigkeitsanalyse stellt im Compilerbau die Abhängigkeit zwischen Anweisungen fest. Daraus wird ermittelt wann es sicher ist die Ausführungsreihenfolge von Programmen zu verändern bzw. zu parallelisieren. Allgemein …   Deutsch Wikipedia

  • Ausgabeabhängigkeit — Dependence analysis bzw. die Abhängigkeitsanalyse stellt im Compilerbau die Abhängigkeit zwischen Anweisungen fest. Daraus wird ermittelt wann es sicher ist die Ausführungsreihenfolge von Programmen zu verändern bzw. zu parallelisieren. Allgemein …   Deutsch Wikipedia

  • Echte Datenabhängigkeit — Dependence analysis bzw. die Abhängigkeitsanalyse stellt im Compilerbau die Abhängigkeit zwischen Anweisungen fest. Daraus wird ermittelt wann es sicher ist die Ausführungsreihenfolge von Programmen zu verändern bzw. zu parallelisieren. Allgemein …   Deutsch Wikipedia

  • Gegenabhängigkeit — Dependence analysis bzw. die Abhängigkeitsanalyse stellt im Compilerbau die Abhängigkeit zwischen Anweisungen fest. Daraus wird ermittelt wann es sicher ist die Ausführungsreihenfolge von Programmen zu verändern bzw. zu parallelisieren. Allgemein …   Deutsch Wikipedia

  • Kontrollflussabhängigkeit — Dependence analysis bzw. die Abhängigkeitsanalyse stellt im Compilerbau die Abhängigkeit zwischen Anweisungen fest. Daraus wird ermittelt wann es sicher ist die Ausführungsreihenfolge von Programmen zu verändern bzw. zu parallelisieren. Allgemein …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”