1CS553 Lecture Data Dependence Analysis 2Compiling for Parallelism & Locality Assignments– Deadline for project 4 extended to Dec 1 Last time– Data dependences and loops Today– Finish data dependence analysis for loopsCS553 Lecture Data Dependence Analysis 3Dependence Testing in General General code do i1 = l1,h1 ... do in = ln,hn A(f(i1,...,in)) = ... A(g(i1,...,in)) enddo ...enddo There exists a dependence between iterations I=(i1, ..., in) and J=(j1, ..., jn)when– f(I) = g(J)– (l1,...ln) < I,J < (h1,...,hn)CS553 Lecture Data Dependence Analysis 4Algorithms for Solving the Dependence Problem Heuristics– GCD test (Banerjee76,Towle76): determines whether integer solution ispossible, no bounds checking– Banerjee test (Banerjee 79): checks real bounds– I-Test (Kong et al. 90): integer solution in real bounds– Lambda test (Li et al. 90): all dimensions simultaneously– Delta test (Goff et al. 91): pattern matches for efficiency– Power test (Wolfe et al. 92): extended GCD and Fourier Motzkin combination Use some form of Fourier-Motzkin elimination for integers,exponential worst-case– Parametric Integer Programming (Feautrier91)– Omega test (Pugh92)CS553 Lecture Data Dependence Analysis 5Dependence Testing Consider the following code… do i = 1,5A(3*i+2) = A(2*i+1)+1 enddo Question– How do we determine whether one array reference depends on anotheracross iterations of an iteration space? A(3*i+2) = A(2*i+1)+12CS553 Lecture Data Dependence Analysis 6Dependence Testing: Simple Case Sample code do i = l,h A(a*i+c1) = ... A(a*i+c2)enddo Dependence?– a*i1+c1 = a*i2+c2, or– a*i1 – a*i2 = c2-c1– Solution exists if a divides c2-c1CS553 Lecture Data Dependence Analysis 7Example Code do i = l,h A(2*i+2) = A(2*i-2)+1enddo Dependence? 2*i1 – 2*i2 = -2 – 2 = -4 (yes, 2 divides -4) Kind of dependence?– Anti? i2 + d = i1 ⇒ d = -2− Flow? i1 + d = i2 ⇒ d = 2i1i2CS553 Lecture Data Dependence Analysis 8GCD Test Idea– Generalize test to linear functions of iterators Code do i = li,hi do j = lj,hj A(a1*i + a2*j + a0) = ... A(b1*i + b2*j + b0) ...enddoenddo Again– a1*i1 - b1*i2 + a2*j1 – b2*j2 = b0 – a0– Solution exists if gcd(a1,a2,b1,b2) divides b0 – a0CS553 Lecture Data Dependence Analysis 9Example Code do i = li,hi do j = lj,hj A(4*i + 2*j + 1) = ... A(6*i + 2*j + 4) ...enddoenddo gcd(4,-6,2,-2) = 2 Does 2 divide 4-1?3CS553 Lecture Data Dependence Analysis 10Banerjee Testfor (i=L; i<=U; i++) { x[a_0 + a_1*i] = ... ... = x[b_0 + b_1*i]}Does a_0 + a_1*i = b_0 + b_1*i’ for some integer i and i’?If so then (a_1*i - b_1*i’) = (b_0 - a_0)Determine upper and lower bounds on (a_1*i - b_1*i’)for (i=1; i<=5; i++) { x[i+5] = x[i];}upper bound = a_1*max(i) - b_1 * min(i’) = 4lower bound = a_1*min(i) - b_1*max(i’) = -4b_0 - a_0 =CS553 Lecture Data Dependence Analysis 11Distance Vectors: Legality Definition– A dependence vector, v, is lexicographically nonnegative when the left-most entry in v is positive or all elements of v are zeroYes: (0,0,0), (0,1), (0,2,-2)No: (-1), (0,-2), (0,-1,1)– A dependence vector is legal when it is lexicographically nonnegative(assuming that indices increase as we iterate) Why are lexicographically negative distance vectors illegal? What are legal direction vectors?CS553 Lecture Data Dependence Analysis 12Direction Vector Definition– A direction vector serves the same purpose as a distance vector when lessprecision is required or available– Element i of a direction vector is <, >, or = based on whether the source ofthe dependence precedes, follows or is in the same iteration as the targetin loop i Example do i = 1,6 do j = 1,5 A(i,j) = A(i-1,j-1)+1 enddo enddo Direction vector: Distance vector:ij(<,<)(1,1)CS553 Lecture Data Dependence Analysis 13Loop-Carried Dependences Definition– A dependence D=(d1,...dn) is carried at loop level i if di is the first nonzeroelement of D Example do i = 1,6 do j = 1,6 A(i,j) = B(i-1,j)+1 B(i,j) = A(i,j-1)*2 enddo enddo Distance vectors: (0,1) for accesses to A (1,0) for accesses to B Loop-carried dependences– The j loop carries dependence due to A– The i loop carries dependence due to B4CS553 Lecture Data Dependence Analysis 14 Idea– Each iteration of a loop may be executed in parallel if it carries nodependences Example do i = 1,6 do j = 1,5 A(i,j) = B(i-1,j-1)+1 B(i,j) = A(i,j-1)*2 enddo enddo Parallelize i loop?ParallelizationijIteration SpaceDistance Vectors: (1,0) for A (flow)(1,1) for B (flow)CS553 Lecture Data Dependence Analysis 15 Idea– Each iteration of a loop may be executed in parallel if it carries nodependences Example do i = 1,6 do j = 1,5 A(i,j) = B(i-1,j-1)+1 B(i,j) = A(i,j-1)*2 enddo enddo Parallelize j loop?ParallelizationijIteration SpaceDistance Vectors: (1,0) for A (flow)(1,1) for B (flow)CS553 Lecture Data Dependence Analysis 16Example 2: Parallelization (reprise) Why can’t this loop be parallelized? do i = 1,100 A(i) = A(i-1)+1 enddo Why can this loop be parallelized? do i = 1,100 A(i) = A(i)+1 enddo1 2 3 4 5 ...i1 2 3 4 5 ...iDistance Vector: (1)Distance Vector: (0)CS553 Lecture Data Dependence Analysis 17 Sample code do j = 1,6 do i = 1,5 A(j,i) = A(j,i)+1 enddo enddo Why is this legal?– No loop-carried dependences, so we can arbitrarily change order ofiteration executionExample 1: Loop Permutation (reprise)do i = 1,5 do j = 1,6 A(j,i) = A(j,i)+1 enddoenddo5CS553 Lecture Data Dependence Analysis 18Concepts Improve performance by ...– improving data locality– parallizing the computation Data Dependences– iteration space– distance vectors and direction vectors– loop carried Transformation legality– must respect data dependences– scalar expansion as a technique to remove anti and output dependences Data Dependence Testing– general formulation of the problem– GCD testCS553 Lecture Data Dependence Analysis 19Next Time Lecture– Loop transformations for parallelism and