CA 714CA - Homework #5

Homework 5 is due  4/10/02.

This homework covers initial part of chapters 3.

3.1

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.