Data locality enhancement by memory reduction.
In this paper, we propose memory reduction as a new approach to data locality enhancement. Under this approach, we use the compiler to reduce the size of the data repeatedly referenced in a collection of nested loops. Between their reuses, the data will more likely remain in higher-speed memory devices, such as the cache. Specifically, we present an optimal algorithm to combine loop shifting, loop fusion and array contraction to reduce the temporary array storage required to execute a collection of loops. When applied to 20 benchmark programs, our technique reduces the memory requirement, counting both the data and the code, by 51% on average. The transformed programs gain a speedup of 1.40 on average, due to the reduced footprint and, consequently, the improved data locality.
INTRODUCTION
Compiler techniques, such as tiling [29, 30], improves temporal
data locality by interchanging the nesting order of time-
iterative loops and array-sweeping loops. Unfortunately,
data dependences in many programs often prevent such loop
interchange. Therefore, it is important to seek locality enhancement
techniques beyond tiling.
In this paper, we propose memory reduction as a new approach
to data locality enhancement. Under this approach,
we use the compiler to reduce the size of the data repeatedly
referenced in a collection of nested loops. Between
END DO
END DO
END DO
E(I
END DO
(a) (b)
E(I
E(I
END IF
END DO
E(I
END DO
(c) (d)

Figure

1: Example 1
their reuses, the data will more likely remain in higher-speed
memory devices, such as the cache, even without loop inter-
change. Specically, we present an optimal algorithm to
combine loop shifting, loop fusion and array contraction to
contract the number of dimensions of arrays. For exam-
ples, a two-dimensional array may be contracted to a single
dimension, or a whole array may be contracted to a scalar.
The opportunities for memory reduction exist often because
the most natural way to specify a computation task may
not be the most memory-e-cient, and because the programs
written in array languages such as F90 and HPF are often
memory ine-cient. Consider an extremely simple example
(Example 1 in Figure 1(a)), where array A is assumed dead
after loop L2. After right-shifting loop L2 by one iteration

Figure

1(b)), L1 and L2 can be fused (Figure 1(c)). Array
A can then be contracted to two scalars, a1 and a2, as Figure
1(d) shows. (As a positive side-eect, temporal locality
of array E is also improved.) The aggressive fusion proposed
here also improves temporal data locality between dierent
loop nests.
In [8], Fraboulet et al. present a network
ow algorithm for
memory reduction based on a retiming theory [16]. Given a
perfect nest, the retiming technique shifts a number of iterations
either to the left or to the right for each statement in
the loop body. Dierent statements may have dierent shifting
factors. Three issues remain unresolved in their work:
Their algorithm assumes perfectly-nested loops and it
applies to one loop level only. Loops in reality, how-
ever, are mostly of multiple levels and they can be arbitrarily
nested. For perfectly-nested loops, although
one may apply their algorithm one level at a time, such
an approach does not provably minimize the memory
requirement. Program transformations such as loop
coalescing can coalesce multiple loop levels into a single
level. Unfortunately, however, their algorithm is
not applicable to the resulting loop, because the required
loop model is no longer satised.
Since their work does not target data locality, the relationship
between memory minimization and local-
ity/performance enhancement has not been studied.
In general, minimization of memory requirement does
not guarantee better locality or better performance.
Care must be taken to control the scope of loop fusion,
lest the increased loop body may increase register spills
and cache replacements, even though the footprint of
the whole loop nest may be reduced.
There are no experimental data to show that memory
requirement can actually be reduced using their
algorithm. Moreover, since their algorithm addresses
memory minimization only, there have been no experimental
data to verify our conjecture that reduced
memory requirement can result in better locality and
better performance, especially if the scope of loop fusion
is under careful control.
In this paper, we make the following main contributions:
We present a network
ow algorithm which provably
minimizes memory requirement for multi-dimensional
cases. We handle imperfectly nested loops, which contains
a collection of perfect nests, by a combination of
loop shifting, loop fusion and array contraction. We
completely reformulate the network
ow which exactly
models the problem for the multi-dimensional general
case.
The work in [8] could also be applied to our program
model if loop fusion is applied rst, possibly enabled by
loop shifting. However, our new algorithm is preferable
because (1) for multidimensional cases, our algorithm
is optimal and polynomial-time solvable with the same
complexity as the heuristic in [8], and (2) our algorithm
models imperfectly-nested loops directly.
For the general case, we propose a heuristic to control
fusion such that the estimated numbers of register
spills and cache misses should not be greater than the
ones in the original loop nests. Even though the benchmarking
cases tested so far are too small to utilize such
a heuristic, it can be important to bigger cases.
Many realistic programs may not immediately t our
program model, even though it is already more general
than that in [8]. We use a number of compiler
algorithms to transform programs in order to t the
model.
We have implemented our memory reduction technique
in our research compiler. We apply our technique to
benchmark programs in the experiments. The results
not only show that memory requirement can be
reduced substantially, but also that such a reduction
can indeed lead to better cache locality and faster execution
in most of these test cases. On average, the
memory requirement for those benchmarks is reduced
by 51%, counting both the code and the data, using
the arithmetic mean. The transformed programs have
an average speedup of 1.40 (using the geometric mean)
over the original programs.
In the rest of this paper, we will present preliminaries in Section
2. We formulate the network
ow problem and prove
its complexity in Section 3. We present controlled fusion
and discuss enabling techniques in Section 4. Section 5 provides
the experimental results. Related work is discussed in
Section 6 and the conclusion is given in Section 7.
2. PRELIMINARIES
In this section, we introduce some basic concepts and present
the basic idea for our algorithm. We present our program
model in Section 2.1 and introduce the concept of loop dependence
graph in Section 2.2. We make three assumptions
for our algorithm in Section 2.3. In Section 2.4, we illustrate
the basic idea for our algorithm. In Section 2.5, we introduce
the concept of reference window, based on which our
algorithm is developed. Lastly in Section 2.6, we show how
the original loop dependence graph can be simplied while
preserving the correctness of our algorithm.
2.1 Program Model
We consider a collection of loop nests, L1 , L2
1, in their lexical order, as shown in Figure 2(a). The
label L i denotes a perfect nest of loops with indices L i;1 ,
starting from the outmost loop. (In
Example 1, i.e. Figure 1(a), we have
Loop L i;j has the lower bound l i;j and the upper bound
respectively, where l i;j and u i;j are loop invariants. For
simplicity of presentation, all the loop nests L i , 1  i  m,
are assumed to have the same nesting level n. If they do
not, we can apply our technique to dierent loop levels incrementally
[27]. Other cases which do not strictly satisfy
this requirement are transformed to t the model using techniques
such as code sinking [30].
The array regions referenced in the given collection of loops
are divided into three classes:
An input array region is upwardly exposed to the beginning
of L1 .
An output array region is live after Lm .
A local array region does not intersect with any input
or output array regions.
By utilizing the existing dependence analysis, region analysis
and live analysis techniques [4, 11, 12, 19], we can compute
input, output and local array regions e-ciently. Note
that input and output regions can overlap with each other.
In Example 1 (Figure 1(a)), E[0 : N ] is both the input array
(c) (d)
(a) (b) (e)

Figure

2: The original and the transformed loop nests
region and the output array region, and A[1 : N ] is the local
array region. Figure 3(a) shows a more complex example
(Example 2), which resembles one of the well-known Livermore
loops. In Example 2, where each declared
array is of dimension [JN
ZZ, ZA[1,2:KN], ZB[2:JN,KN+1] are input array regions.
ZP, ZR, ZQ, ZZ are output array regions. ZA[2:JN,2:KN]
and ZB[2:JN,2:KN] are local array regions.

Figure

2(b) shows the code form after loop shifting but before
loop fusion, where p j (L i ) represents the shifting factor
for loop L i;j . In the rest of this paper, we assume that loops
are coalesced into single-level loops [30, 27] after loop
shifting but before loop fusion. Figure 2(c) shows the code
form after loop coalescing but before loop fusion, where l i
and lower and the upper loop bounds for
the coalesced loop nest L i . Figure 2(d) shows the code form
after loop fusion. The loops are coalesced to ease code generation
for general cases. However, in most common cases,
loop coalescing is unnecessary [27]. Figure 2(e) shows the
code form after loop fusion without loop coalescing applied.
Array contraction will then be applied to the code shown in
either Figure 2(d) or in Figure 2(e).
2.2 Loop Dependence Graph
We extend the denitions of the traditional dependence distance
vector and dependence graph [14] to a collection of
loops as follows.
Denition 1. Given a collection of loop nests, L1
Lm , as in Figure 2(a), if a data dependence exists from iteration
n) of loop L1 to iteration (j1 ;
loop L2 , we say the distance vector is (j1
Denition 2. Given a collection of loop nests, L1 , L2
Lm , a loop dependence graph (LDG) is a directed graph
E) such that each node in V represents a loop
nest
Each directed edge, e =< represents a data
dependence (
ow, anti- or output dependence) from L i to
END DO
END DO
L2: DO
END DO
END DO
L3: DO
END DO
END DO
L4: DO
END DO
END DO
(a)
(b)
(c)

Figure

3: Example 2 and its original and simplied
loop dependence graphs
. The edge e is annotated by a distance vector 1 ~
dv(e).
For each dependence edge e, if its distance vector is not
constant, we replace it with a set of edges as follows. Let
S be the set of dependence distances e represents. Let ~
be the lexicographically minimum distance in S. Let
f ~
d1 6 ~ d, ~
d1)g. Any vector
From [29, 30], ~
(~ u is lexicographically greater than
n).
~
d1 in S1 (a subset of S) should lexically be neither smaller
than nor equal to any other vector in S. We replace the
original edge e with (jS1 annotated by ~
d0 and
~

Figure

3(b) shows the loop dependence graph for the example
in Figure 3(a), without showing the array regions.
As an example, the
ow dependence from L1 to L3 with
~
is due to array region In

Figure

3(b), where multiple dependences of the same type
ow, anti- or output) exist from one node to another, we
use one arc to represent them all in the gure. All associated
distance vectors are then marked on this single arc.
2.3 Assumptions
We make the following three assumptions in order to simplify
our formulation in Section 3.
Assumption 1. The loop trip counts for perfect nests L i
and L j are equal at the same corresponding loop level h,
n. This can be also stated as u i;h l i;h
Assumption 1 can be satised by applying techniques such
as loop peeling and loop partitioning. If the dierence in
the iteration counts is small, loop peeling should be quite
eective. Otherwise, one can partition the iteration spaces
of certain loops into equal pieces.
Throughout this paper, we use  (h) to denote the loop trip
count of loop L i at level h, which is constant or symbol-
icly constant w.r.t. the program segment under consid-
eration. Denote ~
and
equals to the number of accumulated level-n loop iterations
which will be executed in one level-h loop iteration. Let
In this paper, we also denote  i
as the number of static write references due to local array
regions 2 in loop L i . We arbitrarily assign each static write
reference in L i a number 1  k   i in order to distinguish
them. Take loops in Figure 3(b) as an example, we have
~
Assumption 2. The sum of the absolute values of all dependence
distances at loop level h in loop dependence graph
E) should be less than one-fourth of the trip count
of a loop at level h. This assumption can also be stated
as  jEj
dv(ek )j < 1~
for all ek 2 E annotated with the
dependence distance vector ~
Assumption 2 is reasonable because, for most programs, the
constant dependence distances are generally very small. If
non-constant dependence distances exist, the techniques discussed
in Section 4.2, such as loop interchange and circular
loop skewing, may be utilized to reduce such dependence
distances.
2 In the rest of this paper, the term of \a static write ref-
erence" means \a static write reference due to local array
regions".
d2
d2
(a) (b)

Figure

4: An illustration of memory minimization
Assumption 3. For each static write reference r, each instance
of r writes to a distinct memory location. There
should be no IF-statement within the loops to guard the
statement which contains the reference r. Dierent static
references should write to dierent memory locations.
If a static write reference does not write to a distinct memory
location in each loop iteration, we apply scalar or array
expansion to this reference [30]. Later on, our technique
should minimize the total size of the local array regions.
In case of IF statements, we assume both branches will be
taken. In [27], we discussed the case in which the regions
written by two dierent static write references are the same
or overlap with each other.
2.4 Basic Idea
Loop shifting is applied before loop fusion in order to honor
all the dependences. We associate an integer vector ~ p(L i )
with each loop nest L i in the loop dependence graph. Denote
is the shifting
factor of L j at loop level k (Figure 2(b)). For each dependence
edge with the distance vector ~
dv, the
new distance vector is ~ p(L
dv ~ p(L i ). Our memory
minimization problem, therefore, reduces to the problem of
determining the shifting factor, p j (L i ), for each Loop L i;j ,
such that the total temporary array storage required is minimized
after all loops are coalesced and legally fused.
dv ~ p(L i ) be the distance vector of ~
dv
after loop shifting. In this paper, ~
v2 denotes the inner
product of ~
v1 and ~
v2 . After loop coalescing, the distance
vector ~ v becomes ~~ v, which we call the coalesced dependence
distance. In order to make loop fusion legal,
must hold, on which the legality of our transformation stands.
The key to memory minimization is to count the number
of simultaneously live local array elements after transformation
(loop shifting, loop coalescing and loop fusion). As an
example, Figure 4(a) shows part of the iteration space for
three loop nests after loop coalescing but before loop fusion.
The rectangle bounds the iteration space for each loop nest.
Each point in the gure represents one iteration. The two
arrows represent the only two
ow dependences, d1 and d2 ,
which are due to the same static write reference, say r1 .
That is, r1 is the source of d1 and d2 .
After loop fusion, all the iteration spaces from dierent loop
nests map to a common iteration space. Figure 4(b) shows
how three separate iteration spaces map to a common one.
Based on Assumption 3, ~~ v also represents the number of
simultaneously live variables due to ~ v in this common iteration
space. In Figure 4(b), the number of simultaneously
live variables is 1 for d1 and is 3 for d2 .
However, there could be overlaps between the simultaneously
live local array elements due to dierent dependences.
In

Figure

4(b), the simultaneously live array elements for dependences
d1 and d2 overlap with each other. In this case,
the number of simultaneously live local array elements due
to the static write reference r1 will be the greater between
the two due to dependences d1 and d2 , i.e., 3 in this case.
Given a collection of loops, after fusion, the total number of
simultaneously live local array elements equals to the sum of
the number of simultaneously live local array elements due
to each static write reference.
2.5 Reference Windows
In [9], Gannon et al. use a reference window to quantify the
minimum cache footprint required by a dependence with a
loop-invariant distance. We shall use the same concept to
quantify the minimum temporary storage to satisfy a
ow
dependence.
Denition 3. (from [9]) The reference window, W (X
for a dependence on a variable X at time t,
is dened as the set of all elements of X that are referenced
by S1 at or before t and will also be referenced (according
to the dependence) by S2 after t.
In

Figure

1(a), the reference window due to the
ow dependence
(from L1 to L2 due to array A) at the beginning of
each loop L2 iteration is f A(I); A(I g. Its
reference window size ranges from 1 to N . In Figure 1(c),
the reference window due to the
ow dependence (caused by
array A) at the beginning of each loop iteration is f A(I 1)
g. Its reference window size is 1.
Next, we extend Denition 3 for a set of
ow dependences
as follows.
Denition 4. Given
ow dependence edges e1 , e2
es , suppose their reference windows at time t are W1 , W2 ,
respectively. We dene the reference window of f
es g at time t as [ s
Since the reference window characterizes the minimum memory
required to carry a computation, the problem of minimizing
the memory required for the given collection of loop
nests is equivalent to the problem of choosing loop shifting
factors such that the loops can be legally coalesced and fused
and that, after fusion, the reference window size of all
ow
dependences due to local array regions is minimized. Given
a collection of loop nests which can be legally fused, we
need to predict the reference window after loop coalescing
and fusion.
Denition 5. For any loop node L i (in an LDG) which
writes to local array regions R, suppose iteration (j1
becomes iteration j after loop coalescing and fusion. We dene
the predicted reference window of L i in iteration (j1
as the reference window of all
ow dependences due to R
in the beginning of iteration j of the coalesced and fused
loop. Suppose the predicted reference window with iteration
jn) has the largest size of those due to R. We
dene it as the predicted reference window size of the entire
loop L i due to R. We dene the predicted reference window
due to a static write reference r in L i as the predicted reference
window of L i due to be the array regions written by r.
convenience, if L i writes to nonlocal regions only, we
dene its predicted reference window to be empty.)
Based on Denition 5, we have the following lemma:
Lemma 1. The predicted reference window size for the
kth static write reference r in L i must be no smaller than
the predicted reference window size for any
ow dependence
due to r.
Proof. This is because the predicted reference window
size for any
ow dependence should be no smaller than the
minimum required memory size to carry the computation
for that dependence. The predicted reference window size
for the kth static write reference r in L i should be no smaller
than the memory size to carry the computation for all
ow
dependences due to r.
Theorem 1. Minimizing memory requirement is equivalent
to minimizing the predicted reference window size for
all
ow dependences due to local array regions.
Proof. By Denition 5 and Lemma 1.
Given a dependence  with the distance vector ~
dv is the dependence distance
for  after loop coalescing but before loop fusion, which we
also call the coalesced dependence distance. Due to Assumption
3, ~ ~
dv also represents the predicted reference window
size of  both in the coalesced iteration space and in the
original iteration space.
Lemma 2. Loop fusion is legal if and only if all coalesced
dependence distances are nonnegative.
Proof. This is to preserve all the original dependences.
Take loop node L2 in Figure 3(c) as an example. The predicted
reference window size of L2 due to the static write
reference ZB(J; K) is the same as the predicted reference
window size of L2 , since ZB(J; K) is the only write reference
in L2.
2.6 LDG Simplification
The loop dependence graph can be simplied by keeping
only dependence edges necessary for memory reduction. The
simplication process is based on the following three claims.
Claim 1. Any dependence from L i to itself is automatically
preserved after loop shifting, loop coalescing and loop
fusion. This is because we are not reordering the computation
within any loop L i .
2. Among all dependence edges from L i to L j ,
suppose that the edge e has the lexicographically
minimum dependence distance vector. After loop shifting
and coalescing, if the dependence distance associated with
e is nonnegative, it is legal to fuse loops L i and L j . This is
because after loop shifting and coalescing, the dependence
distances for all other dependence edges remain equal to or
greater than that for the edge e and thus remain nonnega-
tive. In other words, no fusion-preventing dependences ex-
ist. We will prove this claim in Section 3 through Lemma 3.
3. The amount of memory needed to carry a computation
is determined by the lexicographically maximum
ow-dependence distance vectors which are due to local array
regions, according to Lemma 1.
During the simplication, we also classify all edges into two
classes: L-edges and M-edges. The L-edges are used to determine
the legality of loop fusion. The M-edges will determine
the minimum memory requirement. All M-edges are
ow dependence edges. But an L-edge could be a
ow, an
anti- or an output dependence edge. It is possible that an
edge is classied both as an L-edge and as an M-edge. The
simplication process is as follows.
For each combination of the node L i and the static
reference r in L i where  i > 0, among all dependence
edges from L i to itself due to r, we keep
only the one whose
ow dependence distance vector is
lexicographically maximum. This edge is an M-edge.
For each node L i where  we remove all dependence
edges from L i to itself.
For each node L i where  i > 0, among all dependence
edges from L i to L j (j 6= i), we keep only one dependence
edge for legality such that its dependence distance
vector is lexicographically minimum. This edge
is an L-edge. For any static write reference r in L i ,
among all dependence edges from L i to L j (j 6= i) due
to r, we keep only one
ow dependence edge whose distance
vector is lexicographically maximum. This edge
is an M-edge.
For each node L i where  among all dependence
edges from L i to L j (j 6= i), we keep only the dependence
edge whose dependence distance vector is lexicographically
minimum. This edge is an L-edge.
The above process simplies the program formulation and
makes graph traversal faster. Figure 3(c) shows the loop
dependence graph after simplication of Figure 3(b). In

Figure

3(c), we do not mark the classes of the dependence
edges. As an example, the dependence edge from L1 to L3
marked with (0; 0) is an L-edge, and the one marked with
(0; 1) is an M-edge. The latter edge is associated with the
static write reference ZA(J; K).
3. OBJECTIVE FUNCTION
In this section, we rst formulate a graph-based system to
minimize the number of simultaneously live local array el-
ements. We then reduce our problem to a network
ow
problem, which is solvable in polynomial time.
3.1 Formulating Problem 1
Given a loop dependence graph G, the objective function
to minimize the number of the simultaneously live local array
elements for all loop nests can be formulated as follows.
is an edge in G.)
subject to
~ ~
We call the system dened above as Problem 1. In (2),
~ ~
M i;k represents the number of simultaneously live array
elements due to the kth static write reference in L i .
Constraint (3) says that the coalesced dependence distance
must be nonnegative for all L-edges after loop coalescing
but before loop fusion. Constraint (4) says that the number
of simultaneously live local array elements due to the kth
static write reference in L i , ~ ~
must be no smaller than
the number of simultaneously live local array elements for
every M-edge originated from L i and due to the kth static
write reference in L i .
Combining the constraint (3) and Assumption 2, the following
lemma says that the coalesced dependence distance is
also nonnegative for all M-edges.
Lemma 3. If the constraint (3) holds, ~(~ p(L
holds for all M-edges e =< in G.
Proof. If
~ ~
dv(e). If ~
holds. Otherwise,
assume that the rst non-zero component of ~
dv(e) is the
hth component. Based on Assumption 2, we have ~ ~
For an M-edge e2 =< there must exist an
L-edge e1 =< >. The constraint (3) guarantees that
holds. We have ~(~ p(L
~
~
dv(e1 )).
By the denition of L-edges and M-edges, we have ~
~
Similar to the proof for the case of in the
above, we can prove that ~( ~
holds.
From the proof of Lemma 3, we can also see that for any
dependence  which is eliminated during our simplication
process in Section 2.6, its coalesced dependence distance is
also nonnegative, given that the constraint (3) holds. Hence,
the coalesced dependence distances for all the original dependences
(before simplication in Section 2.6) are nonnega-
tive, after loop shifting and coalescing but before loop fusion.
Loop fusion is legal according to Lemma 2.
In Section 2.6, we know that for any
ow dependence edge
e3 from L i to L j due to the static write reference r which
is eliminated during the simplication process, there must
exist an M-edge e4 from L i to L j due to r. From the proof of
holds. Hence, the constraint (4) computes the predicted
reference window size, ~ ~
ow dependences
originated from L i due to the kth static write reference
in the unsimplied loop dependence graph (see Section
2.2). According to Lemma 1, the constraint (4) correctly
computes the predicted reference window size, ~ ~
M i;k .
3.2 Transforming Problem 1
We dene a new problem, Problem 2, by adding the following
two constraints to Problem 1. (e =< is an
edge in G.)
~
Lemma 4. Given any optimal solution for Problem 1,
we can construct an optimal solution for Problem 2, with
the same value for the objective function (2).
Proof. The search space of Problem 2 is a subset of
that of Problem 1. Given an LDG G, the optimal objective
function value (2) for Problem 2 must be equal to or
greater than that for Problem 1. Given any optimal solution
for Problem 1, we nd the shifting factor (~ p) and
~
M i;k values for Problem 2 as follows.
1. Initially let ~ p and ~
i;k values from Problem 1 be
the solution for Problem 2. In the following steps, we
will adjust these values so that all the constraints for
Problem 2 are satised and the value for the objective
function (2) is not changed.
2. If all ~ p values satisfy the constraint (5), go to step 4.
Otherwise, go to step 3.
3. This step nds ~ p values which satisfy the constraint
(5).
Following the topological order of nodes in G, nd the
rst node L i such that there exists an L-edge
where the constraint (5) is not satised.
(Here we ignore self cycles since they must represent
M-edges in G.) Suppose ~
is the sth and the rst
nonzero component of ~
. Let ~
the only two nonzero components
are the sth and the (s
by ~ p(L Because of ~ ~ the new ~ p
values, including ~ p(L j ), satisfy the constraints (3) and
(4). The value for the objective function (2) is also not
changed.
If ~ p(L
lexicographically nega-
tive, we can repeat the above process. Such a process
will terminate within at most n times since otherwise
the constraint (3) would not hold for the optimal solution
of Problem 1.
Note that the node L i is selected based on the topological
order and the shifting factor ~ p(L j ) is increased
compared to its original value. For any L-edge with the
destination node L j , if the constraint (5) holds before
updating ~ p(L j ), it still holds after the update. Such a
property will guarantee our process to terminate.
Go to step 2.
4. This step nds ~
i;k values which satisfy the constraint
(6).
Given nd the ~
value which satises the constraint (6) such that the
constraint (6) becomes equal for at least one edge.
If the ~
achieved above satises the constraint (4),
we are done. Otherwise, we increase the nth component
of the ~
M i;k value until the constraint (4) holds
and becomes equal for at least one edge.
Find all ~
values. The value for the objective function
(2) is not changed.
With such ~ p and ~
i;k values, the value for the objective
function (2) for Problem 2 is the same as that for Problem
1. Hence, we get an optimal solution for Problem 2 with
the same value for the objective function (2).
Theorem 2. Any optimal solution for Problem 2 is also
an optimal solution for Problem 1.
Proof. Given any optimal solution of Problem 2, we
take its ~ p and ~
M i;k values as the solution for Problem 1.
Such ~ p and ~
M i;k values satisfy the constraints (3)-(4), and
the value for the objective function (2) for Problem 1 is
the same as that for Problem 2. Such a solution must be
optimal for Problem 1. Otherwise, we can construct from
Problem 1 another solution of Problem 2 which has lower
value for the objective function (2), according to Lemma 4.
This contradicts to the optimality of the original solution
for Problem 2.
By expanding the vectors in Problem 2, an integer programming
problem results. General solutions for IP
problems, however, do not take the LDG graphical characteristics
into account. Instead of solving the IP problem,
~ ~
~ ~
~ ~ (1)
(1)

Figure

5: The transformed graph (G1) for Figure
3(c)
we transform it into a network
ow problem, as discussed in
the next subsection.
3.3 Transforming Problem 2
Given a loop dependence graph G, we generate another
graph
For any node L create a corresponding node ~
in G1 .
For any node L has an outgoing M-edge,
let the weight of ~
L i be w( ~
~. For each static
reference rk (1  k   i ) in L i , create another
node ~
in G1 , which is called the sink of ~
due to
rk . Let the weight of ~
be w( ~
For any node L i 2 G which does not have an outgoing
M-edge, let the weight of ~
For any M-edge < in G due to the static write
reference rk , suppose its distance vector is ~
dv. Add
an edge < ~
> to G1 with the distance vector
~
dv.
For any L-edge < suppose its distance
vector is ~
dv. Add an edge < ~
to G1 with the
distance vector ~
dv.
For the original graph in Figure 3(c), Figure 5 shows the
transformed graph.
We assign a vector ~ q to each node in G1 as follows.
For each node ~
For each node ~
The new system, which we call Problem 3, is dened as
follows. is an edge in G1 annotated by ~
dk .)
subject to
~
dk  ~ 0; 8e (8)
Theorem 3. Problem 3 is equivalent to Problem 2.
Proof. We have
~ 0~
Hence the objective function (2) is equivalent to (7).
For each edge e =< ~
in G1 , the inequality (8) is
equivalent to
where e1 is an L-edge in G from L i to L j . Inequality (10) is
equivalent to (5), hence inequality (8) is equivalent to (5).
For each edge e =< ~
> in G1 , the inequality (8) is
equivalent to
~
where e1 is an M-edge in G from L i to L j due to the kth
static write reference in L i . Inequality (11) is equivalent to
(6), hence inequality (8) is equivalent to (6).
Similarly, it is easy to show that the constraints (3) and (4)
are equivalent to constraint (9).
Note that one edge in G could be both an L-edge and an M-
edge, which corresponds to two edges in G1 . From Assumption
2, the following inequality holds for the transformed
graph
dv(ek )j < 1~
where ek 2 E1 is annotated with the dependence distance
vector ~
Same as Problem 2, Problem 3 can be solved by linearizing
the vector representation so that the original problem
becomes an integer programming problem, which in its general
form, is NP-complete. In the next subsections, however,
we show that we can achieve an optimal solution in polynomial
time for Problem 3 by utilizing the network
ow
property.
3.4 Optimality Conditions
We develop optimality conditions to solve Problem 3. We
utilize the network
ow property. A network
ow consists
of a set of vectors such that each vector f(e i ) corresponds
to an edge e i 2 E1 and, for each node v i 2 V1 , the sum of
ow values from all the in-edges should be equal to w(v i )
plus the sum of
ow values from all the out-edges. That is,
where ek =< :; v i > represents an in-edge of v i and
represents an out-edge of v i .
Lemma 5. Given there exists at least one
legal network
ow.
Proof. Find a spanning tree T of G1 . Assign the
ow
value to be ~ 0 for all the edges not in T . Hence, if we can
nd a legal network
ow for T , the same
ow assignment is
also legal for G1 .
We assign
ow value to the edges in T in reverse topological
order. Since the total weight of the nodes in T is equal to
~ 0, a legal network
ow exists for T .
Based on equation (13), given a legal network
ow, we have
For any node v 2 V1 , we have
or 1. For our network
ow algorithm, we abstract
out the factor ~ from w(v) such that w(v) is represented
by c only. Such an abstraction will give each
ow value the
ck is an integer constant.
Suppose f(ek )  ~ 0 for the edge ek 2 E1 , which is equivalent
to ck  0. With the constraint (9), we have
Hence, we have
Therefore, with the equation (14), if f(ek )  ~ 0, we have
Collectively, we have the optimality conditions stated as
the following theorem such that if they hold, the inequality
becomes the equality and the optimality is achieved
for Problem 3.
Theorem 4. If the following three conditions hold,
1. Constraints (8) and (9) are satised, and
2. A legal network
ow f(ek exists such that ck
3.  jV 1 j
dk holds, i.e., inequality
becomes an equality.
then Problem 3 achieves an optimal solution
dk .
Proof. Obvious from the above discussion.
Solving Problem 3
Here, let us consider each vector w(v i ), ~
dk as a single
computation unit. Based on the duality theory [24, 2],
Problem 3, excluding the constraint (9), is equivalent to
subject to
The constraint (9) is mandatory for the equivalence between
Problem 3 and its dual problem, following the development
of optimality conditions in Section 3.4 [1]. The constraint
(19) in the dual system precisely denes a
ow property,
where each edge e i is associated with a
ow vector f(e i ).
We dene Problem 4 as the system by (7)-(8) and (18)-
(20). Similar to w(v i ), the vector f(ek ) is represented by ck
Although apparently the search space
of Problem 4 encloses that of Problem 3, Problem 4
has correct solutions only within the search space dened
by Problem 3.
Based on the property of duality, Problem 4 achieves an
optimal solution if and only if
The constraints (8), (19) and (20) holds, and
The objective function values for (7) and (18) are equal,
dk holds.
If we can prove that the constraint (9) holds for the optimal
solution of Problem 4, such a solution must also be optimal
for Problem 3, according to Theorem 4.
There exist plenty of algorithms to solve Problem 4 [1,
2]. Although those algorithms are targeted to the scalar
system (the vector length equals to 1), some of them can
be directly adapted to our system by vector summation,
subtraction and comparison operations. A network simplex
algorithm [2] can be directly utilized to solve our sys-
tem. The algorithmic complexity, however, is exponential
in the worst case in terms of the number of nodes and
edges in G1 . Several graph-based algorithms [1], on the
other hand, have polynomial-time complexity. Examples include
successive shortest path algorithm with the complexity
scaling algorithm with the complexity
O(jV1 jjE1 jlogjV1 j), and so on. From [1], the current fastest
polynomial-time algorithm for solving network
ow problem
is enhanced capacity scaling algorithm with the complexity
logjV1 j). For these algorithms, we
have the following lemma.
Lemma 6. For any optimal solution of ~
q i in Problem
4, there exists a spanning tree T in G1 such that each edge
Proof. This is true due to the foundation of the simplex
method [2].
Let T be the spanning tree in Lemma 6. If we x any ~ q to
be ~ 0, all ~
can be determined uniquely. With
such uniquely-determined ~
ds
For any e =<
dk , with the
inequality (21), we have
ds j: (22)
For the inequality (22), based on the inequality (12), we
have
annotated with ~
Lemma 7. We have ~( ~
annotated with ~
dk , subject to the
constraints (8) and (23).
Proof. If ~
holds.
Otherwise, assume the rst non-zero component is the hth
for ~
dk . Then, q
and q (h)
With the constraint (23), we have
Hence, Inequality (12) guarantees that the constraint
holds when the optimality of Problem 4 is achieved.
The optimal solution for Problem 4 is also an optimal solution
for Problem 3.
3.6 Successive Shortest Path Algorithm
We now brie
y present one of the network
ow algorithms,
successive shortest path algorithm [1], which can be used to
solve Problem 4.
The algorithm is depicted in Figure 6. We let f(ek
are
scalars. After the rst while iteration, the algorithm always
Output: ~
Procedure:
Initialize the sets
while
Select a node vk 2 E and v l 2 D.
Determine shortest path distances ~
j from node vk to all
other nodes in G1 with respect to the residue costs
c
where the edge <
is annotated with ~
d ij in G1 .
Let P denote a shortest path from vk to v l .
Update ~
the
ow value in the residue network
ow graph.
Augment - units of
ow along the path P .
and the residue graph.
while

Figure

The successive shortest path algorithm
maintains feasible shifting factors and nonnegativity of
ow
values by satisfying the constraints (8) and (20). It adjusts
the
ow values such that the constraint (19) holds for all
edges in G1 when the algorithm ends. For the complete description
of the algorithm, including the concept of reduced
cost and residue network
ow graph, the semantics of sets E
and D, etc., please refer to [1].
For Example 2 (in Figure 3), after applying successive shortest
path algorithm, we have ~ p(L1
and ~ p(L2

Figure

7 shows the transformed code
for Example 2 after memory reduction.
4. REFINEMENTS
4.1 Controlled Fusion
Although array contraction after loop fusion will decrease
the overall memory requirement, loop fusion at too many
loop levels can potentially increase the working set size of the
loop body, hence it can potentially increase register spilling
and cache misses. This is particularly true if a large number
of loops are under consideration. To control the number of
fused loops, after computing the shifting factors to minimize
the memory requirement, we use a simple greedy heuristic,
Pick and Reject (see Figure 8), to incrementally select loop
nests to be actually fused. If a new addition will cause
the estimated cache misses and register spills to be worse
than before fusion, then the loop nest under consideration
will not be fused. The heuristic then continues to select
fusion candidates from the remaining loop nests. The loop
nests are examined in an order such that the loops whose
fusion saves memory most are considered rst. We estimate
register spilling by using the approach in [22] and estimate
cache misses by using the approach in [7].
It may also be important to avoid performing loop fusion at
too many loop levels if the corresponding loops are shifted.
This is because, after loop shifting, loop fusion at too many
loop levels can potentially increase the number of operations
either due to the IF-statements added to the loop body or
due to the eect of loop peeling. Coalescing, if applied,
may also introduce more subscript computation overhead.
Although all such costs tend to be less signicant than the
costs of cache misses and register spills, we still carefully
END DO
END IF
END DO
END DO
END IF
END DO

Figure

7: The transformed code for Figure 3(a) after
memory reduction
control the fusion of innermost loops. If the rate of increased
operations after fusion exceeds a certain threshold, we only
fuse the outer loops.
4.2 Enabling Loop Transformations
We use several well-known loop transformations to enable
eective fusion. Long backward data-dependence distances
make loop fusion ineective for memory reduction. Such
long distances are sometimes due to incompatible loops [26]
which can be corrected by loop interchange. Long backward
distances may also be due to circular data dependences
which can be corrected by circular loop skewing [26]. Fur-
thermore, our technique applies loop distribution to a node,
the dependence distance vectors originated from L i
are dierent from each other. In this case, distributing the
loop may allow dierent shifting factors for the distributed
loops, potentially yielding a more favorable result.
5. EXPERIMENTAL RESULTS
We have implemented our memory reduction technique in a
research compiler, Panorama [12]. We implemented a net-
work
ow algorithm, successive shortest path algorithm [1].
The loop dependence graphs in our experiments are relatively
simple. The successive shortest path algorithm takes
less than 0.06 seconds for each of the benchmarks. To measure
its eectiveness, we tested our memory reduction technique
on 20 benchmarks on a SUN Ultra II uniprocessor
workstation and on a MIPS R10K processor within an SGI
Procedure Pick and Reject
Input: (1) a collection of m loop nests, (2) ~ ~
the estimated number of register
spills np and the estimated number of cache misses nm, both in
the original loop nests.
Output: A set of loop nests to be fused, FS.
Procedure:
1. Initialize FS to be empty. Let OS initially contain all the m
loop nests.
2. If OS is empty, return FS. Otherwise, select a loop nest L i
from OS such that the local array regions R written in L i can
be reduced most, i.e., the dierence between the size of R and
the number of the simultaneously live array elements due to the
static write references in L i , should lexically be neither smaller
than nor equal to any other loop nest in OS. Let TR be the set
of loop nests in OS which contain references to R. Estimate a,
the number of register spills, and b, the number of cache misses,
after fusing the loops in both FS and TR and after performing
array contraction for the fused loop. If (a  np^b  nm), then
FS FS[TR, OS OS TR. Otherwise, OS OS fL i g
and go to step 2.

Figure

8: Procedure Pick and Reject
Origin 2000 multiprocessor. We present the experimental
results on the R10K. The results on the Ultra II are
similar [27]. The R10K processor has a 32KB 2-way set-associative
data cache with a 32-byte cache line, and it
has a 4MB 2-way set-associative unied L2 cache with a
128-byte cache line. The cache miss penalty is 9 machine
cycles for the L1 data cache and 68 machine cycles for the
L2 cache.
5.1 Benchmarks and Memory Reduction

Table

1 lists the benchmarks used in our experiments, their
descriptions and their input parameters. These benchmarks
are chosen because they either readily t our program model
or they can be transformed by our enabling algorithms to
t. With additional enabling algorithms developed in the
future, we hope to collect more test programs. In this table,
\m/n" represents the number of loops in the loop sequence
(m) and the maximum loop nesting level (n). Note that
the array size and the iteration counts are chosen arbitrarily
for LL14, LL18 and Jacobi. To dierentiate benchmark
swim from SPEC95 and SPEC2000, we denote the SPEC95
version as swim95 and the SPEC2000 version as swim00.
Program swim00 is almost identical to swim95 except for
its larger data size. For combustion, we change the array
size (N1 and N2) from 1 to 10, so the execution time will
last for several seconds. Programs climate, laplace-jb,
laplace-gs and all the Purdue set problems are from an
HPF benchmark suite at Rice University [20, 21]. Except
for lucas, all the other benchmarks are written in F77. We
manually apply our technique to lucas, which is written in
F90. Among 20 benchmark programs, our algorithm nds
that the purdue-set programs, lucas, LL14 and combustion
do not need to perform loop shifting. For each of the benchmarks
in Table 1, all m loops are fused together. For swim95,
swim00 and hydro2d, where only the outer loops are
fused. For all other benchmarks, all n loop levels are fused.
For each of the benchmarks, we examine three versions of
the code, i.e. the original one, the one after loop fusion but
before array contraction, and the one after array contrac-
Table

1: Test programs
Benchmark Name Description Input Parameters m/n
LL14 Livermore Loop No. 14
Jacobi Jacobi Kernel w/o convergence test
tomcatv A mesh generation program from SPEC95fp reference input 5/1
swim95 A weather prediction program from SPEC95fp reference input 2/2
swim00 A weather prediction program from SPEC2000fp reference input 2/2
hydro2d An astrophysical program from SPEC95fp reference input 10/2
lucas A promality test from SPEC2000fp reference input 3/1
mg A multigrid solver from NPB2.3-serial benchmark Class 'W' 2/1
combustion A thermochemical program from UMD Chaos group
purdue-02 Purdue set problem02 reference input 2/1
purdue-03 Purdue set problem03 reference input 3/2
purdue-04 Purdue set problem04 reference input 3/2
purdue-07 Purdue set problem07 reference input 1/2
purdue-08 Purdue set problem08 reference input 1/2
purdue-12 Purdue set problem12 reference input 4/2
purdue-13 Purdue set problem13 reference input 2/1
climate A two-layer shallow water climate model from Rice reference input 2/4
laplace-jb Jacobi method of Laplace from Rice
laplace-gs Gauss-Seidel method of Laplace from Rice
combustion purdue-02 purdue-03 purdue-04 purdue-07 purdue-08 purdue-12 purdue-13 climate laplace-jb laplace-gs
Benchmarks (for each benchmark, from left to right: original
and transformed codes)
Normalized
Occupied
Memory
Size
Code
Data
(Data Size for the Original Programs (unit: KB))
swim00 hydro2d lucas mg combustion
191000 11405 142000 8300 89
purdue-12 purdue-13 climate laplace-jb laplace-gs
4194 4194 169 6292 1864

Figure

9: Memory sizes before and after transfor-
mation
tion. Among these programs, only combustion, purdue-07
and purdue-08 t the program model in [8]. In those cases,
the algorithm in [8] will derive the same result as ours. So,
there is no need to list those results.
For all versions of the benchmarks, we use the native Fortran
compilers to produce the machine codes. We simply
use the optimization
ag \-O3" with the following adjust-
ments. We switch prefetching for laplace-jb, software
pipelining for laplace-gs and loop unrolling for purdue-03.
For swim95 and swim00, the native compiler fails to insert
prefetch instructions in the innermost loop body after memory
reduction. We manually insert prefetch instructions into
the three key innermost loop bodies, following exactly the
same prefetching patterns used by the native compiler for
the original codes.

Figure

9 compares the code sizes and the data sizes of the
original and the transformed codes. We compute the data
size based on the global data in common blocks and the local
data dened in the main program. The data size shown for
each original program is normalized to 100. The actual data
size varies greatly for dierent benchmarks, which are listed
in the table associated with the gure. For mg and climate,
the memory requirement diers little before and after the
program transformation. This is due to the small size of the
contractable local array. For all other benchmarks, our technique
reduces the memory requirement considerably. The
arithmetic mean of the reduction rate, counting both the
data and the code, is 51% for all benchmarks. For several
small purdue benchmarks, the reduction rate is almost
100%.
5.2 Performance

Figure

compares the normalized execution time, where
\Mid" represents the execution time of the codes after loop
fusion but before array contraction, and \Final" represents
the execution time of the codes after array contraction. The
geometric mean of speedup after memory reduction is 1.40
over all benchmarks.
The best speedup of 5.67 is achieved for program purdue-03.
combustion purdue-02 purdue-03 purdue-04 purdue-07 purdue-08 purdue-12 purdue-13 climate laplace-jb laplace-gs
Normalized
Execution
Time
Original
Mid
Final

Figure

10: Performance before and after transfor-
combustion
Normalized
Cache
Ref/Miss
Count
DL1-Hit
DL1-Miss
L2-Miss
(Original, Mid and Final are from left to right for each

Figure

11: Cache statistics before and after trans-
formation
This program contains two local arrays, A(1024; 1024) and
P (1024), which carry values between three adjacent loop
nests. Our technique is able to reduce both arrays into
scalars and to fuse three loops into one.
5.3 Memory Reference Statistics
To further understand the eect of memory reduction on
the performance, we examined the cache behavior of dier-
ent versions of the tested benchmarks. We measured the
reference count (dynamic load/store instructions), the miss
count of the L1 data cache, and the miss count of the L2
unied cache. We use the perfex package to get the cache
statistics. Figures 11 and 12 compare such statistics, where
the total reference counts in the original codes are normalized
to 100.
When arrays are contracted to scalars, register reuse is often
increased. Figures 11 and 12 show that the number of total
references get decreased in most of the cases. The total
number of reference counts, over all benchmarks, is reduced
by 21.1%. However, in a few cases, the total reference counts
get increased instead. We examined the assembly codes and
found a number of reasons:50150250350purdue-02 purdue-03 purdue-04 purdue-07 purdue-08 purdue-12 purdue-13 climate laplace-jb laplace-gs
Normalized
Cache
Ref/Miss
Count
DL1-Hit
DL1-Miss
L2-Miss
(Original, Mid and Final are from left to right for each

Figure

12: Cache statistics before and after transformation
(cont.)
1. The fused loop body contains more scalar references in
a single iteration than before fusion. This increases the
register pressure and sometimes causes more register
spilling.
2. The native compilers can perform scalar replacement [3]
for references to noncontracted arrays. The fused loop
body may prevent such scalar replacement for two reasons

If register pressure is high in a certain loop, the
native compiler may choose not to perform scalar
replacement.
After loop fusion, the array data
ow may become
more complex, which then may defeat the native
compiler in its attempt to perform scalar replacement

3. Loop peeling may decease the eectiveness of scalar
replacement since fewer loop iterations benet from
it.
Despite the possibility of increased memory reference counts
in a few cases due to the above reasons, Figures 11 and 12
show that cache misses are generally reduced by memory re-
duction. The total number of cache misses, over all bench-
marks, is reduced by 63.8% after memory reduction. The
total number of L1 data cache misses is reduced by 57.3%
after memory reduction. The improved cache performance
seems to often have a bigger impact on execution time than
the total reference counts.
5.4 Other Experiments
In [27], we reported how our memory reduction technique
aects prefetching, software pipelining, register allocation
and unroll-and-jam. We conclude that our technique does
not seem to create di-culties for these optimizations.
6. RELATED WORK
The work by Fraboulet et al. is the closest to our memory
reduction technique [8]. Given a perfectly-nested loop,
they use retiming [16] to adjust the iteration space for individual
statements such that the total buer size can be
minimized. We have compared their algorithm with ours in
the introduction and in Section 5.1.
Callahan et al. present unroll-and-jam and scalar replacement
techniques to replace array references with scalar variables
to improve register allocation [3]. However, they only
consider the innermost loop in a perfect loop nest. They do
not consider loop fusion, neither do they consider array partial
contraction. Gao and Sarkar present the collective loop
fusion [10]. They perform loop fusion to replace arrays by
scalars, but they do not consider partial array contraction.
They do not perform loop shifting, therefore they cannot
fuse loops with fusion-preventing dependences. Sarkar and
Gao perform loop permutation and loop reversal to enable
collective loop fusion [23]. These enabling techniques can
also be used in our framework.
Lam et al. reduce memory usage for highly-specialized multi-dimensional
integral problems where array subscripts are
loop index variables [15]. Their program model does not
allow fusion-preventing dependences. Lewis et al. proposes
to apply loop fusion and array contraction directly to array
statements for array languages such as F90 [17]. The same
result can be achieved if the array statements are transformed
into various loops and loop fusion and array contraction
are then applied. They do not consider loop shifting in
their formulation. Strout et al. consider the minimum working
set which permits tiling for loops with regular stencil of
dependences [28]. Their method applies to perfectly-nested
loops only. In [6], Ding indicates the potential of combining
loop fusion and array contraction through an example. How-
ever, he does not apply loop shifting and does not provide
formal algorithms and evaluations.
Loop fusion has been studied extensively. To name a few
publications, Kennedy and McKinley prove maximizing data
locality by loop fusion is NP-hard [13]. They provide two
polynomial-time heuristics. Singhai and McKinley present
parameterized loop fusion to improve parallelism and cache
locality [25]. They do not perform memory reduction or loop
shifting. Recently, Darte analyzes the complexity of loop fusions
[5] and claims that the problem of maximum fusion of
parallel loops with constant dependence distances is NP-complete
when combined with loop shifting. His goal is to
nd the minimum number of partitions such that the loops
within each partition can be fused, possibly enabled by loop
shifting, and the fused loop remains parallel. Mainly because
of dierent objective functions, his problem and ours
yield completely dierent complexity. Manjikian and Abdelrahman
present shift-and-peel [18]. They shift the loops
in order to enable fusion. None of the works listed above
address the issue of minimizing memory requirement for a
collection of loops and their techniques are very dierent
from ours.
7. CONCLUSION
In this paper, we propose to enhance data locality via a
memory reduction technique, which is a combination of loop
shifting, loop fusion and array contraction. We reduce the
memory reduction problem to a network
ow problem, which
is solved optimally in O(jV j 3 ) time. Experimental results so
far show that our technique can reduce the memory requirement
signicantly. At the same time, it speeds up program
execution by a factor of 1.40 on average. Furthermore, the
memory reduction does not seem to create di-culties for a
number of other back-end compiler optimizations. We also
believe that memory reduction by itself is vitally important
to computers which are severely memory-constrained and to
applications which are extremely memory-demanding.
8.

ACKNOWLEDGEMENTS

This work is sponsored in part by National Science Foundation
through grants CCR-9975309, ACI/ITR-0082834 and
MIP-9610379, by Indiana 21st Century Fund, by Purdue
Research Foundation, and by a donation from Sun Microsys-
tems, Inc.
9.



--R

Network Flows: Theory
Linear Programming and Network Flows.
Improving register allocation for subscripted variables.
Interprocedural array region analyses.
On the complixity of loop fusion.
Improving
On estimating and enhancing cache e
Loop alignment for memory accesses optimization.
Strategies for cache and local memory management by global program transformation.
Collective loop fusion for array contraction.
Structured data ow analysis for arrays and its use in an optimizing compiler.
Experience with e-cient array data ow analysis for array privatization
Maximizing loop parallelism and improving data locality via loop fusion and distribution.
The Structure of Computers and Computations
Optimization of memory usage and communication requirements for a class of loops implementing multi-dimensional integrals
Retiming synchronous circuitry.
The implementation and evaluation of fusion and contraction in array languages.
Fusion of loops for parallelism and locality.
Array data- ow analysis and its use in array privatization
Applications benchmark set for fortran-d and high performance fortran
Problems to test parallel and vector languages.
Optimized unrolling of nested loops.
Optimization of array accesses by collective loop transformations.
Theory of Linear and Integer Programming.
A parameterized loop fusion algorithm for improving parallelism and cache locality.
New tiling techniques to improve cache temporal locality.
Performance enhancement by memory reduction.

Improving Locality and Parallelism in Nested Loops.
High Performance Compilers for Parallel Computing.
--TR
Theory of linear and integer programming
Strategies for cache and local memory management by global program transformation
Linear programming and network flows (2nd ed.)
Structured dataflow analysis for arrays and its use in an optimizing complier
Improving register allocation for subscripted variables
Optimization of array accesses by collective loop transformations
Network flows
Array-data flow analysis and its use in array privatization
Improving locality and parallelism in nested loops
Interprocedural array region analyses
Fusion of Loops for Parallelism and Locality
Experience with efficient array data flow analysis for array privatization
The implementation and evaluation of fusion and contraction in array languages
Schedule-independent storage mapping for loops
New tiling techniques to improve cache temporal locality
Optimized unrolling of nested loops
High Performance Compilers for Parallel Computing
Structure of Computers and Computations
Optimization of Memory Usage Requirement for a Class of Loops Implementing Multi-dimensional Integrals
On Estimating and Enhancing Cache Effectiveness
Collective Loop Fusion for Array Contraction
Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution
On the Complexity of Loop Fusion
Loop Alignment for Memory Accesses Optimization
Improving effective bandwidth through compiler enhancement of global and dynamic cache reuse

--CTR
G. Chen , M. Kandemir , M. J. Irwin , G. Memik, Compiler-directed selective data protection against soft errors, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
Yonghong Song , Cheng Wang , Zhiyuan Li, A polynomial-time algorithm for memory space reduction, International Journal of Parallel Programming, v.33 n.1, p.1-33, February 2005
David Wonnacott, Achieving Scalable Locality with Time Skewing, International Journal of Parallel Programming, v.30 n.3, p.181-221, June 2002
G. Chen , M. Kandemir , M. Karakoy, A Constraint Network Based Approach to Memory Layout Optimization, Proceedings of the conference on Design, Automation and Test in Europe, p.1156-1161, March 07-11, 2005
Apan Qasem , Ken Kennedy, Profitable loop fusion and tiling using model-driven empirical search, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
Alain Darte , Guillaume Huard, New Complexity Results on Array Contraction and Related Problems, Journal of VLSI Signal Processing Systems, v.40 n.1, p.35-55, May       2005
Benny Thrnberg , Qubo Hu , Martin Palkovic , Mattias O'Nils , Per Gunnar Kjeldsberg, Polyhedral space generation and memory estimation from interface and memory models of real-time video systems, Journal of Systems and Software, v.79 n.2, p.231-245, February 2006
Daniel Cociorva , Gerald Baumgartner , Chi-Chung Lam , P. Sadayappan , J. Ramanujam , Marcel Nooijen , David E. Bernholdt , Robert Harrison, Space-time trade-off optimization for a class of electronic structure calculations, ACM SIGPLAN Notices, v.37 n.5, May 2002
Geoff Pike , Paul N. Hilfinger, Better tiling and array contraction for compiling scientific programs, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-12, November 16, 2002, Baltimore, Maryland
Yonghong Song , Rong Xu , Cheng Wang , Zhiyuan Li, Improving Data Locality by Array Contraction, IEEE Transactions on Computers, v.53 n.9, p.1073-1084, September 2004
Zhiyuan Li , Yonghong Song, Automatic tiling of iterative stencil loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.6, p.975-1028, November 2004
Chen Ding , Ken Kennedy, Improving effective bandwidth through compiler enhancement of global cache reuse, Journal of Parallel and Distributed Computing, v.64 n.1, p.108-134, January 2004
Mahmut Taylan Kandemir, Improving whole-program locality using intra-procedural and inter-procedural transformations, Journal of Parallel and Distributed Computing, v.65 n.5, p.564-582, May 2005
loop fusion;data locality;loop shifting;array contraction