Dependence Analysis of Data Arrays: Understanding Iteration Space and Testing

Dependence Analysis of Data Array Presented By: Neelam.S.Gaidhankar Roll No: 04

Dependence testing of successive iteration in multi-dimensional data array . Its provide a theoretical foundation for the development of vectorising. The 3 main parts of a dependence analysis of data arrays such as: Iteration space & dependence analysis. Dependence Testing. Iteration Space. Dependence Equations. Distance & Direction vectors.

Subscript Separability & Partitioning. Subscript Categories. Subscript Separability. Subscript partitioning. Categorized dependence Tests. The Testing Algorithm. Test Categories. The ZIV Test. The SIV Test. Weak-Zero SIV Test. Weak-Crossing SIV Test. The MIV Tests.

Iteration space & dependence analysis Flow dependence, anti-dependence & output dependence is defined for scalar data. The existence of a dynamic references of R1 & R2, If & only if either R1 or R2 is a write operation, R1 executes before R2, or R1 & R2 both write the same variable. When the referenced object is a data array indexed by a multi- dimensional subscript. The dependence may become very difficult to determine at compile time. A process of computing all data dependences in a program is called Dependence analysis

Dependence Testing: calculating data dependence for array is complicated. Two array references may not access the same memory location. Dependence testing is a method, used to determine whether dependences exit b/w two subscript. It references to the same array in a loop nest. Eg: The following model loop nest of n levels, represented by n integer indices i1,i2, .in.

do i1=L1,U1 do i2=L2,U2 do in= Ln, s1: A(f1(i1, .in), ..,fm(i1, ..in))= . s2: .=A(g1(i1, .in), ..,gm(i1, in)) Enddo . Enddo Enddo.

Iteration space: The n dimensional discrete Cartesian space for n-deep loop is called an Iterationspace . Eg: Lexicographic order for sequential execution of successive iterations in a loop structure(Monica lam,1992) A two dimensional iteration space in below fig, were a two- level loop nest in unit-increment steps:

do i=0,5 do j=i,7 f(i, j)= .. Enddo Enddo.

The following sequential order of iteration is a lexicographic order: (0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7) (1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7) (2,2),(2,3),(2,4),(2,5),(2,6),(2,7) (3,3),(3,4),(3,5),(3,6),(3,7) (4,4),(4,5),(4,6),(4,7) (5,5),(5,6),(5,7)

Dependence equation: Let and be vector of n integer ,within the range of upper & lower loop bounds of the n loops. There is a dependence from s1 to s2 ,if and only if their exit and . Such that is lexicographical fi( )= i ( ) i,1 i m.

Distance & Distance vector: A data dependence for =(a1,a2, .a3) & =( 1, 2, n). The distance vector D=(D1, Dn) is defined as - . The distance vector d=(d1,d2, .dn) of the dependence is defined by, di={< if i < i = if i = i > if i > i. The elements are always displayed in order from left to right &from outermost to innermost loop in the nest. Direction vectors are useful for calculating the level of loop-carried dependences.

Subscript separability & partitioning Dependence testing has 2 goals: It tries to disprove the dependence b/w pairs of subscripted references to the same array variable. It tries to characterize them in some manner, like a minimum complete set of distance & direction vectors. Dependence testing must also be conservative.

Subscript categories: A subscript refers to one of the subscripted positions in a pair of array references. A subscript is said to be Zero index variable(ZIV),if the subscript position contains no index in reference. A subscript is said to be single index variable(ZIV),if only one index occurs in that position. A subscript with more than one index is said to be Multiple index variable(MIV). Do i1=L1,U1 Do j=L2,U2 Do k=Ln,Un A(5,i+1,j)=A(N,i,k)+C Enddo Enddo Enddo

Subscript separability: When testing multidimensional arrays, a subscript position is separable. If two different subscript contain the same index then is coupled. separability is important bcz, multidimensional array references in dependence testing. Eg: Do i1=L1,U1 Do j=L2,U2 Do k=L3,U3 A(i,j,j)=A(i,j,k)+c Enddo Enddo Enddo. The 1st subscript is separable bcz,index i not appear in dimension. The 2nd & 3rd are coupled bcz, they both contain index j. ZIV subscript are separable bcz they contain no Indices.

Subscript partitioning: The subscript in a pair of array references as separable or minimal coupled group. A coupled is minimal, if it cannot be partitioned into two non-empty subgroups, with distinct set of indices. Once a partition is achieved, each separable & each coupled group has completely disjoint set of indices. Eg: Do i=L1,U1 Do j=L2,U2 A(i+1,j)=A9i,j)+c Enddo The 1st subscript yield the direction vector(<) for the i-loop & 2nd subscript yield the direction vector(=) for the j-loop. Enddo

Categorized Dependence Tests The goal of dependence testing is to construct the set of distance & direction vectors. A potential dependences b/w an arbitrary pair of subscripted references to the same array variable. Hence distance vectors may be treated as direction vectors.

The Testing Algorithm: Some are following procedure is for dependence testing based on a partitioning approach such as: I. partition the subscripts into separable & minimal coupled groups using the algorithm. II. Label each subscript as ZIV,SIV,MIV. III. For each separable, apply single subscript test based on the complexity of the subscript. IV. For each control group, apply a multiple subscript test, to produce a set of direction vector. V. If any test yields independence, no dependence exits. VI. Otherwise merge all direction vectors.

Test categories: Dependence test result for ZIV subscript are treated specially. If a ZIP subscript proves independence, the independence test algorithm halts immediately. If independence is not proved, the ZIV test does not produce direction vectors & no merge is necessary. To implement the algorithm, we have specified how to perform the single subscript tests (ZIV,SIV,MIV) separately. The trivial case of ZIV 1ST, SIV 2nd finally MIV 3rd which is more involved. A subscript expression is linear if it has a1 i1+a2 i2 + ..+an in + e.

The ZIV Test: The ZIV Test is dependence test performed on 2 loop-invariant expression. If the system determine the two expression cannot be equal, it has proved independence. Otherwise, the subscript does not contribute any direction vectors . The ZIV test can be easily extended for symbolic expression.

The SIV Test: The SIV subscript for index i is said to be strong if it has the form (ai + c1,ai + c2). If a linear and coefficients of two occurrences of index i are constant & equal. For strong SIV subscript, define the dependence distance as d=i - i = c1-c2 / a A dependence exits if & only if d is an integer and |d| U L, where U and L are the loop upper and lower bounds.

Weak-Zero SIV Test: The case in which a1=0 or a2=0 is called a weak-zero SIV subscript. If a2 = 0, the dependence equation reduces to, i = c2-c1 / a1. To check the resulting value for I is an integer & within the loop bounds, a similar check applies when a1 = 0. The weak-zero SIV finds dependence caused by particular iteration i. Eg: Do i=1,N A(i + 2N) = A(i + N) The i is usually the first or last iteration of the loop. Enddo

Weak-crossing SIV Test: All subscripts where a2 = -a1 are weak-crossing SIV. In these cases we set i=i and derive dependence equation as i=c2-c1 / 2a1 The intersection of dependence equation with the line i=i . Weak-crossing SIV subscript cause crossing dependences, loop carried dependences. Whose end points all cross iteration i.

The MIV Tests: SIV tests can be extended to handle complex iteration space. Eg: triangle or trapezoidal loops. To compute the minimum & maximum loop bounds for each loop index. Starting at the outermost loop nest & working inward. Each index in a loop upper bound with a maximum value. The opposite in lower bound, replacing each index with a minimal value.