Dependency in Program Transformations
D
e
p
e
n
d
e
n
c
y
R
e
c
a
p
•
Reduction
•
Data dependencies
•
Data dependencies across loop iterations
S1: a=X;
if(a==1)
S2: b=Y;
O
t
h
e
r
D
e
p
e
n
d
e
n
c
i
e
s
•
Control dependency
S1: a=X;
if(a==1)
S2: b=Y;
•
Address dependency
S1: a=X;
S2: b=Y[a];
Transformation Correctness
Program Equivalence
(1) program P is transformed to P’
(2) Program P and P’ are equivalent.
The transformation is correct.
correct transformation is semantics preserving
Given same input, if two computations produce identical values for output
variables on the same inputs then the computations are equivalent.
C
o
r
r
e
c
t
n
e
s
s
o
f
D
e
p
e
n
d
e
n
c
e
-
B
a
s
e
d
T
r
a
n
s
f
o
r
m
a
t
i
o
n
s
Reordering transformations: S1;S2; --> S2;S1;
Reordering transformation and dependencies
A
reordering transformation
changes the order of execution of the code,
without adding or deleting any executions of any statements.
A reordering transformation
preserves
a dependence if it preserves the relative
execution order of the source and sink of that dependence.
C
o
r
r
e
c
t
o
f
R
e
o
r
d
e
r
i
n
g
T
r
a
n
s
f
o
r
m
a
t
i
o
n
Any reordering transformation that preserves every dependence in
a program preserves the meaning of that program.
C
o
r
r
e
c
t
o
f
R
e
o
r
d
e
r
i
n
g
T
r
a
n
s
f
o
r
m
a
t
i
o
n
Any reordering transformation that preserves every dependence in
a program preserves the meaning of that program.
Is the following correct?
a=X; Y=a*0;
Y=a*0; a=X;
Y=0; a=X;
T
r
u
e
a
n
d
F
a
l
s
e
D
e
p
e
n
d
e
n
c
e
True dependence:
dependence cannot be removed
a=X; Y=a;
False dependence:
dependence can be removed
a=X; Y=a*0;
Data dependence analysis is undecidable in general
We will not remove false dependence (for now at least)
S
u
b
t
l
e
Q
u
e
s
t
i
o
n
s
How to reason about
-
Side effect
-
Crash/failure
-
Non-termination
We will not cover these issues in this course.
If (Interested) goto
https://compcert.org/motivations.html
Given same input, if two computations produce identical values for output
variables on the same inputs then the computations are equivalent.
D
e
p
e
n
d
e
n
c
i
e
s
a
c
r
o
s
s
M
u
l
t
i
-
D
i
m
e
n
s
i
o
n
a
l
A
c
c
e
s
s
e
s
Identifying dependencies across iterations is a challenge
Identifying dependencies are not immediate
for(int p=0;p<N;p++){ for(int q=0;q<M;q++){S1: a[p,q+1] = a[p,q];
}
}
D
e
p
e
n
d
e
n
c
i
e
s
a
c
r
o
s
s
M
u
l
t
i
-
D
i
m
e
n
s
i
o
n
a
l
A
c
c
e
s
s
e
s
Identifying dependencies across iterations is a challenge
Identifying dependencies are not immediate
for(int p=0;p<N;p++){ for(int q=0;q<M;q++){S1: a[p,q+1] = a[p,q];
}
}
a[0][0]
a[0][1]
a[0][2]
a[1][0]
a[1][1]
a[1][2]
a[2][0]
a[2][1]
a[2][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 p=0;i<N;p++){ for(int q=0;q<M;q++){S1: a[p,q+1] = a[p,q];
}
}
a[0][0]
a[0][1]
a[0][2]
a[1][0]
a[1][1]
a[1][2]
a[2][0]
a[2][1]
a[2][2]
i
= (0,0) and
j
= (0,1): d(
i
,
j
) =
j – i
= (0,1)
i
= (1,0) and
j
= (1,1): d(
i
,
j
) = (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
i
= (0,0) and
j
= (0,1): d(
i
,
j
) = (0,1) => D(i,j) = (=,<)
i
= (1,0) and
j
= (1,1): d(
i
,
j
) = (0,1) => D(i,j) = (=,<)
…..
A
n
o
t
h
e
r
E
x
a
m
p
l
e
for(int i = 0; i<N; i++)
for(int j = 0; j<M; j++)
for(int k = 0; k<L; k++)
A[i+1][j+1][k] = A[i][j][k] + A[i][j+1][k+1]
}
}
}
Direction matrices: (<, <, =), (<, =, >)
R
e
f
e
r
e
n
c
e
s
Chapter 2.2.3, 2.2.4
Optimizing compilers for modern architectures
a dependence-based approach
by Randy Allen, Ken Kennedy
Uncover the intricacies of dependencies in program transformations, exploring the preservation of correctness and the impact of reordering transformations. Discover the nuances of true and false dependencies, and delve into the undecidability of data dependence analysis.
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 Dependency
Recap Recap Reduction Data dependencies Data dependencies across loop iterations S1: a=X; if(a==1) S2: b=Y;
Other Dependencies Other Dependencies Control dependency Address dependency S1: a=X; if(a==1) S2: b=Y; S1: a=X; S2: b=Y[a];
Transformation Correctness Program Equivalence Given same input, if two computations produce identical values for output variables on the same inputs then the computations are equivalent. (1) program P is transformed to P (2) Program P and P are equivalent. The transformation is correct. correct transformation is semantics preserving
Correctness of Dependence Correctness of Dependence- -Based Transformations Based Transformations Reordering transformations: S1;S2; --> S2;S1; A reordering transformation changes the order of execution of the code, without adding or deleting any executions of any statements. Reordering transformation and dependencies A reordering transformation preserves a dependence if it preserves the relative execution order of the source and sink of that dependence.
Correct of Reordering Transformation Correct of Reordering Transformation Any reordering transformation that preserves every dependence in a program preserves the meaning of that program.
Correct of Reordering Transformation Correct of Reordering Transformation Any reordering transformation that preserves every dependence in a program preserves the meaning of that program. Is the following correct? a=X; Y=a*0; Y=a*0; a=X; Y=0; a=X;
True and False Dependence True and False Dependence True dependence: dependence cannot be removed a=X; Y=a; False dependence: dependence can be removed a=X; Y=a*0; Data dependence analysis is undecidable in general We will not remove false dependence (for now at least)
Subtle Questions Subtle Questions Given same input, if two computations produce identical values for output variables on the same inputs then the computations are equivalent. How to reason about - Side effect - Crash/failure - Non-termination We will not cover these issues in this course. If (Interested) goto https://compcert.org/motivations.html
Dependencies across Multi Dependencies across Multi- -Dimensional Accesses Dimensional Accesses Identifying dependencies across iterations is a challenge Identifying dependencies are not immediate for(int p=0;p<N;p++){ for(int q=0;q<M;q++){ S1: a[p,q+1] = a[p,q]; } }
Dependencies across Multi Dependencies across Multi- -Dimensional Accesses Dimensional Accesses Identifying dependencies across iterations is a challenge Identifying dependencies are not immediate a[0][0] a[0][1] a[0][2] for(int p=0;p<N;p++){ for(int q=0;q<M;q++){ S1: a[p,q+1] = a[p,q]; } } a[1][0] a[1][1] a[1][2] a[2][0] a[2][1] a[2][2]
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 a[0][0] a[0][1] a[0][2] for(int p=0;i<N;p++){ for(int q=0;q<M;q++){ S1: a[p,q+1] = a[p,q]; } } a[1][0] a[1][1] a[1][2] a[2][0] a[2][1] a[2][2] i = (0,0) and j = (0,1): d(i,j) = j i = (0,1) i = (1,0) and j = (1,1): d(i,j) = (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 = i = (0,0) and j = (0,1): d(i,j) = (0,1) => D(i,j) = (=,<) i = (1,0) and j = (1,1): d(i,j) = (0,1) => D(i,j) = (=,<) ..
Another Example Another Example for(int i = 0; i<N; i++) for(int j = 0; j<M; j++) for(int k = 0; k<L; k++) A[i+1][j+1][k] = A[i][j][k] + A[i][j+1][k+1] } } } Direction matrices: (<, <, =), (<, =, >)
References References Chapter 2.2.3, 2.2.4 Optimizing compilers for modern architectures a dependence-based approach by Randy Allen, Ken Kennedy
