CodeTools[ProgramAnalysis] - Maple Programming Help

Home : Support : Online Help : Programming : CodeTools : Program Analysis : CodeTools/ProgramAnalysis/DependenceCone

CodeTools[ProgramAnalysis]

 DependenceCone
 compute dependencies between array references in a loop

 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. $1\le 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.

Examples

 > $\mathrm{with}\left({\mathrm{CodeTools}}_{\mathrm{ProgramAnalysis}}\right):$

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 $\mathrm{MatrixMultiplication}$:
 > $\mathrm{loop}≔\mathrm{CreateLoop}\left(\mathrm{MatrixMultiplication}\right):$
 • Compute the dependence cone for all references to the Array A:
 > $\mathrm{dc1}≔\mathrm{DependenceCone}\left(\mathrm{loop},A,\left[\mathrm{di},\mathrm{dj},\mathrm{dk}\right]\right)$
 ${\mathrm{dc1}}{≔}\left[{1}{\le }{\mathrm{dk}}{,}{\mathrm{dj}}{=}{0}{,}{\mathrm{di}}{=}{0}\right]$ (1)
 • This result implies that the accesses to the array A with the indices $\left(i,j,k\right)$ are dependent on the previous writes to the array with indices $\left(i,j,k-n\right)$, where $n\in ℕ$.  This means that accesses to A[i,j,k] depend on previous loop iterations that have the same $i$ and $j$ ($\mathrm{di}=0$ and $\mathrm{dj}=0$), but smaller values of $k$ ($1\le \mathrm{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]:
 > $\mathrm{dc2}≔\mathrm{DependenceCone}\left(\mathrm{loop},{A}_{i,j},{A}_{i-1,j-1},\left[\mathrm{di},\mathrm{dj}\right]\right)$
 ${\mathrm{dc2}}{≔}\left[{\mathrm{dj}}{=}{1}{,}{\mathrm{di}}{=}{1}\right]$ (2)
 • Compute the dependence of A[i-1,j] with respect to A[i, j].
 > $\mathrm{dc3}≔\mathrm{DependenceCone}\left(\mathrm{loop},{A}_{i-1,j},{A}_{i,j},\left[\mathrm{di},\mathrm{dj}\right]\right)$
 ${\mathrm{dc3}}{≔}\left[{1}{\le }{0}\right]$ (3)
 • 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.