pdf questions attached

Advanced Computer Architecture- 06CS81- Unit 8
Loop Level Parallelism- Detection and Enhancement
Static Exploitation of ILP
•Use compiler support for increasing parallelism
–Supported by hardware
•Techniques for eliminating some types of dependences
–Applied at compile time (no run time support)
•Finding parallelism
•Reducing control and data dependencies
•Using speculation
Unrolling Loops – High-level
–for (i=1000; i>0; i=i-1)
x[i] = x[i] + s;
–C equivalent of unrolling to block four iterations into one:
–for (i=250; i>0; i=i-1)
{
x[4*i] = x[4*i] + s;
x[4*i-1] = x[4*i-1] + s;
x[4*i-2] = x[4*i-2] + s;
x[4*i-3] = x[4*i-3] + s;
}
Enhancing Loop-Level Parallelism
•Consider the previous running example:
–for (i=1000; i>0; i=i-1)
x[i] = x[i] + s;
–there is no loop-carried dependence – where data used in a later iteration depends on
data produced in an earlier one
–in other words, all iterations could (conceptually) be executed in parallel
•Contrast with the following loop:
–for (i=1; i<=100; i=i+1) {
A[i+1] = A[i] + C[i]; /* S1 */
B[i+1] = B[i] + A[i+1]; /* S2 */
}
–what are the dependences?
A Loop with Dependences
•For the loop:
–for (i=1; i<=100; i=i+1) {
A[i+1] = A[i] + C[i];
/* S1 */
B[i+1] = B[i] + A[i+1]; /* S2 */
}
–what are the dependences?
•There are two different dependences:
–loop-carried: (prevents parallel operation of iterations)
•S1 computes A[i+1] using value of A[i] computed in previous iteration
•S2 computes B[i+1] using value of B[i] computed in previous iteration
–not loop-carried: (parallel operation of iterations is ok)
•S2 uses the value A[i+1] computed by S1 in the same iteration
•The loop-carried dependences in this case force successive iterations of the loop to
execute in series. Why?
–S1 of iteration i depends on S1 of iteration i-1 which in turn depends on …, etc.

Another Loop with Dependences
•Generally, loop-carried dependences hinder ILP
–if there are no loop-carried dependences all iterations could be executed in parallel
–even if there are loop-carried dependences it may be possible to parallelize the loop – an
analysis of the dependences is required…
•For the loop:
–for (i=1; i<=100; i=i+1) {
A[i] = A[i] + B[i]; /* S1 */
B[i+1] = C[i] + D[i]; /* S2 */
}
–what are the dependences?
•There is one loop-carried dependence:
–S1 uses the value of B[i] computed in a previous iteration by S2
–but this does not force iterations to execute in series. Why…?
–…because S1 of iteration i depends on S2 of iteration i-1…, and the chain of
dependences stops here!
Parallelizing Loops with Short Chains of Dependences
•Parallelize the loop:
–for

(i=1; i<=100; i=i+1) {
B[i+1] = C[i] + D[i]; /* S2 */
•Parallelized code:
–A[1] = A[1] + B[1];
for (i=1; i<=99; i=i+1)
{
B[i+1] = C[i] + D[i];
A[i+1] = A[i+1] + B[i+1];
}
B[101] = C[100] + D[100];

A[i] = A[i] + B[i];

/* S1 */

}

–the

dependence between the two statements in the loop is no longer loop-carried and
iterations of the loop may be executed in parallel
–

Loop-Carried Dependence Detection: affine array index: a x i+b
To detect loop-carried dependence in a loop, the Greatest Common Divisor (GCD) test
can be used by the compiler, which is based on the following:
If an array element with index: a x i + b is stored and element:
c x i + d of
the same array is loaded later where index runs from m to n, a dependence exists if
the following two conditions hold:
1.There are two iteration indices, j and k , m <= j , k <= n
(within iteration limits)
2.The loop stores into an array element indexed by:
a x j +b
and later loads from the same array the element indexed by:
c x k + d
Thus:
a x j + b = c x k + d

The Greatest Common Divisor (GCD) Test
If a loop carried dependence exists, then :
GCD(c, a) must divide (d-b)
The GCD test is sufficient to guarantee no loop carried dependence
However there are cases where GCD test succeeds but no dependence exits because GCD
test does not take loop bounds into account
Example:
for (i=1; i<=100; i=i+1) {
x[2*i+3] = x[2*i] * 5.0;
}
a=2 b=3
c=2
d=0
GCD(a, c) = 2
d - b = -3
2 does not divide -3
No loop carried dependence possible.
Example- Loop Iterations to be Independent
Finding multiple types of dependences
for (i=1; i<=100; i=i+1) {
Y[i] = X[i] / c; /* S1 */
X[i] = X[i] + c; /* S2 */
Z[i] = Y[i] + c; /* S3 */
Y[i] = c - Y[i]; /* S4 */ }
Answer The following dependences exist among the four statements:
1. There are true dependences from S1 to S3 and from S1 to S4 because of Y[i]. These
are not loop carried, so they do not prevent the loop from being considered parallel.
These dependences will force S3 and S4 to wait for S1 to complete.
2. There is an antidependence from S1 to S2, based on X[i].
3. There is an antidependence from S3 to S4 for Y[i].
4. There is an output dependence from S1 to S4, based on Y[i].
Eliminating false dependencies
The following version of the loop eliminates these false (or pseudo) dependences.
for (i=1; i<=100; i=i+1 {
/* Y renamed to T to remove output dependence */
T[i] = X[i] / c;
/* X renamed to X1 to remove antidependence */
X1[i] = X[i] + c;
/* Y renamed to T to remove antidependence */
Z[i] = T[i] + c;
Y[i] = c - T[i];
}
Drawback of dependence analysis
•When objects are referenced via pointers rather than array indices (but see discussion
below)

• When array indexing is indirect through another array, which happens with many
representations of sparse arrays
• When a dependence may exist for some value of the inputs, but does not exist in
actuality when the code is run since the inputs never take on those values
• When an optimization depends on knowing more than just the possibility of a
dependence, but needs to know on which write of a variable does a read of that variable
depend
Points-to analysis
Relies on information from three major sources:
1. Type information, which restricts what a pointer can point to.
2. Information derived when an object is allocated or when the address of an object is
taken, which can be used to restrict what a pointer can point to. For example, if p always
points to an object allocated in a given source line and q never points to that object, then
p and q can never point to the same object.
3. Information derived from pointer assignments. For example, if p may be assigned the
value of q, then p may point to anything q points to.
Eliminating dependent
computations
copy propagation, used to simplify sequences like the following:
DADDUI R1,R2,#4
DADDUI R1,R1,#4
to
DADDUI R1,R2,#8

Tree height reduction
•they reduce the height of the tree structure representing a computation, making it wider
but shorter.
Recurrence
Recurrences are expressions whose value on one iteration is given by a function that
depends onthe previous iterations.
sum = sum + x;
sum = sum + x1 + x2 + x3 + x4 + x5;
If unoptimized requires five dependent operations, but it can be rewritten as
sum = ((sum + x1) + (x2 + x3)) + (x4 + x5);
evaluated in only three dependent operations.

Scheduling and Structuring Code for Parallelism
Static Exploitation of ILP
•Use compiler support for increasing parallelism

–Supported by hardware

•Techniques for eliminating some types of dependences
–Applied at compile time (no run time support)
•Finding parallelism
•Reducing control and data dependencies
•Using speculation
Techniques to increase the amount of ILP
•For processor issuing more than one instruction on every clock cycle.
–Loop unrolling,
–software pipelining,
–trace scheduling, and
–superblock scheduling

Software pipelining
•Symbolic loop unrolling
•Benefits of loop unrolling with reduced code size
•Instructions in loop body selected from different loop iterations
•Increase distance between dependent instructions in
Software pipelined loop
Loop: SD
F4,16(R1)
#store to v[i]
ADDD
F4,F0,F2
#add to v[i-1]
LD
F0,0(R1)
#load v[i-2]
ADDI R1,R1,-8
BNE
R1,R2,Loop
5 cycles/iteration (with dynamic scheduling and renaming)
Need startup/cleanup code

Software pipelining
(cont.)

SW pipelining example
Iteration i:
L.D

Iteration i+1: L.D

Iteration i+2: L.D

F0,0(R1)
ADD.D
F4,F0,F2
S.D
F4,0(R1)
F0,0(R1)
ADD.D
F4,F0,F2
S.D
F4,0(R1)
F0,0(R1)
ADD.D
F4,F0,F2
S.D
F4,0(R1)

SW pipelined loop with startup and cleanup code
#startup, assume i runs from 0 to n
R1,R1-16
#point to v[n-2]
F0,16(R1)
#load v[n]
F4,F0,F2
#add v[n]
F0,8(R1)
#load v[n-1]
#body for (i=2;i<=n-2;i++)
Loop: SD
F4,16(R1)
#store to v[i]
ADDD
F4,F0,F2
#add to v[i-1]
LD
F0,0(R1)
#load v[i-2]
ADDI
R1,R1,-8
BNE
R1,R2,Loop
#cleanup
SD
F4,8(R1)
#store v[1]
ADDD
F4,F0,F2
#add v[0]
SD
F4,0(R1)
#store v[0]
Software pipelining versus unrolling
ADDI
LD
ADDD
LD

•Performance effects of SW pipelining vs. unrolling
–Unrolling reduces loop overhead per iteration

–SW pipelining reduces startup-cleanup pipeline overhead
Software pipelining versus unrolling (cont.)
Software pipelining
(cont.)

Advantages
•Less code space than conventional unrolling
•Loop runs at peak speed during steady state
•Overhead only at loop initiation and termination
•Complements unrolling
Disadvantages
•Hard to overlap long latencies
•Unrolling combined with SW pipelining
•Requires advanced compiler transformations
Global Code Scheduling
•Global code scheduling aims to compact a code fragment with internal control structure
into the shortest possible sequence that preserves the data and control dependences.

Global code scheduling

•aims to compact a code fragment with internal control
–structure into the shortest possible sequence
–that preserves the data and control dependences
•Data dependences are overcome by unrolling
•In the case of memory operations, using dependence analysis to determine if two
references refer to the same address.
•Finding the shortest possible sequence of dependent instructions- critical path
•Reduce the effect of control dependences arising from conditional nonloop branches by
moving code.
•Since moving code across branches will often affect the frequency of execution of such
code, effectively using global code motion requires estimates of the relative frequency of
different paths.
•if the frequency information is accurate, is likely to lead to faster code.
Global code scheduling- cont.
•Global code motion is important since many inner loops contain conditio