CodeTools[ProgramAnalysis]
DependenceCone
compute dependencies between array references in a loop
Calling Sequence
Parameters
Description
Examples
References
Compatibility
DependenceCone(loop, arrayname, dvars)
DependenceCone(loop, ref1, ref2, dvars)
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
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. 1≤0), 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.
with⁡CodeToolsProgramAnalysis:
Dependencies for all References to an Array
The following procedure computes the matrix multiplication A=B·C :
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 MatrixMultiplication:
loop≔CreateLoop⁡MatrixMultiplication:
Compute the dependence cone for all references to the Array A:
dc1≔DependenceCone⁡loop,A,di,dj,dk
dc1≔1≤dk,dj=0,di=0
This result implies that the accesses to the array A with the indices i,j,k are dependent on the previous writes to the array with indices i,j,k−n, where n∈ℕ. This means that accesses to A[i,j,k] depend on previous loop iterations that have the same i and j (di=0 and dj=0), but smaller values of k (1≤dk).
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]:
dc2≔DependenceCone⁡loop,Ai,j,Ai−1,j−1,di,dj
dc2≔dj=1,di=1
Compute the dependence of A[i-1,j] with respect to A[i, j].
dc3≔DependenceCone⁡loop,Ai−1,j,Ai,j,di,dj
dc3≔1≤0
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.
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.
The CodeTools[ProgramAnalysis][DependenceCone] command was introduced in Maple 2016.
For more information on Maple 2016 changes, see Updates in Maple 2016.
See Also
CodeTools[ProgramAnalysis][IterationSpace]
CodeTools[ProgramAnalysis][CreateLoop]
CodeTools[ProgramAnalysis][GenerateProcedure]
CodeTools[ProgramAnalysis][UnimodularLoopTransformation]
Download Help Document