Understanding Data Dependencies in Nested Loops

Slide Note

Studying data dependencies in nested loops is crucial for optimizing code performance. The analysis involves assessing dependencies across loop iterations, iteration numbers, iteration vectors, and loop nests. Dependencies in loop nests are determined by iteration vectors, memory accesses, and write operations between statements within the loop body. Knowing how data dependencies propagate within nested loops helps in parallelization and optimization strategies.

kentleywe Follow

Uploaded on Sep 19, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Dependency Analysis Dependency Analysis

Recap Recap Program Equivalence Data dependencies across loop iterations

Data Dependencies in Nested Loop Data Dependencies in Nested Loop Iteration Number loop index: I Lower and Upper Bound: L and U Step size: S iteration number i = (I L+1) / S Example: Suppose, L= 1, U = 10, I = 7, S =2 L=1; U=10; S=2; for(int I=L; I<=U; I+=S) { } i = (7 1 +1)/2 = 4

Data Dependencies in Nested Loop Data Dependencies in Nested Loop Iteration Vector Consider a nest of n loops labelled by 1 <= k <=n from the outer to the inner loop. The iteration vector i = {i1, i2, , in} of a particular iteration of the n-th loop is a vector of integers that contains the iteration numbers for each of the loops in order of nesting level. Example: for(int i=1;i<=2;i++) { // 1 for (int j=1;j<=2;j++) { // 2 S; } } S(2,1) is the instance of statement S in the - 2nd iteration of the 1-loop and - 1st iteration of the 2-loop

Data Dependencies in Nested Loop Data Dependencies in Nested Loop Iteration Space All possible iteration vectors Example: {(1,1), (1,2), (2,1), (2,2)} for(int i=1;i<=2;i++) { // 1 for (int j=1;j<=2;j++) { // 2 S; } }

Data Dependencies in Nested Loop Data Dependencies in Nested Loop ikis the kth element of the vector i i = (2,1) i[1:k] is a k-vector consisting of the leftmost k elements of i i1 = 2, i2 = 1 i[1:2]= (2,1) Iteration i precedes iteration j, denoted i < j, if and only if Given i =(2,1) and j =(2,2) 1) i[1:n-1] < j[1:n-1] or i < j (2,1) < (2,2) 2) i[1:n-1] = j[1:n-1] and in< jn

Dependence in Loop Nest Dependence in Loop Nest There exists a dependence from statement S1 to statement S2 in a common nest of loops if and only if there exist two iteration vectors i and j for the nest, such that (1) i < j or i = j and there is a path from S1 to S2 in the body of the loop, (2) statement S1 accesses memory location M on iteration i and statement S2 accesses location M on iteration j, and (3) one of these accesses is a write.

Dependence in Loop Nest Dependence in Loop Nest There exists a dependence from statement S1 to statement S2 in a common nest of loops if and only if there exist two iteration vectors i and j for the nest, such that (1) i < j or i = j and there is a path from S1 to S2 in the body of the loop, (2) statement S1 accesses memory location M on iteration i and statement S2 accesses location M on iteration j, and (3) one of these accesses is a write. for(int i = 1, i<=N; i++){ // 1 for(int j=1; j<=2; j++){ // 2 S0: A[i][j] = A[i][j] + B } S1: T = A(i,1); S2: A(i,1) = A(i,2); S3: A(i,2) = T; } S0 j=2 j=1 j=1 j=2 S3 S1 S2

Distance Vector Distance Vector If there is a dependence from S1 on iteration i to S2 on iteration j; then the dependence distance vectord(i, j) is defined as d(i, j) = j - i for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ for(int k=1; k<=L; k++){ S1: a[i+1,j,k-1] = a[i,j,k]+1; } } } j = (2,2,2) reads a[2][2][2] i = (1,2,3) writes a[2][2][2] d(i,j) = j i = (1,0,-1)

Direction Vector Direction Vector If there is a dependence from S1 on iteration i and S2 on iteration j; then the dependence direction vectorD(i, j) is defined as < if d(i, j)k > 0 = if d(i, j)k = 0 > if d(i, j)k < 0 D(i, j)k = for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ for(int k=1; k<=L; k++){ S1: a[i+1,j,k-1] = a[i,j,k]+1; } } } j = (2,2,2) reads a[2][2][2] i = (1,2,3) writes a[2][2][2] d(i,j) = j i = (1,0,-1) D(i,j) = (<, =, >)

Direction Vector and Dependencies Direction Vector and Dependencies A dependence cannot exist if it has a direction vector such that the leftmost non- = component is not < j = (2,2,2) reads a[2][2][2] for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ for(int k=1; k<=L; k++){ S1: a[i+1,j,k-1] = a[i,j,k]+1; } } } i = (1,2,3) writes a[2][2][2] d(i,j) = j i = (1,0,-1) D(i,j) = (<, =, >) There is a data dependence

Loop Loop- -carried carried Dependences Dependences There is loop-carried dependence takes place across iterations in a loop. Statement S2 has a loop-carried dependence on statement S1 if and only if - S1 references location M on iteration i, S2 references M on iteration j and - d(i,j) > 0 (that is, D(i,j) contains a < as leftmost non = component). The level of a loop-carried dependence is the index of the leftmost non- = of D(i,j) for the dependence. D(i,j) = (=,=,<) for all dependencies for(int i = 1; i<10; i++) for(int j = 1; j<10; j++) for(int k = 1; k<10; k++) S1: A[i][j][k+1] = A[i][j][k]; Dependencies level = 3

Loop Independent Dependencies Loop Independent Dependencies Statement S2 has a loop-independent dependence on statement S1 if and only if there exist two iteration vectors i and j such that: (1)Statement S1 refers to memory location M on iteration i, S2 refers to M on iteration j, and i = j. (2) There is a control flow path from S1 to S2 within the iteration. for(int i=0;i<N;i++){ S1: t = a[i]; S2: a[i] = b[i]; S3: b[i] = t; }

General Condition for Loop Dependency General Condition for Loop Dependency Let and be iteration vectors within the iteration space of the following loop nest for(int i1 = L1; i1<=U1; i1+=S1) for(int i2 = L2; i2<=U2; i2+=S2) ... for(int in = Ln; in<=Un; in+=Sn) S1: A(f1(i1,...,in),...,fm(i1,...,in)) = ... S2 ... = A(g1(i1,...,in),...,gm(i1,...,in)) } ... } } A dependence exists from S1 to S2 if and only if there exist values of and such that (1) is lexicographically less than or equal to and (2) the following system of dependence equations is satisfied: fi( ) = gi( ) for all i, 1 i m