Loop dependence analysis

In computer science, loop dependence analysis is a process which can be used to find dependencies within iterations of a loop with the goal of determining different relationships between statements. These dependent relationships are tied to the order in which different statements access memory locations. Using the analysis of these relationships, execution of the loop can be organized to allow multiple processors to work on different portions of the loop in parallel. This is known as parallel processing. In general, loops can consume a lot of processing time when executed as serial code. Through parallel processing, it is possible to reduce the total execution time of a program through sharing the processing load among multiple processors.

The process of organizing statements to allow multiple processors to work on different portions of a loop is often referred to as parallelization. In order to see how we can exploit parallelization, we have to first analyze the dependencies within individual loops. These dependencies will help determine which statements in the loop need to be completed before other statements can start, and which statements in the loop can be executed in parallel with respect to the other statements in the loop. Two general categories of dependencies that will be analyzed in the loop are data dependencies and control dependencies.

Description

Loop dependence analysis occur on a normalized loop of the form:

for i₁ until U₁ do

for i₂ until U₂ do

...

for i_n until U_n do

body

done

...

done

done

where <samp>body</samp> may contain:

S1 a[f₁(i₁, ..., i_n), ..., f_m(i₁, ..., i_n)] := ...

...

S2 ... := a[h₁(i₁, ..., i_n), ..., h_m(i₁, ..., i_n)]

Where a is an m-dimensional array and <samp>f_n</samp>, <samp>h_n</samp>, etc. are functions mapping from all iteration indexes (i_n) to a memory access in a particular dimension of the array.

For example, in C:

<syntaxhighlight lang=c>

for (i = 0; i < U1; i++)

for (j = 0; j < U2; j++)

a[i+4-j] = b[2*i-j] + i*j;

</syntaxhighlight>

f₁ would be <samp>i+4-j</samp>, controlling the write on the first dimension of a and h₂ would be <samp>2*i-j</samp>, controlling the read on the first dimension of b.

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.

Independence is shown by demonstrating that no two instances of S1 and S2 access or modify the same spot in array <samp>a</samp>. 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 or modify the dependence.

In the course of proving or disproving 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 <samp>i1 = 1</samp>, <samp>i2 = 3</samp> and <samp>i3 = 5</samp>. Of course, references to abstract iterations, such as S[d1+1,d2,d3], are both permitted and common.

Data dependence

Data dependencies show the relationships between the variables in the code. There are three different types of data dependencies:

• True Dependence (sometimes referred to as Flow Dependence)
• Anti Dependence
• Output Dependence

True dependence

A true dependence occurs when a location in memory is written to before it is read. This introduces write-after-write (WAW) hazards because the second instruction to write the value to a memory location needs to wait until the first instruction finishes writing data to the same memory location or else when the memory location is read at a later time it will contain the wrong value. One common example is an "if" statement. "if" statements create branches in a program. The "then" portion of the "if" statement explicitly directs or controls actions to be taken. inspired by Implicit computational complexity techniques. They use it to detect not only invariant commands in loops, but also larger code fragments such as an inner loop. The analysis also detects quasi-invariants of arbitrary degrees, that is commands or code fragments that become invariant after a fixed number of iterations of the loop body. The technique was later used by Aubert, Rubiano, Rusch, and Seiller to automatically parallelise loops in C code and to certify polynomial growth of variables.

See also

• Dependence analysis
• Banerjee test
• Alias analysis
• DOPIPE
• Loop Level Parallelism
• Loop transformation
• Loop splitting
• Loop fusion
• Loop interchange
• Loop skewing
• Automatic parallelization
• Automatic vectorization

References