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.

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. S1 a[f 1 (i 1 , ..., i n ), ..., f m (i 1 , ..., i n )] := ... ... S2 ... := a[h 1 (i 1 , ..., i n ), ..., h m (i 1 , ..., i n )] Where a is an m-dimensional array and f n , h n , 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: for (i = 0; i f 1 would be i+4-j , controlling the write on the first dimension of a and h 2 would be 2*i-j , 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 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 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 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. S1: a = 5; S2: b = a; In this example, there is a true dependence between S1 and S2 because variable a is first written in statement S1 and then variable a is read by statement S2. This true dependence can be represented by S1 →T S2. A true dependence can also be seen when reading and writing between different iterations in a loop. The following example shows a true dependence between different iterations. for (j = 1; j In this example, a true dependence exists between statement S1 in the jth iteration and S1 in the j+1th iteration. There is a true dependence because a value will be written to a[j] in one iteration and then a read occurs by a[j-1] in the next iteration. This true dependence can be represented by S1[j] →T S1[j+1]. S1: a = b; S2: b = 5; In this example, there is an anti dependence between statements S1 and S2. This is an anti dependence because variable b is first read in statement S1 and then variable b is written to in statement S2. This can be represented by S1 →A S2. An anti dependence can be seen by different iterations in a loop. The following example shows an example of this case: for (j = 0; j In this example, there is an anti dependence between the jth iteration of S1 and the j+1th element of S1. Here, the j+1th element is read before that same element is written in the next iteration of j. This anti dependence can be represented by S1[j] →A S1[j+1]. S1: c = 8; S2: c = 15; In this example, there is an output dependence between statements S1 and S2. Here, the variable c is first written to in S1 and then variable c is written to again in statement S2. This output dependence can be represented by S1 →O S2. An output dependence can be seen by different iterations in a loop. The following code snippet shows an example of this case: for (j = 0; j In this example, there is an output dependence between the jth element in S1 and the j+1th element in S2. Here, c[j+1] in statement S2 is written to in one iteration. In the next iteration, c[j] in statement S2, which is the same memory location as c[j+1] in the previous iteration, is written to again. This output dependence can be represented as S1[j] →O S2[j+1]. It is easier to show the difference between the two graphs with a nested for loop. for (i = 0; i In this example, there is a true dependence between the j iteration of statement S1 and the j+1th statement of S1. 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:

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369807015 under CC BY-SA 4.0; modifications have been made.