15-745 © 2005 Seth Copen Goldstein 115-745Optimizing For Data Locality - 1Seth Copen [email protected] on “A Data Locality Optimizing Algorithm, Wolf & Lam, PLDI ‘9115-745© 2005 Seth Copen Goldstein2Outline• The Problem• Loop Transformations– dependence vectors– Transformations– Unimodular transformations• Some Linear Algerbra15-745© 2005 Seth Copen Goldstein3The Issue• Improve cache reuse in nested loops• Canonical simple case: Matrix Multiplyfor I1:= 1 to nfor I2:= 1 to nfor I3:= 1 to nC[I1,I3] += A[I1,I2] * B[I2,I3]=I1I3I2I2I3I2+1In next iteration of I2previous data that could be reused has been replaced in cache.15-745© 2005 Seth Copen Goldstein4Tiling solves problemfor I1:= 1 to nfor I2:= 1 to nfor I3:= 1 to nC[I1,I3]+=A[I1,I2] * B[I2,I3]=I1I3I2I2I2+1for II2:= 1 to n by sfor II3:= 1 to n by sfor I1:= 1 to nfor I2:= II2to min(II2+ s - 1,n)for I3:= II3to min(II3+ s - 1,n)C[I1,I3]+=A[I1,I2] * B[I2,I3];I315-745© 2005 Seth Copen Goldstein5The Problem• How to increase reuse by transforming loop nest• Matrix Mult is simple as it is both– legal to tile– advantageous to tile• Can we determine both legality and benefit?(reuse vector space)• Can we transform loop to make it legal?(unimodular transformations)15-745© 2005 Seth Copen Goldstein6Loop Transformation Theory•Iteration Space• Dependence vectors• Unimodular transformations15-745© 2005 Seth Copen Goldstein7Loop Nests and the Iter space• General form of tightly nested loop• The iteration space is a convex polyhedron in Znbounded by the loop bounds.• Each iteration is a node in the polyhedron identified by its vector: p=(p1, p2, …, pn)for I1:= low1to high1by step1for I2:= low2to high2by step2…for Ii:= lowito highiby stepi…for In:= lownto highnby stepnStmts15-745© 2005 Seth Copen Goldstein8Lexicographical Ordering• Iterations are executed in lexicographic order.•for p=(p1, p2, …, pn) and q=(q1, q2, …, qn)if p≻kq iff for 1 ≤ k ≤ n,∀ 1 ≤ i < k, (pi= qi) and pk> qk• For MM:– (1,1,1), (1,1,2), (1,1,3), …,(1,2,1), (1,2,2), (1,2,3), …,…,(2,1,1), (2,1,2), (2,1,3), …– (1,2,1) ≻2(1,1,2), (2,1,1) ≻1(1,4,2), etc.15-745© 2005 Seth Copen Goldstein9Iteration SpaceEvery iteration generates a point in an n-dimensional space, where n is the depth of the loop nest.for (i=0; i<n; i++) {}for (i=0; i<n; i++) for (j=0; j<4; j++) {}32415-745© 2005 Seth Copen Goldstein10Dependence Vectors• Dependence vector in an n-nested loop is denoted as a vector: d=(d1, d2, …, dn).•Each diis a possibly infinite range of ints in , where• So, a single dep vector represents a set of distance vectors.• A distance vector defines a distance in the iteration space.• A dependence vector is a distance vector if each diis a singleton.[]maxmin,iidd and}{},{maxminmaxminiiiidddd ≤∞∪Ζ∈−∞∪Ζ∈15-745© 2005 Seth Copen Goldstein11Other defs• Common ranges in dependence vectors–[1, ∞] as + or >–[-∞, -1] as – or <–[-∞, ∞] as ± or *• A distance vector is the difference between the target and source iterations (for a dependent ref), e.g., d = It-Is15-745© 2005 Seth Copen Goldstein12Examplesfor I1:= 1 to nfor I2:= 1 to nfor I3:= 1 to nC[I1,I3] += A[I1,I2] * B[I2,I3](0,1,0)for I1:= 0 to 5for I2:= 0 to 6A[I2+ 1] := 1/3 * (A[I2] + A[I2+1]+A[I2+2])I1I2D={(0,1),(1,0),(1-1)}15-745© 2005 Seth Copen Goldstein13Loop indep and dep data deps• A loop independent data dependence has a dependence vector of ?• A loop dependent data dependence has a dependence vector of ?15-745© 2005 Seth Copen Goldstein14Plausible Dependence vectors• A dependence vector is plausible iffit is lexicographically non-negative.• All sequential programs have plausible dependence vectors. Why?•Plausible: (1,-1)• implausible (-1,0)(-1,0)112233ji[1,1] [1,2] [1,3](0,1)[2,1] [2,2] [2,3][3,1] [3,2] [3,3](0,-1)(1,-1) (-1,0)112233ji[1,1] [1,2] [1,3](0,1)[2,1] [2,2] [2,3][3,1] [3,2] [3,3](0,-1)(1,-1)15-745© 2005 Seth Copen Goldstein15Loop Transforms• A loop transformation changes the order in which iterations in the iteration space are visited.• For example, Loop Interchangefor i := 0 to nfor j := 0 to mbodyfor j := 0 to mfor i := 0 to nbodyijji15-745© 2005 Seth Copen Goldstein16Unimodular Transforms•Interchangepermute nesting order• Reversalreverse order of iterations•Skewingscale iterations by an outer loop index15-745© 2005 Seth Copen Goldstein17Interchange• Change order of loops• For some permutation p of 1 … n• When is this legal?for I1:= …for I2:= ……for In:= …bodyfor Ip(1):= …for Ip(2):= ……for Ip(n):= …body15-745© 2005 Seth Copen Goldstein18Transform and matrix notation• If dependences are vectors in iterspace, then transforms can be represented as matrix transforms• E.g., for a 2-deep loop, interchange is:• Since, T is a linear transform, Td is transformed dependence:⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡12210110pppp⎥⎦⎤⎢⎣⎡=0110T⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡12210110dddd15-745© 2005 Seth Copen Goldstein19Reversal• Reversal of ithloop reverses its traversal, so it can be represented as:15-745© 2005 Seth Copen Goldstein20Reversal• Reversal of ithloop reverses its traversal, so it can be represented as: Diagonal matrix with ithelement = -1.• For 2 deep loop, reversal of outermost is:⎥⎦⎤⎢⎣⎡−=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡−21001121pppp⎥⎦⎤⎢⎣⎡−=1001T15-745© 2005 Seth Copen Goldstein21Skewing• Skew loop Ijby a factor f w.r.t. loop Iimaps•Example for 2D,...),...,,...,(1 jippp,...),...,,...,(1 ijifpppp+⎥⎦⎤⎢⎣⎡+=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡121211101ppppp⎥⎦⎤⎢⎣⎡=1101T15-745© 2005 Seth Copen Goldstein22Loop Skewing Examplefor I1:= 0 to 5for I2:= 0 to 6A[I2+ 1] := 1/3 * (A[I2] + A[I2+1]+A[I2+2])I1I2D={(0,1),(1,0),(1-1)}for I1:= 0 to 5for I2:= I1to 6+I1A[I2-I1+1] := 1/3 * (A[I2-I1]+A[I2-I1+ 1] + A[I2-I1+ 2])⎥⎦⎤⎢⎣⎡=1101TI1I2D={(0,1),(1,1),(1,0)}15-745© 2005 Seth Copen Goldstein23Linear Algebra•Vector Spaces• Linear Combinations• dimensions•Spans• Kernels15-745© 2005 Seth Copen Goldstein24Vector Spaces• n is a point in n-space•V = { v1, v2, …, vm} is a finite set of n-vectors over m ℜn.• Linear combination of vectors of V isa vector x as defined byx = α1v1+ α2v2+ … + αmvmwhere αiare real numbers.• V is linearly dependent if a combination results
View Full Document
Unlocking...