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.

In general, loops can consume a lot of processing time when executed as serial code.

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.

are functions mapping from all iteration indexes (in) to a memory access in a particular dimension of the array.

Independence is shown by demonstrating that no two instances of S1 and S2 access or modify the same spot in array a.

A true dependence can also be seen when reading and writing between different iterations in a loop.

The following example shows an example of this case: In this example, there is an anti dependence between the jth iteration of S1 and the j+1th element of S1.

Code block 1 shows the correct ordering when using an if statement in the C programming language.

Both of these two possibilities could lead to improper program execution and must be considered when parallelizing these statements within a loop.

Code block 2 show loop independent dependence between statements S1 and S2 in the same iteration.

This can be represented as S1[i,j] →T S1[i,j+1] The iteration space traversal graph and the loop carried dependence graph is: Iteration Space Traversal Graph: Loop Carried Dependence Graph: Recent work by Moyen, Rubiano and Seiller introduced a new data-flow dependence analysis [5] inspired by Implicit computational complexity techniques.

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[6] to automatically parallelise loops in C code.