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.
Loop dependence analysis occur on a normalized loop of the form:
for i1 until U1 do for i2 until U2 do ... for in until Un do body done ... done done
where body may contain:
S1 a[f<sub>1</sub>(i<sub>1</sub>, ..., i<sub>n</sub>), ..., f<sub>m</sub>(i<sub>1</sub>, ..., i<sub>n</sub>)] := ... ... S2 ... := a[h<sub>1</sub>(i<sub>1</sub>, ..., i<sub>n</sub>), ..., h<sub>m</sub>(i<sub>1</sub>, ..., i<sub>n</sub>)]
Where a is an m-dimensional array and fn, hn, etc. are functions mapping from all iteration indexes (in) to a memory access in a particular dimension of the array.
For example, in C:
f1 would be i+4-j, controlling the write on the first dimension of a and h2 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.
Data dependencies show the relationships between the variables in the code. There are three different types of data dependencies:
A true dependence occurs when a location in memory is written to before it is read.[1] [2] It introduces read-after-write (RAW) hazards because the instruction that reads from the location in memory has to wait until it is written to by the previous instruction or else the reading instruction will read the wrong value. An example of a true dependence is:
An anti dependence occurs when a location in memory is read before that same location is written to. This introduces write-after-read (WAR) hazards because the instruction that writes the data into a memory location has to wait until that memory location has been read by the previous instruction or else the reading instruction would read the wrong value. An example of an anti dependence is:
An output dependence occurs when a location in memory is written to before that same location is written to again in another statement.[3] 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. An example of an output dependence is:
Control dependencies must also be considered when analyzing dependencies between different statements in a loop. Control dependencies are dependencies introduced by the code or the programming algorithm itself. They control the order in which instructions occur within the execution of code.[4] 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.
b) d = "uncontrolled"; | b) c = "controlled";d = "uncontrolled"; | b) |
Loop-carried dependencies and loop independent dependencies are determined by the relationships between statements in iterations of a loop. When a statement in one iteration of a loop depends in some way on a statement in a different iteration of the same loop, a loop-carried dependence exists. However, if a statement in one iteration of a loop depends only on a statement in the same iteration of the loop, this creates a loop independent dependence.
Iteration space traversal graphs (ITG) shows the path that the code takes when traversing through the iterations of the loop. Each iteration is represented with a node. Loop carried dependence graphs (LDG) gives a visual representation of all true dependencies, anti dependencies, and output dependencies that exist between different iterations in a loop. Each iteration is represented with a node.It is easier to show the difference between the two graphs with a nested for loop.