This homework covers initial part of chapters 3.
1. if (a>c) {
2. d = d + 5;
3. a = b + d + e;
} else {
4. e = e + 2;
5. f = f + 2;
6. c = c + f;
}
7. b = a + f;
a) Based on the control dependencies, 2, 3, 4, 5,
and 6 depends 1.
Based on the data references:
1 before 3, 6
2 before 3
3 before 4, 7
5 before 6, 7
and hence 1 must be executed before
3, 6, 4, 7 by transitive analysis.
5 should only be executed conditional
on 1 (control reference) but
before 7
and therefore only 2 can be shifted
before the if statement.
Note, 2 can be moved because d doesn't live after
this segment.
b) 3 depends on 2
6 depends on 5
7 depends on 3 and 5
For static schedule in which we can use the data dependencies
to avoid
data hazards.
issue order
1
then either stream of:
2 | 4 and 5
then 3 | 6 and 7
then 7 |
For dynamic schedule, the data hazard are resolve for
us by the hardware.
So we only need to worry about the control hazard.
issue order
1
then either stream of
2, 3, and 7 | 4, 5, 6, and 7
If we shifted 2 before 1 then for static:
issue order
1, 2
then either stream of:
3 | 4 and 5
then 7 | 6 and 7
Dynamic:
issue order
1, 2
then either stream of
3, and 7 | 4, 5, 6, and 7
c) line 4 could be deleted from the code segment because
the value of e
does not live beyond the code segment and the value is
not used later.
d) The ILP would decrease as there would be less parallel
execution but
the code would be no less effective. Using ILP
as a measure is only
useful if it can be guaranteed that the parallelism is
not of
unnecessary instructions. Also a more efficient
compiler could sometimes
compensate for lack of hardware parallelism.