15-745 Lecture 715-745 Lecture 7Data Dependence in Loops – 2Delta TestDelta TestMerging vectorsC i ht © S th G ld t i 2008Lecture 6 15-745 © 2005-8 1Copyright © Seth Goldstein, 2008Based on slides from Allen&KennedyThe General ProblemDO i1= L1, U1DO i2= L2, U2...DO in= Ln, UnS1A(f1(i1,...,in),...,fm(i1,...,in)) = ...S2... = A(g1(i1,...,in),...,gm(i1,...,in))ENDDO...ENDDOENDDOENDDOA dependence exists from S1 to S2 if:h d h h–There exist α and β such that• α < β (control flow requirement)•f(α)=g(β) for alli1 ≤i ≤ m(common access req)•fi(α) =gi(β) for all i, 1 ≤ i ≤ m(common access req)ZIV TestDO j = 1, 100SA(e1) = A(e2) + B(j)SA(e1) = A(e2) + B(j)ENDDOe1,e2 are constants or loop invariant symbolsyIf (e1-e2)!=0 No Dependence exists DO i1= L1, U1DO i=LUStrong SIV TestDO i2= L2, U2...DO in= Ln, UnS1A(f1(i1,...,in),...,fm(i1,...,in)) = ...1(1(1,,n), ,m(1,,n))S2... = A(g1(i1,...,in),...,gm(i1,...,in))ENDDO...ENDDOENDDO• Strong SIV test when• f(...) = aik+c1and g(…) = aik+c2• Plug in α,β and solve for dependence: ()/• β-α = (c1–c2)/a• A dependence exists from S1 to S2 if:•βαis an integer•β-αis an integer• |β-α| ≤ Uk-LkCan extend to symbolic constants• Determine d symbolically•If d is a constant use previous procedureIf d is a constant, use previous procedure• Otherwise, calculate U-L symbolically•Compare UL and d symbolically (& hope)•Compare U-L and d symbolically (& hope)Eg •E.g., for i=1 to NA[i+2*N] = A[i]A[i 2 N] A[i]Lecture 6 15-745 © 2005-8 5DO i1= L1, U1DO i=LUWeak-zero SIV TestDO i2= L2, U2...DO in= Ln, UnS1A(f1(i1,...,in),...,fm(i1,...,in)) = ...1(1(1,,n), ,m(1,,n))S2... = A(g1(i1,...,in),...,gm(i1,...,in))ENDDO...ENDDOENDDO• Weak-Zero SIV test when• f(...) = aik+c1and g(…) = c2• Plug in α,β and solve for dependence:/• α = (c2–c1)/a• A dependence exists from S1 to S2 if:•is an integer•αis an integer• Lk≤α≤UkDO i1= L1, U1DO i=LUWeak-crossing SIV TestDO i2= L2, U2...DO in= Ln, UnS1A(f1(i1,...,in),...,fm(i1,...,in)) = ...1(1(1,,n), ,m(1,,n))S2... = A(g1(i1,...,in),...,gm(i1,...,in))ENDDO...ENDDOENDDO• Weak-Zero SIV test when• f(...) = aik+c1and g(…) = -aikc2• To find crossing point, set α = β and solve:/• α = (c2–c1)/2a• A dependence exists from S1 to S2 if:•2αis an integer•2αis an integer• Lk≤α≤UkNon-rectangular spaces• Triangular iteration space when only one loop bound depends on an outer loop indexbound depends on an outer loop ndex• Trapezoidal space when both loop bounds depend on an outer loop indexpp•Example:Examplefor i=1 to Nfor j=L0+L1*I to U0+U1*IA[j+D] = …… = A[j]– Is d in loop bounds?Lecture 6 15-745 © 2005-8 8How are we doing so far?• Empirical study froom Goff, Kennedy, & Tseng– Look at how often independence and exact d p nd nc inf m ti n is f und in 4 suit s f dependence information is found in 4 suites of fortran programs–Compare ZIV, SIV (strong, weak-0, weak-crossing, mp , ( g,,g,exact), MIV, Delta– Check usefulness of symbolic analysis• ZIV used 44% of time and proves 85% of indep• Strong-SIV used 33% of time and proves 5%(success per application 97%)(success per application 97%)• S-SIV, 0-SIV, x-SIV used 41%• MIV used only 5% of timey• Delta used 8% of time, proves 5% of indep• Coupled subscripts rare (20% overall, but concentrated)Lecture 6 15-745 © 2005-8 9Basics:Coupled Subscript Groups• Why are they important?Coupling can cause imprecision in dependence Coupling can cause imprecision in dependence testingDO I = 1, 100S1A(I+1,I) = B(I) + C(,) ()S2 D(I) = A(I,I) * EENDDODealing w/ Coupled Groups• subscript-by-subscript testing to impreciseHowever we could intersect depsHowever, we could intersect depsDO I = 1, 100S1 A(I+1,I) = B(I) + CS2 D(I) = A(I,I) * EENDDOfi t ild d1 d d 0 Th t’ first yields d=+1, second d=0. That’s impossible. Therefore, no dependence•Delta test uses this intuition when the •Delta test uses this intuition when the subscripts are SIV to apply information between indicestw n n cLecture 6 15-745 © 2005-8 11ExamplesFor IFor JApply SIV to yield: ΔI=1For JA[I+1,I+J] = … = A[I I+J1]I0+J0= I0+ΔI +J0+ΔJ-10= ΔI + ΔJ-1 1 ΔJ1… = A[I, I+J-1]For I For J For K= 1 + ΔJ-1ΔJ = 0For I, For J, For KA[J-I,I+1,J+K] = A[J-I,I,J+K]Apply SIV to yield: ΔI=1J0-I0= J0+ΔJ-I0-ΔI0= ΔJ ΔIJ0+K0= J0+ΔJ+K0+ΔK0= ΔJ +ΔKLecture 6 15-745 © 2005-8 120= ΔJ -ΔI0= ΔJ-1ΔJ = 10 = 1 +ΔKΔK = -1Constraints• An assertion about an index that must hold for a dependence to exist.a dependence to ex st.• So, when intersection of constraints is empty, must be independentp• In Delta test we generate constraints from SIV tests, so distance (or direction vector) is sufficientLecture 6 15-745 © 2005-8 13Delta TestProcedure delta(subscr, constr)Init constraint vector C to <none>while exist untested SIV subscripts in subscrapply SIV test to all untested SIV subscriptsreturn independence, or derive new constraint vector C’.C’ <- C ∩ C’If C’ = Ø then return independenceelse if C != C’ thenC <- C’propagateCinto MIV subscriptspropagate Cinto MIV subscriptsapply ZIV test to untested ZIV subscriptsreturn independence if no solutionwhile exist untested RDIV subscriptstest andpropogateRDIV constantstest and propogateRDIV constantstest remaining MIV subscripts using MIV testsintersect direction vectors with C, and returnLecture 6 15-745 © 2005-8 14Merging Results• After we test all subscripts we have vectors for each partition. Now we need to merge for each part t on. Now we need to merge these into a set of direction vectors for the memory reference• Since we partitioned into separable sets we can do cross-product of vectors from each iipartition.• Start with a single vector = (*,*,…,*) of length dth f l tdepth of loop nest.• Foreach parition, for each index involved in vector create new set from vector create new set from old vector-these indicies x this setLecture 6 15-745 © 2005-8 15Example MergeFor IFor JFor JS1A[J-1] = …S = A[J]S2… = A[J]For 1stsubscript in A using Sas source and Sas For 1stsubscript in A using S1as source and S2as target: J has DV of -1Merge 1 into (**) > (*1) What does thismean?Merge -1 into (,) -> (,-1). What does thismean?• (<,-1): true dep in outer loop(1):antidepfrom Sto SÆ(1)Lecture 6 15-745 © 2005-8 16•(=,-1):anti-depfrom S2to S1Æ(=,1)• (>,-1): anti-dep from S2to
View Full Document
Unlocking...