|
Calling Sequence
|
|
DependenceCone(loop, arrayname, dvars)
DependenceCone(loop, ref1, ref2, dvars)
|
|
Parameters
|
|
loop
|
-
|
ForLoop to analyze
|
arrayname
|
-
|
symbol; name of an array in loop
|
ref1, ref2
|
-
|
indexed names, references to array elements that appear in loop's body
|
dvars
|
-
|
(optional) list of names, the distance variables' names
|
|
|
|
|
Description
|
|
•
|
DependenceCone computes loop's dependence cone, which is a compact encoding of the dependencies between read and write operations in a ForLoop. The command returns a system of equalities and inequalities that represents a superset to the set of the loop's distance vectors. When the returned value is an inconsistent system (e.g. ), then there exist no dependencies between the array entries across the loop's iterations.
|
•
|
In the first calling sequence, the dependencies between all references to the given array arrayname are computed. Alternatively, the second calling sequence computes the dependencies between two array references into the same array ref1 and ref2, ignoring the other references to that array in the loop.
|
•
|
Use the optional argument dvars to specify the names used for the distance variables in the returned list of relations. There should be one entry for each loop variable. Otherwise, the names for the distance variables are generated automatically.
|
|
|
Examples
|
|
>
|
|
|
Dependencies for all References to an Array
|
|
•
|
The following procedure computes the matrix multiplication :
|
>
|
MatrixMultiplication := proc (A, B, C, m, r, n)
local i, j, k;
for i to m do
for j to n do
for k to r do
A[i, j] := A[i, j] + B[i, k] * C[k, j]:
end do:
end do:
end do:
end proc:
|
•
|
Construct the ForLoop data structure from the procedure :
|
>
|
|
•
|
Compute the dependence cone for all references to the Array A:
|
>
|
|
| (1) |
•
|
This result implies that the accesses to the array A with the indices are dependent on the previous writes to the array with indices , where . This means that accesses to A[i,j,k] depend on previous loop iterations that have the same and ( and ), but smaller values of ().
|
|
|
Dependencies Between Specific Array Accesses
|
|
•
|
Consider the loop in a heat equation solving procedure:
|
>
|
heat_eq := proc (A, m, n)
local i, j;
for i to m do
for j to n do
A[i, j] := A[i-1, j-1] + 2 * A[i-1, j] + A[i-1, j+1] + 3:
end do
end do
end proc:
loop := CreateLoop(heat_eq):
|
•
|
Compute the dependence of A[i, j] with respect to A[i-1, j-1]:
|
>
|
|
•
|
Compute the dependence of A[i-1,j] with respect to A[i, j].
|
>
|
|
•
|
The result is an inconsistent system of equations (i.e. having no solution), meaning that there is no dependence of A[i-1,j] on A[i, j] in any previous iteration of the loop.
|
|
|
|
References
|
|
|
Yi-Qing Yang, Corinne Ancourt, and François Irigoin. "Minimal data dependence abstractions for loop transformations: Extended version." International Journal of Parallel Programming. Vol. 23, No. 4. (1995): 359-388.
|
|
|
Compatibility
|
|
•
|
The CodeTools[ProgramAnalysis][DependenceCone] command was introduced in Maple 2016.
|
|
|
|