Data Dependencies in Nested Loops
D
e
p
e
n
d
e
n
c
y
A
n
a
l
y
s
i
s
R
e
c
a
p
•
Program Equivalence
•
Data dependencies across loop iterations
D
a
t
a
D
e
p
e
n
d
e
n
c
i
e
s
i
n
N
e
s
t
e
d
L
o
o
p
Iteration Number
loop index: I
Lower and Upper Bound: L and U
Step size: S
iteration number i = (I – L+1) / S
Example:
L=1; U=10; S=2;
for(int I=L; I<=U; I+=S) { …
}
Suppose, L= 1, U = 10, I = 7, S =2
i = (7 –1 +1)/2 = 4
D
a
t
a
D
e
p
e
n
d
e
n
c
i
e
s
i
n
N
e
s
t
e
d
L
o
o
p
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
, i
2
, …, i
n
} 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
- 2
nd
iteration of the
1
-loop and
- 1
st
iteration of the
2
-loop
D
a
t
a
D
e
p
e
n
d
e
n
c
i
e
s
i
n
N
e
s
t
e
d
L
o
o
p
Iteration Space
All possible iteration vectors
Example:
for(int i=1;i<=2;i++) { // 1
for (int j=1;j<=2;j++) { // 2
S;
}
}
{(1,1), (1,2), (2,1), (2,2)}D
a
t
a
D
e
p
e
n
d
e
n
c
i
e
s
i
n
N
e
s
t
e
d
L
o
o
p
i
k
is the
k
th element of the vector
i
i
[1:
k
] is a
k
-vector consisting of the
leftmost
k
elements of
i
Iteration
i
precedes
iteration
j
,
denoted
i
<
j
, if and only if
1)
i
[1:
n
-1] <
j
[1:
n
-1] or
2)
i
[1:
n
-1] =
j
[1:
n
-1] and
i
n
<
j
n
i
=
(2,1)
i
1
= 2, i
2
= 1
i
[1:2]
=
(2,1)
Given
i
=
(2,1) and
j
=
(2,2)
i
<
j
(2,1) < (2,2)
D
e
p
e
n
d
e
n
c
e
i
n
L
o
o
p
N
e
s
t
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.
D
e
p
e
n
d
e
n
c
e
i
n
L
o
o
p
N
e
s
t
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
S1
S2
S3
j=1
j=1
j=2
j=2
D
i
s
t
a
n
c
e
V
e
c
t
o
r
If there is a dependence from
S
1
on iteration
i
to
S
2
on iteration
j
;
then the
dependence distance vector
d
(
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)
D
i
r
e
c
t
i
o
n
V
e
c
t
o
r
If there is a dependence from
S
1
on iteration
i
and
S
2
on iteration
j
;
then the
dependence direction vector
D
(
i
,
j
) is defined as
D
(
i
,
j
)
k
=
“<” if
d
(
i
,
j
)
k
> 0
“=” if
d
(
i
,
j
)
k
= 0
“>” if
d
(
i
,
j
)
k
< 0
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
) = (<, =, >)
D
i
r
e
c
t
i
o
n
V
e
c
t
o
r
a
n
d
D
e
p
e
n
d
e
n
c
i
e
s
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
) = (<, =, >)
There is a data dependence
A dependence cannot exist if it has a direction vector
such that the leftmost non-“=” component is not “<”
D
i
r
e
c
t
i
o
n
V
e
c
t
o
r
a
n
d
D
e
p
e
n
d
e
n
c
i
e
s
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;
}
}
}
Any anti-dependence?
i
= (2,2,2) reads a[2][2][2]
j
= (1,2,3) writes a[2][2][2]
d(
i
,
j
) =
j – i
= (-1,0,1)
D(
i
,
j
) = (>, =, <)
No anti-dependence
A dependence cannot exist if it has a direction vector
such that the leftmost non-“=” component is not “<”
L
o
o
p
-
c
a
r
r
i
e
d
D
e
p
e
n
d
e
n
c
e
s
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.
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];
D
(
i
,
j
) = (=,=,<) for all dependencies
Dependencies level = 3
L
o
o
p
I
n
d
e
p
e
n
d
e
n
t
D
e
p
e
n
d
e
n
c
i
e
s
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;
}
G
e
n
e
r
a
l
C
o
n
d
i
t
i
o
n
f
o
r
L
o
o
p
D
e
p
e
n
d
e
n
c
y
Let α and β be iteration vectors within the iteration space of the following loop nest
for(int
i1 = L1
;
i1<=
U1
;
i1+=
S1
)
for(int
i
2
= L
2;
i2<=
U
2;
i2+=
S
2)
...
for(int
i
n
= L
n;
in<=
U
n;
in+=
S
n)
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
R
e
f
e
r
e
n
c
e
s
Chapter 2
Optimizing compilers for modern architectures
a dependence-based approach
by Randy Allen, Ken Kennedy
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.
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
References References Chapter 2 Optimizing compilers for modern architectures a dependence-based approach by Randy Allen, Ken Kennedy
