Chapter: Compilers : Principles, Techniques, & Tools : Optimizing for Parallelism and Locality
Finding Synchronization-Free Parallelism
Finding Synchronization-Free Parallelism
1 An Introductory Example
2 Affine Space Partitions
3 Space-Partition Constraints
4 Solving Space-Partition
Constraints
5 A Simple Code-Generation
Algorithm
6 Eliminating Empty Iterations
7 Eliminating Tests from
Innermost Loops
8 Source-Code Transforms
9 Exercises for Section 11.7
Having developed the theory of affine array accesses, their reuse
of data, and the dependences among them, we shall now begin to apply this
theory to paral-lelization and optimization of real programs. As discussed in
Section 11.1.4, it is important that we find parallelism while minimizing
communication among processors. Let us start by studying the problem of
parallelizing an application without allowing any communication or synchronization
between processors at all. This constraint may appear to be a purely academic
exercise; how often can we find programs and routines that have such a form of
parallelism? In fact, many such programs exist in real life, and the algorithm
for solving this problem is useful in its own right. In addition, the concepts
used to solve this problem can be extended to handle synchronization and
communication.
1. An Introductory Example
Shown in Fig. 11.23
is an excerpt of a C translation (with Fortran-style array accesses retained
for clarity) from a 5000-line Fortran multigrid algorithm to solve
three-dimensional Euler equations. The
program spends most its time in a small number of routines like the one shown
in the figure. It is typical of many numerical programs. These often consist of
numerous for-loops, with different nesting levels, and they have many array
accesses, all of which are affine expressions of surrounding loop indexes. To
keep the example short, we have elided lines from the original program with
similar characteristics.
The code of Fig. 11.23 operates on the scalar variable T
and a number of different arrays with different dimensions. Let us first
examine the use of variable T. Because each iteration in the loop uses
the same variable T, we cannot execute the iterations in parallel.
However, T is used only as a way to hold a common subexpression used
twice in the same iteration. In the first two of the three loop nests in Fig.
11.23, each iteration of the innermost loop writes a value into T and uses the
value immediately after twice, in the same iteration. We can eliminate the
dependences by replacing each use of T by the right-hand-side expression
in the previous assignment of T, without changing the semantics of the
program. Or, we can replace the scalar T by an array. We then have each
iteration use its own array element T[j, i].
With this
modification, the computation of an array element in each as-signment statement
depends only on other array elements with the same values for the last two
components (j and i, respectively). We can thus group all
operations that operate on the (j,i)th element of all arrays into
one computa-tion unit, and execute them in the original sequential order. This
modification produces ( j l — 1) x ( i l — 1) units of computation that are all
independent of one another. Notice that second and third nests in the source
program involve a third loop, with index k. However, because there is no
dependence between dynamic accesses with the same values for j and «, we
can safely perform the loops on k inside the loops on j and i
— that is, within a computation unit.
Knowing that these computation units are independent enables a
number of legal transforms on this code. For example, instead of executing the
code as originally written, a uniprocessor can perform the same computation by
execut-ing the units of independent operation one unit at a time. The resulting
code, shown in Fig. 11.24, has improved temporal locality, because results
produced are consumed immediately.
The independent units
of computation can also be assigned to different processors and executed in
parallel, without requiring any synchronization or communication. Since there
are ( j l — 1) x ( i l — 1) independent units of com putation, we can utilize at most ( j l - 1) x ( i
l - 1) processors. By organizing the processors as if they were in a
2-dimensional array, with ID's where 2
< j < jl
and 2 <
i < i l , the
SPMD program to be executed by
each processor is simply the body in the inner loop in Fig. 11.24.
The above example illustrates the basic approach to finding
synchronization-free parallelism. We first split the computation into as many
independent units as possible. This partitioning exposes the scheduling choices
available. We then assign computation units to the processors, depending on the
number of processors we have. Finally, we generate an SPMD program that is
executed on each processor.
2. Affine Space Partitions
A loop nest is said
to have k degrees of parallelism if it has, within the nest, k
parallelizable loops — that is, loops such that there are no data dependencies
between different iterations of the loops. For example, the code in Fig. 11.24 has 2 degrees of parallelism. It is convenient to
assign the operations in a com-putation with k degrees of parallelism to
a processor array with k dimensions.
We shall assume initially that each dimension of the processor array has as many
processors as there are iterations of the corresponding loop. After all the independent computation units have been found, we shall
map these "virtual" processors to the actual processors. In practice,
each processor should be responsible for a fairly large number of iterations,
because otherwise there is not enough work to amortize away the overhead of
parallelization.
We break down the
program to be parallelized into elementary statements, such as 3-address statements. For each statement, we find an affine
space partition that maps each dynamic instance of the statement, as
identified by its loop indexes, to a processor ID.
Example 1 1 . 4 0 :
As discussed above, the code of Fig. 11.23 has two degrees of parallelism. We
view the processor array as a 2-dimensional space. Let (pi,P2) be the ID of a
processor in the array. The parallelization scheme discussed in Section 11.7.1
can be described by simple affine partition functions. All the statements in
the first loop nest have this same affine partition:
All the statements in
the second and third loop nests have the following same affine partition:
The algorithm to find
synchronization-free parallelism consists of three steps:
1.
Find, for each
statement in the program, an affine partition that maxi-mizes the degree of
parallelism. Note that we generally treat the state-ment, rather than the
single access, as the unit of computation. The same affine partition must apply
to each access in the statement. This grouping of accesses makes sense, since
there is almost always dependence among accesses of the same statement anyway.
2.
Assign the
resulting independent computation units among the processors, and choose an
interleaving of the steps on each processor. This assignment is driven by
locality considerations.
3.
Generate an
SPMD program to be executed on each processor.
We shall discuss next how to find the affine partition functions,
how to gen-erate a sequential program that executes the partitions serially,
and how to generate an SPMD program that executes each partition on a different
pro-cessor. After we discuss how parallelism with synchronizations is handled
in Sections 11.8 through 11.9.9, we return to Step 2 above in Section 11.10 and
discuss the optimization of locality for uniprocessors and multiprocessors.
3. Space-Partition Constraints
To require no communication, each pair of operations that share a
data depen-dence must be assigned to the same processor. We refer to these
constraints as "space-partition constraints." Any mapping that
satisfies these constraints cre-ates partitions that are independent of one
another. Note that such constraints can be satisfied by putting all the
operations in a single partition. Unfortu-nately, that "solution"
does not yield any parallelism. Our goal is to create as many independent
partitions as possible while satisfying the space-partition constraints; that
is, operations are not placed on the same processor unless it is necessary.
When we restrict ourselves to affine partitions, then instead of
maximizing the number of independent units, we may maximize the degree (number
of dimensions) of parallelism. It is sometimes possible to create more
independent units if we can use piecewise affine partitions. A piecewise
affine partition divides instances of a single access into, different sets and
allows a different affine partition for each set. However, we shall not
consider such an option here.
Formally, an affine
partition of a program is
synchronization free if and only if for every two (not necessarily
distinct) accesses sharing a dependence, T1
= ( F 1 , f 1 , B 1 , b 1 ) in statement s1 nested in d1 loops, and T2 = ( F 2 , f y , B 2 , b 2 ) in
statement s2 nested in d2 loops, the partitions ( C 1 , c 1 ) and ( C
2 , c 2 ) for statements si and s 2 , respectively, satisfy the following
space-partition constraints:
The goal of the parallelization algorithm is to find, for each
statement, the partition with the highest rank that satisfies these
constraints.
Shown in Fig. 11.25 is a diagram illustrating the essence of the
space-partition constraints. Suppose there are two static accesses in two loop
nests with index vectors ii and i 2 . These accesses are dependent in the
sense that they access at least one array element in common, and at least one
of them is a write. The figure shows particular dynamic accesses in the two
loops that hap pen to access
the same array element, according to the affine access functions Fiii + fi and
F 2 i 2 +f 2 . Synchronization is
necessary unless the affine partitions for the two static accesses, C i i i +
c i and C 2 i 2 + c 2 , assign the dynamic accesses to the same
processor.
If we choose an affine partition whose rank is the maximum of the
ranks of all statements, we get the maximum possible parallelism. However,
under this partitioning some processors may be idle at times, while other
processors are executing statements whose affine partitions have a smaller
rank. This situation may be acceptable if the time taken to execute those
statements is relatively short. Otherwise, we can choose an affine partition
whose rank is smaller than the maximum possible, as long as that rank is
greater than 0.
We show in Example
11.41 a small program designed to illustrate the power of the technique. Real
applications are usually much simpler than this, but may have boundary
conditions resembling some of the issues shown here. We shall use this example
throughout this chapter to illustrate that programs with
affine accesses have relatively simple space-partition
constraints, that these con-straints can be solved using standard linear
algebra techniques, and that the desired SPMD program can be generated
mechanically from the affine parti-tions.
Example 1 1 . 4 1 :
This example shows how we formulate the space-partition constraints for the
program consisting of the small loop nest with two state-ments, si and s2, shown in Figure 11.26.
We show the data dependences in the program in Figure 1L27. That is, each black dot represents an instance of statement Si,
and each white dot represents a n instance o f statement S 2 . The dot
located a t coordinates (i, j ) represents the instance of the statement
that is executed for those values of the loop indexes.
Note, however, that the instance of s2 is located just below the
instance of «i for the same pair, so the vertical scale of j is greater than
the horizontal scale of i.
Notice that X[i,j] is written by si (i, j), that is, by the
instance of statement si with index values i and j. It is later read by s2(i,j
+ 1), so si(i,j) must precede s2(i,j + 1). This observation explains the
vertical arrows from black dots to white dots. Similarly, Y[i,j] is written by
s2(i,j) and later read by s1(i + 1, j). Thus, s2(i,j) must precede si(i + l,j),
which explains the arrows from white dots to black.
It is easy to see from this diagram that this code can be
parallelized without synchronization by assigning each chain of dependent
operations to the same processor. However, it is not easy to write the SPMD
program that implements this mapping scheme. While the loops in the original
program have 100 itera-tions each, there are 200 chains, with half originating
and ending with statement si and the other half originating and ending
with s2. The lengths of the chains vary from 1 to 100 iterations.
Since there are two statements, we are seeking two affine
partitions, one for each statement. We only need to express the space-partition
constraints for one-dimensional affine partitions. These constraints will be
used later by the solution method that tries to find all the independent
one-dimensional affine partitions and combine them to get multidimensional
affine partitions. We can thus represent the affine partition for each
statement by a 1 x 2 matrix and a 1 x 1
vector to translate the vector of indexes into a single processor
number. Let ([C11C12], [ci]), ([C2iC22], [c2 ]), be the one-dimensional affine
partitions for the statements s1 and
s2, respectively. We apply six data
dependence tests:
1. Write access
X[i,j] and itself in
statement si,
2. Write access X[i,j] with read access X[i, j] in
statement si,
3. Write access X[i,j]
in statement si with read access X[i,j — 1] in state-ment 82,
4. Write access ^ [ i
, j] and itself in statement s2,
5. Write access
Y[i,j] with read access Y[i,j] in statement s2,
6. Write access Y[i,
j] in statement s2 with read access Y[i
— l,j] in statement si .
We see that the dependence tests are all simple and highly
repetitive. The only dependences present in this code occur in case (3) between
instances of accesses
j] and X[i,j —
1] and in case (6) between Y[i,j] and Y[i — 1, j ] .
The space-partition
constraints imposed by the data dependence between
X[i,j] in statement si and X[i,j — 1] in statement
s2 can be expressed in the following terms:
For all and such that
1 < i < 100 1 < j < 100
1 < i' < 100 1 < j ' < 100
i = i'
we have
That is, the first
four conditions say that (i,j) and lie within the iteration space of the loop
nest, and the last two conditions say that the dynamic accesses X[i, j] and
X[i,j — 1] touch the same array
element. We can derive the
space-partition constraint for accesses Y[i — in statement s2 and Y[i, j] in
statement si in a similar manner.
4. Solving Space-Partition Constraints
Once the space-partition constraints have been extracted, standard
linear alge-bra techniques can be used to find the affine partitions satisfying
the constraints. Let us first show how we find the solution to Example 11.41.
Example 11 . 42 : We
can find the affine partitions for Example 11.41 with the following steps:
1.
Create the space-partition constraints
shown in Example 11.41. We use the loop bounds in determining the data
dependences, but they are not used in the rest of the algorithm otherwise.
3. The equation above holds for all combinations of
t1 and t2- Thus, it must be that
4.
Find all the independent solutions to
the equations involving only un-knowns in the coefficient matrix, ignoring the
unknowns in the constant vectors in this step. There is only one independent
choice in the coef-
ficient matrix, so
the affine partitions we seek can have at most a rank of one. We keep the
partition as simple as possible by setting Cn — 1. We cannot assign 0 to C11 because that will create a
rank-0 coefficient matrix, which maps all iterations to the same processor. It
then follows that C2i = 1, C22 = - 1, C12 = - 1 .
5. Find the constant
terms. We know that the difference between the constant terms, c2 — ci, must be
— 1 . We get to pick the actual values, however. To keep the partitions simple,
we pick c2 = 0; thus ci = — 1 .
Let p be the ID of the
processor executing iteration In terms of p, the affine partition is
That is, the (i,j)th
iteration of si is assigned to the processor p = i — j — 1, and the (i,j)th
iteration of s2 is assigned to processor p — % — j.
Algorithm 11.43 :
Finding a highest-ranked synchronization-free affine partition for a program.
INPUT : A program with
affine array accesses.
OUTPUT : A partition.
METHOD : Do the following:
1. Find all
data-dependent pairs of accesses in a program for each pair of data-dependent
accesses, T1 — ( F i , f i , B i , b i )
in statement s1 nested in di loops
and T2 = ( F 2 , f 2 , B 2 , b 2
) in statement s2
nested in d2
loops. Let ( C i , c i ) and ( C 2 , c 2 ) represent the (currently
unknown) partitions of statements s1 and
s2, respectively. The space-partition constraints state
for all i1 and i2,
within their respective loop bounds. We shall generalize the domain of
iterations to include all ii in Zdl and i2 in Zd2;
that is, the bounds are all assumed to be minus infinity to infinity. This
assumption makes sense, since an affine partition cannot make use of the fact
that an index variable can take on only a limited set of integer values.
2. For each pair of
dependent accesses, we reduce the number of unknowns in the index vectors.
(a) Note
that Fi + f is the same vector as
That is, by adding an
extra component 1 at the bottom of column-vector i, we can make the
column-vector f be an additional, last column of the matrix F. We may thus
rewrite the equality of the access functions
(b) The above
equations will in general have more than one solution. However, we may still
use Gaussian elimination to solve the equations for the components of ix
and i2 as best we can. That is, eliminate as many variables as
possible until we are left with only variables that cannot be eliminated. The
resulting solution for i2 and i2 will have the form where
U is an upper-triangular matrix and t is a vector of free vari-ables ranging
over all integers.
(c) We may use the
same trick as in Step (2a) to rewrite the equality of the partitions.
Substituting the vector (ii, i2 ,1) with the result
from Step (2b), we can write the constraints on the partitions as
3. Drop the
nonpartition variables. The equations above hold for all combi-nations of t if
Rewrite these
equations in the form Ax = 0, where x is a vector of all the unknown
coefficients of the affine partitions.
4.
Find the rank of the affine partition
and solve for the coefficient matrices. Since the rank of an affine partition
is independent of the value of the constant terms in the partition, we
eliminate all the unknowns that come
from the constant
vectors like ci or c 2 , thus replacing Ax = 0 by sim-plified
constraints A'x' = 0. Find the solutions to A'x' = 0, expressing
them as B, a set of basis vectors spanning the null space of A'.
5.
Find the constant terms. Derive one
row of the desired affine partition from each basis vector in B, and derive the
constant terms using Ax = 0.
Note that Step 3
ignores the constraints imposed by the loop bounds on variables t. The
constraints are only stricter as a result, and the algorithm must therefore be
safe. That is, we place constraints on the C's and c's assuming t is arbitrary. Conceivably, there would be other
solutions for the C's and c's that are
valid only because some values of t are impossible. Not searching for these
other solutions may cause us to miss an optimization, but cannot cause the
program to be changed to a program that does something different from what the
original program does.
5. A Simple Code-Generation Algorithm
Algorithm 11.43 generates affine partitions that split
computations into inde-pendent partitions. Partitions can be assigned
arbitrarily to different proces-sors, since they are independent of one
another. A processor may be assigned more than one partition and can interleave
the execution of its partitions, as long as operations within each partition,
which normally have data dependences, are executed sequentially.
It is relatively easy to generate a correct program given an
affine partition. We first introduce Algorithm 11.45, a simple approach to generating code for a single processor that
executes each of the independent partitions sequentially. Such code optimizes
temporal locality, since array accesses that have several uses are very close
in time. Moreover, the code easily can be turned into an SPMD program that
executes each partition on a different processor. The code generated is,
unfortunately, inefficient; we shall next discuss optimizations to make the
code execute efficiently.
The essential idea is as follows. We are given bounds for the
index variables of a loop nest, and we have determined, in Algorithm 11.43, a partition for the accesses of a particular statement s.
Suppose we wish to generate sequential code that performs the action of each
processor sequentially. We create an outermost loop that iterates through the
processor IDs. That is, each iteration of this loop performs the operations
assigned to a particular processor ID. The original program is inserted as the
loop body of this loop; in addition, a test is added to guard each operation in
the code to ensure that each processor only executes the operations assigned to
it. In this way, we guarantee that the processor executes all the instructions
assigned to it, and does so in the original sequential order.
Example 11.44: Let us generate code that executes the
independent parti-tions in Example 11.41 sequentially. The original sequential program is
from Fig. 11.26 is repeated here as Fig. 11.28.
In Example 11.41, the affine partitioning algorithm found one
degree of parallelism. Thus, the processor space can be represented by a single
variable p. Recall also from that example that we selected an affine
partition that, for all values of index variables i and j
with 1 =< i =< 100 and 1 =< j =< 100, assigned
We can generate the
code in three steps:
1.
For each statement, find all the
processor IDs participating in the com-putation. We combine the constraints 1 =< i =< 100 and 1 =< j =< 100 with one of the equations p = i - j - 1 or p = i - j, and project away i and j to
get the new constraints
2. Find all the processor
IDs participating in any of the statements.
When
we take the union of
these ranges, we get - 1 0 0 =< p =< 99; these bounds
are sufficient to
cover all instances of both statements si and s 2 .
3.
Generate the
code to iterate through the computations in each partition sequentially. The
code, shown in Fig. 11.29, has an outer loop that iterates through all the
partition IDs participating in the computation (line (1)). Each partition goes
through the motion of generating the indexes of all the iterations in the
original sequential program in lines (2) and (3) so that it can pick out the
iterations the processor p is supposed to execute. The tests of lines
(4) and (6) make sure that statements s1 and s2 are executed
only when the processor p would execute them.
The generated code, while correct, is extremely inefficient.
First, even though each processor executes computation from at most 99
iterations, it gen-erates loop indexes for 100 x 100 iterations, an order of
magnitude more than necessary. Second, each addition in the innermost loop is
guarded by a test, creating another constant factor of overhead. These two
kinds of inefficiencies are dealt with in Sections 11.7.6 and 11.7.7,
respectively. •
Although the code of Fig. 11.29 appears designed to execute on a
unipro-cessor, we could take the inner loops, lines (2) through (8), and
execute them on 200 different processors, each of which had a different value
for p, from —100 to 99. Or, we could partition the responsibility for the
inner loops among any number of processors less than 200, as long as we
arranged that each processor knew what values of p it was responsible for and
executed lines (2) through (8) for just those values of p.
Algorithm 11.45 : Generating code that executes partitions of a
program sequentially.
INPUT : A program P with affine array accesses. Each statement s
in the program has associated bounds of the form B s i + bs > 0, where i is
the vector of loop indexes for the loop nest in which statement s appears.
Also associated with statement s is a partition C 5 i + cs = p
where p is an m-dimensional vector of variables representing a processor
ID; m is the maximum, over all statements in program P, of the
rank of the partition for that statement.
OUTPUT : A program equivalent to P but iterating over the
processor space over loop rather than indexes.
M E T H O D : Do the following:
1.
For each
statement, use Fourier-Motzkin elimination to project out all the loop index
variables from the bounds.
2.
Use Algorithm 11.13
to determine bounds on the partition ID's.
3. Generate loops, one for each of the m
dimensions of processor space. Let
p = [pi,P2, -- -
,Pm] be the vector of variables for these loops; that is, there is one
variable for each dimension of the processor space. Each loop variable pi
ranges over the union of the partition spaces for all statements in the program
P.
Note that the union of the partition spaces is not necessarily
convex. To keep the algorithm simple, instead of enumerating only those partitions
that
have a nonempty
computation to perform, set the lower
bound of each pi to
the minimum of all the lower bounds imposed by all statements and
the upper bound of each pi to the maximum of all the upper bounds
imposed by all statements. Some values of p may thereby have no
operations.
The code to be executed by each partition is the original
sequential pro-gram. However, every statement is guarded by a predicate so that
only those operations belonging to the partition are executed. •
An example of Algorithm 11.45 will follow shortly. Bear in mind,
however, that we are still far from the optimal code for typical examples.
6. Eliminating Empty Iterations
We now discuss the first of the two transformations necessary to
generate ef-ficient SPMD code. The code executed by each processor cycles
through all the iterations in the original program and picks out the operations
that it is supposed to execute. If the code has k degrees of
parallelism, the effect is that each processor performs k orders of
magnitude more work. The purpose of the first transformation is to tighten the
bounds of the loops to eliminate all the empty iterations.
We begin by considering the statements in the program one at a
time. A statement's iteration space to be executed by each partition is the
original itera-tion space plus the constraint imposed by the affine partition.
We can generate tight bounds for each statement by applying Algorithm 11.13 to
the new iter-ation space; the new index vector is like the original sequential
index vector, with processor ID's added as outermost indexes. Recall that the
algorithm will generate tight bounds for each index in terms of surrounding
loop indexes.
After finding the iteration spaces of the different statements, we
combine them, loop by loop, making the bounds the union of those for each
statement. Some loops end up having a single iteration, as illustrated by
Example 11.46 below, and we can simply eliminate the loop and simply set the
loop index to the value for that iteration.
Example 1 1 . 4 6
: For the loop of Fig. 11.30(a), Algorithm 11.43 will create the
affine partition
Algorithm 11.45 will create the code of Fig. 11.30(b). Applying
Algorithm 11.13 to statement s1 produces the bound: p < i < p,
or simply % = p. Similarly, the algorithm determines j = p
for statement s2- Thus, we get the code of Fig. 11.30(c). Copy propagation of
variables i and j will eliminate the unnec-essary test and
produce the code of Fig. 11.30(d). •
We now return to
Example 11.44 and illustrate the step to merge multiple iteration spaces from different statements together.
Example 11*47:
Let us now tighten the loop bounds of the code in Example 11.44. The
iteration space executed by partition p for statement si is defined by the
following equalities and inequalities:
Applying Algorithm 11.13 to the above creates the
constraints shown in Fig. 11.31(a). Algorithm 11.13 generates the constraint p
+ 2 < i < 100 + p + 1 from i — p - 1 = j and 1 < j < 100, and
tightens the upper bound of p to 98.
Likewise, the bounds for each of the variables for
statement s2 are shown in Fig. 11.31(b).
The iteration spaces
for si and s2 in Fig. 11.31 are similar, but as
ex-pected from Fig. 11.27, certain limits differ by 1 between the two. The code
in Fig. 11.32 executes over this union of iteration spaces. For example, for i
use min(l,£>+1) as the lower bound and max(100,100+ p + 1 ) as the upper
bound. Note that the innermost loop has 2 iterations except that it has only
one the first and last time it is executed. The overhead in generating loop
indexes is thus reduced by an order of magnitude. Since the iteration space
executed is larger than either that of si
and s2, conditionals are still necessary to select when these
statements are executed.
7. Eliminating Tests from Innermost Loops
The second transformation is to remove conditional tests from the
inner loops. As seen from the examples above, conditional tests remain if the
iteration spaces of statements in the loop intersect but not completely. To
avoid the need for conditional tests, we split the iteration space into
subspaces, each of which executes the same set of statements. This optimization
requires code to be duplicated and should only be used to
remove conditionals in the inner loops.
To split an iteration
space to reduce tests in inner loops, we apply the following steps repeatedly
until we remove all the tests in the inner loops:
1. Select a loop that consists of statements with
different bounds.
2.
Split the loop using a condition such
that some statement is excluded from at least one of its components. We choose
the condition from among the boundaries of the overlapping different polyhedra.
If some statement has all its iterations in only one of the half planes of the
condition, then such a condition is useful.
3. Generate code for
each of these iteration spaces separately.
Example 1 1 . 4 8 : Let
us remove the conditionals from the code of Fig. 11.32. Statements si and 52 are mapped to the same set of
partition ID's except for
The code for each
subspace can then be specialized for the value(s) of p contained. Figure
11.33 shows the resulting code for each of
the three iteration
spaces.
Notice that the first
and third spaces do not need loops on i or j, because for the particular
value of p that defines each space, these loops are degenerate; they
have only one iteration. For example, in space (1), substituting p = —100 in the loop bounds restricts i to 1, and subsequently j to 100. The assignments
to p in spaces (1) and (3) are evidently
dead code and can be eliminated.
Next we split the
loop with index i in space (2). Again, the first and last iterations of loop index i are
different. Thus, we split the loop into three subspaces:
The loop nest for
space (2) in Fig. 11.33 can thus be written as in Fig. 11.34(a). Figure 11.34(b) shows the optimized program. We have substituted Fig.
11.34(a) for the loop nest in Fig. 11.33. We also propagated out assignments to
p, i, and j into the array accesses.
When optimizing at the intermediate-code level, some of these
assignments will be identified as common subexpressions and re-extracted from
the array-access code.
8. Source-Code Transforms
We have seen how we can derive from simple affine partitions for
each statement programs that are significantly different from the original
source. It is not apparent from the examples seen so far how affine partitions
correlate with changes at the source level. This section shows that we can
reason about source code changes relatively easily by breaking down affine
partitions into a series of primitive transforms.
Seven Primitive Affine Transforms
Every affine partition can be expressed as a series of primitive
affine transforms, each of which corresponds to a simple change at the source
level. There are seven kinds of primitive transforms: the first four primitives
are illustrated in Fig. 11.35, the last three, also known as unimodular
transforms, are illustrated in Fig. 11.36.
The figure shows one example for each primitive: a source, an
affine parti-tion, and the resulting code. We also draw the data dependences
for the code before and after the transforms. From the data dependence
diagrams, we see that each primitive corresponds to a simple geometric
transform and induces a relatively simple code transform. The seven primitives
are:
Unimodular Transforms
A unimodular transform is represented by just a unimodular
coefficient matrix and no constant vector. A unimodular matrix is a
square matrix whose determinant is ± 1 . The significance of a unimodular
transform is that it maps an n-dimensional iteration space to another
n-dimensional polyhedron, where there is a one-to-one correspondence between
iterations of the two spaces.
1.
Fusion. The fusion transform is characterized by mapping
multiple loop indexes in the original program to the same loop index.
The new loop fuses statements from different loops.
2. Fission. Fission is the inverse of fusion. It maps the same
loop index for different statements to different loop indexes in the
transformed code. This splits the original loop into multiple loops.
3. Re-indexing. Re-indexing shifts the dynamic executions of a
statement by a constant number of iterations. The affine transform has a
constant term.
4.
Scaling. Consecutive iterations in the source program are
spaced apart by a constant factor. The affine transform has a positive
nonunit coefficient.
5.
Reversal. Execute iterations in a loop in reverse order. Reversal
is char-acterized by having —1 as a coefficient.
6.
Permutation. Permute the inner and outer loops. The affine
transform consists of permuted rows of the identity matrix.
7.
Shewing. Iterate through the iteration space in the loops
at an angle. The affine transform is a unimodular matrix with l's on the
diagonal.
A Geometric Interpretation of Parallelization
The affine transforms shown in all but the fission example are
derived by apply-ing the synchronization-free affine partition algorithm to the
respective source codes. (We shall discuss how fission can parallelize code
with synchronization in the next section.) In each of the examples, the
generated code has an (outer-most) parallelizable loop whose iterations can be
assigned to different processors and no synchronization is necessary.
These examples illustrate that there is a simple geometric
interpretation of how parallelization works. Dependence edges always point from
an earlier instance to a later instance. So, dependences between separate statements
not nested in any common loop follows the lexical order; dependences between statements nested in the same loop follows the
lexicographic order. Geometri-cally, dependences of a two-dimensional loop nest
always point within the range [0°, 180°), meaning that the angle of the
dependence must be below 180°, but no less than 0°.
The affine transforms change the ordering of iterations such that
all the dependences are found only between operations nested within the same
iteration of the outermost loop. In other words, there are no dependence edges
at the boundaries of iterations in the outermost loop. We can parallelize
simple source codes by drawing their dependences and finding such transforms
geometrically.
9. Exercises for Section 11.7
Exercise 1 1 . 7 . 1 : For the
following loop
for (i = 2;
i < 100; i++)
A[i] =
A[i-2];
a)
What is the
largest number of processors that can be used effectively to execute this loop?
b)
Rewrite the
code with processor p as a parameter.
c)
Set up and find
one solution to the space-partition constraints for this loop.
d) What is the affine partition of highest rank
for this loop?
Exercise 11 . 7 . 2: Repeat Exercise 11.7.1 for the loop nests in Fig.
11.37.
Exercise 11 . 7 .
3: Rewrite the following code
for
(i = 0; i < 100; i++) A[i] = 2*A[i] ;
for
(j = 0; j < 100; j++) A[j] = A[j] + 1;
so it consists of a single loop. Rewrite the loop in terms of a
processor number p so the code can be partitioned among 100 processors,
with iteration p executed by processor p.
Exercise 11 . 7 .
4: In the following code
for (i = 1;
i < 100; i++)
for (j =
1; j
< 100; j++)
/* (s) */ A[i,j] =
(A[i-l,j] + A[i+l,j]
+ A[i,j-1] + A[i,j+l])/4;
for (i = 0; i <= 97;
i++)
A[i] = A[i+2] ;
(a)
for (i = 1; i <= 100;
i++)
for (j = 1; j <=
100; j++)
for (k = 1; k <= 100; k++) {
A[i,j,k] = A[i,j,k]
+ B[i-l,j,k];
B[i,j,k] = B[i,j,k] +
C[i, j-l,k] ;
C[i,j,k] =
C[i,j,k] + A[i,j,k-1];
}
!(b)
for (i = 1; i <= 100;
i++)
for (j = 1;
j <= 100; j++)
for (k = 1; k <=
100; k++) {
A[i,j,k] = A[i,j,k]
+ B[i-l,j,k];
B[i,j,k] = B[i,j,k]
+ A[i,j-l,k];
C[i,j,k] =
C[i,j,k] + A[i,j,k-1] + B[i,j,k];
}
!(c)
Figure 11.37: Code for Exercise 11.7.2
the only constraints
are that the statement s that forms the body of the loop
nest must execute
iterations s(i — l,j) and s(i, j — 1) before executing iteration
s(i,j). Verify that
these are the only necessary constraints. Then rewrite the code so that
the outer loop has index variable p, and on the pth iteration of the outer
loop, all instances of s(i,j) such that i + j = p are executed.
Exercise
1 1 . 7 . 5 : Repeat Exercise 11.7.4, but arrange that on the pth iteration of the outer loop, instances of s such that i — j = p
are executed.
! Exercise 1 1 . 7 . 6 : Combine the following loops
for
(i = 0; i < 100; i++) A[i] = B[i];
for
(j = 98; j >= 0; j = j-2) B[i] = i;
into a single loop, preserving all dependencies.
Exercise 11 . 7 . 7: Show
that the matrix
is unimodular. Describe the transformation it performs on a
two-dimensional loop nest.
Exercise 11 . 7 . 8: Repeat
Exercise 11.7.7 on the matrix
Related Topics