Compiler-directed cache polymorphism.
Classical compiler optimizations assume a fixed cache architecture and modify the program to take best advantage of it. In some cases, this may not be the best strategy because each loop nest might work best with a different cache configuration and transforming a nest for a given fixed cache configuration may not be possible due to data dependences. Working with a fixed cache configuration can also increase energy consumption in loops where the best required configuration is smaller than the default (fixed) one. In this paper, we take an alternate approach and modify the cache configuration for each nest depending on the access pattern exhibited by the nest. We call this technique compiler-directed cache polymorphism (CDCP). More specifically, in this paper, we make the following contributions. First, we present an approach for analyzing data reuse properties of loop nests. Second, we give algorithms to simulate the footprints of array references in their reuse space. Third, based on our reuse analysis, we present an optimization algorithm to compute the cache configurations for each nest. Our experimental results show that CDCP is very effective in finding the near-optimal data cache configurations for different nests in array-intensive applications.
INTRODUCTION
Most of today's microprocessor systems include several special
architectural features (e.g., large on-chip caches) that use
a significant fraction of on-chip transistors. These complex
and energy-hungry features are meant to be applicable across
different application domains. However, they are effectively
wasted for applications that cannot fully utilize them, as they
are implemented in a rigid manner. For example, not all the
loops in a given array-based embedded application can take
advantage of a large on-chip cache. Also, working with a fixed
cache configuration can increase energy consumption in loops
where the best required configuration (from the performance
angle) is smaller than the default (fixed) one. This is because
a larger cache can result in a large per access energy.
The conventional approach to address the locality problem
for caches (that is, the problem of maximizing the number
of cache hits) is to employ compiler optimization techniques
[8]. Current compiler techniques generally work under
the assumption of a fixed cache memory architecture, and
try to modify the program behavior such that the new behavior
becomes more compatible with the underlying cache
configuration. However, there are several problems with this
method. First, these compiler-directed modifications sometimes
are not effective when data dependences prevent necessary
program transformations. Second, the available cache
space sometimes cannot be utilized efficiently, because the
static configuration of cache does not match different requirements
of different programs and/or of different portions of
the same program. Third, most of the current compiler techniques
(adapted from scientific compilation domain) do not
take energy issues into account in general.
An alternative approach to the locality problem is to use re-configurable
cache structures and dynamically tailor the cache
configurations to meet the execution profile of the application
at hand. This approach has the potential to address the locality
problem in cases where optimizing the application code
alone fails. However, previous research on this area [1, 9] is
mainly focused on the implementation and the employment
mechanisms of these designs, and lacks software-based techniques
to direct dynamic cache reconfigurations. Recently, a
compiler-directed scheme to adapt the cache assist was proposed
in [6]. Our work focuses on the cache as opposed to the
cache assist.
In this paper, we propose a strategy where an optimizing
compiler decides the best cache configuration for each nest
in the application code. More specifically, in this paper, we
make the following contributions. First, we present techniques
for analyzing the data reuse properties of a given loop nest
and constructing formal expressions of these reuse patterns.
Second, we develop algorithms to simulate the footprints of
array references. Our simulation approach is much more efficient
than classical cycle-based simulation techniques as it
simulates only data reuse space. Third, we develop an optimization
algorithm for computing the optimized cache configurations
for each loop nest. We also provide a program level
algorithm for selecting dynamic cache configurations. We focus
on the behavior of array references in loop nests as loop
nests are the most important part of array-intensive media
and signal processing application programs. In most cases,
the computation performed in loop nests dominates the execution
time of these programs. Thus, the behavior of the
loop nests determines both performance and energy behavior
of applications. Previous research [8] shows that the performance
of loop nests is directly influenced by the cache behavior
of array references. Also, recently, energy consumption has
become an important issue in embedded systems [9]. Conse-
quently, determining a suitable combination of cache memory
configuration and optimized software is a challenging problem
in embedded design world.
The rest of this paper is organized as follows. Section 2 reviews
basic concepts, notions, and representations for array-based
codes. In Section 3, concepts related to cache behavior
such as cache misses, interferences, data reuse, and data locality
are analyzed. Section 4 introduces our compiler-directed
cache polymorphism technique, and presents a complete set
of algorithms to implement it. We present experimental results
in Section 5 to show the effectiveness of our technique.
Finally, Section 6 concludes the paper with a summary and
discusses some future work on this topic.
2. ARRAY-BASED CODES
This paper is particularly targeted at the array-based codes.
Since the performance of loop nests dominates the overall performance
of the array-based codes, optimizing nests is particularly
important for achieving best performance in many
embedded signal and video processing applications. Optimizing
data locality (so that the majority of data references are
satisfied from the cache instead of main memory) can improve
the performance and energy efficiency of loop nests in the following
ways. First, it can significantly reduce the number of
misses in data cache, thus avoiding frequent accesses to lower
memory hierarchies. Second, by reducing the number of accesses
to the lower memory hierarchies, the increased cache hit
rate helps promote the energy efficiency of the entire memory
system. In this section, we discuss some basic notions about
array-based codes, loop nests, array references as well as some
assumptions we made.
2.1 Representation for Programs
We assume that the application code to be optimized has
the format which is shown in Figure 1.
Assumption 1. Each array in the application code being
optimized is declared in the global declaration section of the
program. The arrays declared in the global section can be referenced
by any loop in the code.
This assumption is necessary for our algorithms that will
be discussed in following sections. In the optimization stage
of computing the cache configuration for the loop nests, Assumption
1 ensures an exploitable relative base address of
each array involved.
Global Declaration Section of Arrays;
main(int argc, char *argv[ ])
f
Loop Nest No. 0;
Loop Nest No.
Loop Nest No. l;

Figure

1: Format for a Program.
f

Figure

2: Format for a Loop Nest.
Since loop nests are the main structures in array-based pro-
grams, program codes between loop nests can be neglected.
We also assume that each nest is independent from the oth-
ers. That is, as shown in Figure 1, the application contains
a number of independent nests, and no inter-loop-nest data
reuse is accounted for. This assumption can be relaxed to
achieve potentially more effective utilization of reconfigurable
caches. This will be one of our future research. Note that several
compiler optimizations such as loop fusion, fission, and
code sinking can be used to bring a given application code
into our format [12].
Assumption 2. All loop nests are at the same program lexical
level, the global level. There is no inter-nesting between
any two different loop nests.
Assumption 3. All nests in the code are perfectly-nested,
i.e., all array operations and array references only occur at
the innermost loop.
These assumption, while not vital for our analysis, make our
implementation easier. We plan to relax these in our future
work.
2.2 Representation for Loop Nests
In our work, loop nests form the boundaries at which dynamic
cache reconfigurations occur. Figure 2 shows the format
for a loop nest.
In this format, ~ i stands for the loop index vector, ~
are the corresponding
lower bound, upper bound, and stride for each loop index
to different instances of array references in the nest.
Note that these may be same or different references to the
same array, or different references to different arrays. Function
f j;k ( ~ i) is the subscript (expression) function (of ~ i) for the
th subscript of the j th array reference, where
and dk is the number of dimensions for the
corresponding array.
2.3 Representation for Array References
In a loop nest with the loop index vector ~ i, a reference AR j
to an array with m dimensions is expressed as:
We assume that the subscript expression functions f j;k ( ~ i) are
affine functions of the loop indices and loop-invariant con-
stants. A row-major storage layout is assumed for all arrays
as in C language. Assuming that the loop index vector is
an n depth vector; that is, ~
the number of loops in the nest, an array reference can be
represented
(1)
The vector at the left side of the above equation is called
array reference subscript vector ~
f . The matrix above is defined
as access matrix A. The rightmost vector is known as
the constant offset vector ~c. Thus, the above equation can be
also written as [12]:
~
3. CACHE BEHAVIOR
In this section, we review some basic concepts about cache
behavior. As noted earlier, in array-intensive applications,
cache behavior is largely determined by the footprints of the
data manipulated by loop nests. In this paper, we first propose
an algorithm for analyzing the cache behavior for different
arrays and different array references in a given loop nest.
Based on the information gathered from this analysis, we then
propose another algorithm to compute the cache memory demand
in order to achieve a perfect cache behavior for the loop
nest being analyzed, and suggest a cache configuration.
3.1 Cache Misses
There are three types of cache misses: compulsory (cold)
misses, capacity misses, and conflict (interference) misses.
Different types of misses influence the performance of program
in different ways. Note that, most of the data caches
used in current embedded systems are implemented as set-associative
caches or direct-mapping caches in order to achieve
high speed, low power, and low implementation cost. Thus,
for these caches, interference misses can dominate the cache
behavior, particularly for array-based codes. It should be
stressed that since the cache interferences occur in a highly
irregular manner, it is very difficult to capture them accurately
[11]. Ghosh et al. proposed cache miss equations in [4]
as an analytical framework to compute potential cache misses
and direct code optimizations for cache behavior.
3.2 Data Reuse and Data Locality
Data reuse and data locality concepts are discussed in [12]
in detail. Basically, there are two types of data reuses: temporal
reuse and spatial reuse. In a given loop nest, if a reference
accesses the same memory location across different loop iter-
ations, this is termed as temporal reuse; if the reference accesses
the same cache block (not necessarily the same memory
location), we call this spatial reuse. We can consider temporal
reuse is a special case of spatial reuse. If there are different
references accessing the same memory location, we say that a
group-temporal reuse exists; whereas if different references are
accessing the same cache block, it is termed as group-spatial
reuse. Note that group reuse only occurs among different references
of the same array in a loop nest. When the reused
data item is found in the cache, we say that the reference exhibits
locality. This means that data reuse does not guarantee
data locality. We can convert a data reuse into locality only
by catching the reused item in cache. Classical loop-oriented
compiler techniques try to achieve this by modifying the loop
access patterns.
4. ALGORITHMSFORCACHEPOLYMOR-
The performance and energy behavior of loop nests are
largely determined by their cache behavior. Thus, how to optimize
the cache behavior of loop nests is utmost important
for satisfying high-performance and energy efficiency demands
of array-based codes.
There are at least two kinds of approaches to perform optimizations
for cache behavior. The conventional way is compiler
algorithms that transform loops using interchange, re-
versal, skewing, and tiling transformations, or transform the
data layout to match the array access pattern. As mentioned
earlier, the alternative approach is to modify the underlying
cache architecture depending on the program access pattern.
Recent research work [7] explores the potential benefits from
the second approach. The strategy presented in [7] is based on
exhaustive simulation. The main drawback of this simulation-based
strategy is that it is extremely time consuming and can
consider only a fixed set of configurations. Typically, simulating
each nest with all possible cache configurations makes this
approach unsuitable for practice. In this section, we present
an alternative way for determining the suitable cache configurations
for different sections (nests) of a given code.
4.1 Compiler-directed Cache Polymorphism
The existence of cache interferences is the main factor that
degrades the performance of a loop nest. cache interferences
disrupt the data reuse in a loop nest by preventing data
reuse from being converted into locality. Note that both self-
interferences or cross-interferences can prevent a data item
from being used while it is still in the cache. Our objective is
then to determine the cache configurations that help reduce
interferences. The basic idea behind the compiler-directed
cache polymorphism (CDCP) is to analyze the source code of
an array-based program and determine data reuse characteristics
of its loop nests at compile time, and then to compute a
suitable (near-optimal) cache configuration for each loop nest
to exploit the data locality implied by its reuse. The near-optimal
cache configuration determined for each nest eliminates
most of the interference misses while keeping the cache
size and associativity under control. In this way, it optimizes
execution time and energy at the same time. In fact, increasing
either cache capacity or associativity further only
increases energy consumption. In this approach, the source
codes are not modified (obviously, they can be optimized be-
f

Figure

3: Example Code - a Loop Nest.
fore our algorithms are run; what we mean here is that we do
not do any further code modifications for the sake of cache
morphism).
At the very high level, our approach can be described as
follows. First, we use compiler to transform the source codes
into an intermediate format. In the second step, each loop
nest is processed as a basic element for cache configuration.
In each loop nest, references of each array are assigned into
different uniform reference sets. Each uniform set is then analyzed
to determine the reuse they exhibit over different loop
levels. Then, for each array, an algorithm is used to simulate
the footprints of the reuse space within the layout space of
this array. Following this, a loop nest level algorithm optimizes
the cache configurations while ensuring data locality.
Finally, the code is generated such that these dynamic cache
configurations are activated at runtime (in appropriate points
in the application code).
4.2 Array References and Uniform Reference
Sets
Every array reference is expressed in Equation 2, ~
in which ~
f is the subscript vector, A is the access matrix, ~ i
is the loop index vector and ~c is the constant vector. All
the information are stored in the array reference leaf, array
node and its parent loop-nest node of the intermediate codes.
Consider a piece of code in Figure 3, which is a loop nest:
The first reference of array a is represented by the following
access matrix Aa and constant offset vector \Gamma! ca ,
The reference to array b is also represented by its access matrix
A b and constant offset vector \Gamma! c b :
The definition of uniform reference set is very similar to
the uniformly generated set [3]. If two references to an array
have the same access matrix and only differ in constant offset
vectors, these two references are said to belong to the same
uniform reference set. Constructing uniform reference sets for
an array provides an efficient way for analyzing the data reuse
for the said array. This is because all references in an uniform
reference set have same data access patterns and data reuse
characteristics. Also, identifying uniform reference sets allows
us to capture group reuse easily.
4.3 Algorithm for Reuse Analysis
In the following sections, we use a bottom-up approach
to introduce the algorithms for implementing our compiler-
INPUT: access matrix Am\Lambdan of a uniform reference set
array node, loop-nest node
a given cache block size: BK SZ
OUTPUT: self-reuse pattern vector \Gamma\Gamma\Gamma! SRPn of this uniform set
Begin
Initial self-reuse pattern vector: \Gamma\Gamma\Gamma!
current loop level CLP to be the innermost loop:
current dimension level CDN to be the highest
dimension:
Set index occurring flag IOF
If Element in access matrix A[CDN ][CLP
Break
Go up to the next lower dimension level
While CDN == the lowest dimension
If IOF == FALSE
Set reference has temporal reuse at this level:
Else If CDN == m
If A[CDN ][CLP
Set reference has spatial reuse at this level:
Go up to the next higher loop level
While CLP == the outermost loop level
End.

Figure

4: Algorithm 1: Self-Reuse Analysis.
directed cache polymorphism technique. First, algorithms analyzing
the data reuses including self-reuses and group-reuses
are provided for each uniform reference set in this subsection.
4.3.1 Self-Reuse Analysis
Before the reuse analysis, all references of an array in a loop
nest are first constructed into several uniform reference sets.
Self-reuses (both temporal and spatial) are analyzed at the
level of uniform set. This algorithm works on access matrix.
The detailed algorithm is shown in Figure 4.
This algorithm checks each loop index variable from the
innermost loop to the outermost loop to see whether it occurs
in the subscript expressions of the references. If the j th
loop index variable i j does not occur in any subscript expres-
sion, the reflection in access matrix is that all elements in
the j th column are 0. This means that the iterations at the
th loop do not change the memory location accessed, i.e.,
the array reference has self-temporal reuse in the j th loop.
If the index variable only occurs in the lowest (the fastest-
dimension (i.e., the m th dimension), the distance
between the contiguous loop iterations is checked. In the al-
gorithm, s[CLP ] is the stride of the CLP th loop, BK SZ is
a given cache block size and ELMT SZ is the size of array
elements. If the distance (A[CDN ][CLP ]   s[CLP ]) between
two contiguous iterations of this reference is within a cache
block, it has spatial reuse in this loop level.
4.3.2 Group-Reuse Analysis
Group reuses only exist among references in the same uniform
reference set. Group-temporal reuse occurs when different
references access the same data location across the loop
iterations, while group-spatial reuse exists when different references
access the same cache block in the same or different
loop iterations. Algorithm 2 in Figure 5 exploits a simplified
version of group reuse which only exists in one loop level.
When a group-spatial reuse is found at a particular loop
level, the algorithm in Figure 5 first checks whether this level
INPUT: a uniform reference set with A and ~cs
array node, loop-nest node
a given cache block size: BK SZ
OUTPUT: group-reuse pattern vector \Gamma\Gamma\Gamma\Gamma! GRPn of this uniform set
Begin
Initial group-reuse pattern vector: \Gamma\Gamma\Gamma\Gamma!
For each pair of constant vectors ~
c1 and ~
If ~
c1 and ~
c2 only differ at the j th element
Check the j th row in access matrix A
Find the first occurring loop index variable (non-zero
element) starting from the innermost loop, say i
Continue
Else
Check the k th column of access matrix A
only occurs in the j th dimension
is the lowest dimension of array
If init dist%A[k][m] == 0
Else If GRP[k] == 0
Else
If init dist%A[k][m] == 0
End.

Figure

5: Algorithm 2: Group-Reuse Analysis.
has group-temporal reuse for other pairs of references. If it
does not have such reuse, this level will be set to have group-
spatial reuse. Otherwise, it just omits the current reuse found.
For group-temporal reuse found at some loop level, the element
corresponding to that level in the group-reuse vector
\Gamma\Gamma\Gamma! GRPn will be directly set to have group-temporal reuse.
Now, for each array and each of its uniform reference sets
in a particular loop nest, using Algorithm 1 and Algorithm
2, the reuse information at each loop level can be collected.
As for the example code in subsection 4.3, references to array
a have self-spatial reuse at loop level l, self-temporal reuse
at loop level j and group reuse at loop level j. Reference of
array b has self-spatial reuse at loop level i.
Note that, in contrast to the most of the previous work in
reuse analysis (e.g., [12]), this approach is simple and computes
reuse information without solving a system of equations.
4.4 Simulating the Footprints of Reuse Spaces
The next step in our approach is to transform those data
reuses into real data localities. A straightforward idea is to
make the data cache large enough to hold all the data in these
reuse spaces of the arrays. Note that data which are out of
reuse spaces are not necessary to be kept in cache after the
first reference since there is no reuse for those data. As discussed
earlier, the cache interferences can significantly affect
the overall performance of a nest. Thus, the objective of our
technique is to find a near-optimal cache configuration, which
can reduce or eliminate the majority of the cache interferences
within a nest. An informal definition of a near-optimal cache
configuration is as follows:
Definition 1. A near-optimal cache configuration is the
possibly smallest cache in size and associativity which achieves
a near-optimal number of cache misses. And, any increase in
either cache size or associativity over this configuration does
not deliver further significant improvement.
In order to figure out such a near-optimal cache configuration
that would contain the entire reuse space for a loop
nest, the real cache behavior in these reuse spaces must be
made available for potential optimizations. In this section,
we provide an algorithm that simulates the exact footprints
(memory addresses) of array references in their reuse spaces.
Suppose, for a given loop index vector ~ i, an array reference
with a particular value of ~ can be
expressed as follows:
Here, SA is starting address of the array reference, which
is different from the base address (the memory address of
the first array element) of an array. It is the constant part
of the above equation. Suppose that the data type size of
the array elements is elmt sz, the depth of dimension is m,
the dimensional bound vectors are \Gamma!
and the constant offset vector
is derived from the following equation

ae
are integrated coefficients of the loop
index variables. Suppose the access matrix is Am\Lambdan , Cof j is
derived as follows:
ddk   a lj ;
ae
Note that, with Equation 3, the address of an array reference
at a particular loop iteration can be calculated as the
offset in the layout space of this array. The algorithm provided
in this section is using these formulations to simulate
the footprints of array references at each loop iteration within
their reuse spaces. Following two observations give some basis
as to how to simulate the reuse spaces.
Observation 1. In order to realize the reuse carried by the
innermost loop, only one cache block is needed for this array
reference.
Observation 2. In order to realize the reuse carried by
a non-innermost loop, the minimum number of cache blocks
needed for this array reference is the number of cache blocks
that are visited by the loops inner than it.
Since we have assumed that all subscript functions are affine,
for any array reference, the patterns of reuse space during
different iterations at the loop level which has the reuse are
exactly the same. Thus, we only need to simulate the first
iteration of the loop having the reuse currently under ex-
ploiting. For example, loop level j in loop vector ~ i has the
reuse we are exploiting, the simulation space is defined as
k?j varies from its lower bound l k to upper bound uk .
Algorithm 3 (shown in Figure 6) first calls Algorithms 1 and
2. Then, it simulates the footprints of the most significant
reuse space for an array in a particular loop nest. These
footprints are marked with a array bitmap.
4.5 Computation and Optimization of cache
Configurations for Loop Nests
INPUT: an array node, a loop-nest node
a given cache block size: BK SZ
OUTPUT: an array-level bitmap for footprints
Begin
Initial array size AR SZ in number of cache blocks
Allocate an array-level bitmap ABM with size AR SZ
and initial ABM to zeros
Initial the highest reuse level RS
//n is the depth of loop nest
For each uniform reference set
Call Algorithm 1 for self-reuse analysis
Call Algorithm 2 for group-reuse analysis
highest reuse level of this set
If RS LEV ? URS LEV
If RS LEV == n
For all references of this array
l//only use the lower bound
apply equation 3 to get the reference address f( ~ i)
transfer to block id: bk
set array bitmap: ABM [bk
Else
For all loop indexes
varies the value of i j from lower bound to upper bound
For all references of this array
apply equation 3 to get the reference address f( ~ i)
transfer to block id: bk
set array bitmap: ABM [bk
End.

Figure

Algorithm 3: Simulation of Footprints in
Reuse Spaces.
In previous subsections, the reuse spaces of each array in
a particular loop nest have been determined and their footprints
have also been simulated in the layout space of each
array. Each array has a bitmap indicating the cache blocks
which have been visited by the iterations in reuse spaces after
applying Algorithm 3. As we discussed earlier, the phenomena
of cache interferences can disturb these reuses and prevent
the array references from realizing data localities across loop
iterations. Thus, an algorithm that can reduce these cache
interferences and result in better data localities within the
reuse spaces is crucial.
In this subsection, we provide a loop-nest level algorithm to
explicitly figure out and display the cache interferences among
different arrays accessed within a loop nest. The main point
of this approach is to map the reuse space of each array into
the real memory space. At the same time, the degree of conflict
(number of interferences among different arrays) at each
cache block is stored in a loop-nest level bitmap. Since the
self-interference of each array is already solved by Algorithm
3 using an array bitmap, this algorithm mainly focuses on
reducing the group-interference that might occur among different
arrays. As is well-known, one of the most effective way
to avoid interferences is to increase the associativity of data
cache, which is used in this algorithm. Based on the definition
of near-optimal cache configuration, this algorithm tries
to find the smallest data cache with smallest associativity that
achieves significantly reduced cache interferences and nearly
perfect performance of the loop nest. Figure 7 shows the detailed
algorithm (Algorithm 4) that computes and optimizes
the cache configuration.
For a given loop nest, Algorithm 4 starts with the cache
block size (BK SZ) from its lower bound, e.g., 16 bytes and
goes up to its upper bound, e.g., 64 bytes. At each particular
BK SZ, it first applies Algorithm 3 to obtain the array bitmap
ABM of each array. Then it allocates a loop-nest level bitmap
INPUT: loop-nest node
global list of arrays declared
lower bound of block size: Bk SZ LB
upper bound of block size: Bk SZ UB
OUTPUT: optimal cache configurations at diff. BK SZ
Begin
For each array in this loop nest
Call algorithm 3 to get the array bitmap ABM
create and initial a loop-nest level bitmap LBM,
with the size is the smallest 2 n that is -
the size of the largest array (in block): LBM size
For each array bitmap ABM
map ABM into the loop-nest bitmap LBM
with the relative base-address of array: base addr
to indicate the degree of conflict at each block
For block id ! array size
base addr)%LBM
ABM [block id]
set the largest degree of conflict in LBM
set cache
set optimal cache conf. to current cache conf.
For assoc ! assoc upper bound
half the number of sets of current cache by
For
set highest value of LBM [i]; i - LBM size
set cache size = assoc   LBM size
If assoc ! assoc upper bound
and cache size ! optimal cache size
set optimal cache conf. to current cache conf.
give out optimal cache conf. at BK SZ
doubling BK SZ
while
End.

Figure

7: Algorithm 4: Compute and Optimize cache
Configurations for Loop Nests.
LBM for all arrays within this nest, whose size is the smallest
value in power of 2 that is greater or equal to the largest
array size. All ABMs are remapped to this LBM with their
relative array base addresses. The value of each bits in LBM
indicates the conflict at a particular cache block. Following
this, the optimization is carried out by halving the size of
LBM and remapping LBM . The largest value of bits in
LBM also shows the smallest cache associativity needed to
avoid the interference in the corresponding cache block. This
process is ended when the upper bound of associavitity is met.
A near-optimal cache configuration at block size BK SZ is
computed as the one which has smallest cache size as well as
the smallest associativity.
4.6 Global Level cache Polymorphism
The compiler-directed cache polymorphism technique does
not make changes to the source code. Instead, it uses compiler
only for source code parsing and generates internal code with
the intermediate format which is local to our algorithms. A
global or program level algorithm, Algorithm 5 (in Figure 8)
is presented in this subsection to obtain the directions (cache
configurations for each nest of a program) of the cache reconfiguration
mechanisms.
This algorithm first generates the intermediate format of
the original code and collects the global information of arrays
in source code. After that, it applies Algorithm 4 to each of its
loop nests and obtains the near-optimal cache configurations
for each of them. These configurations are stored in the cache-
configuration list (CCL). Each loop nest has a corresponding
INPUT: source code(.spd)
OUTPUT: Performance data and its cache configurations
for each loop nest
Begin
Initial cache-configuration list: CCL
Use one SUIF pass to generate the intermediate code format
Construct a global list of arrays declared with its
relative base address
For each loop nest
For each array in this loop nest
Construct uniform reference sets for all its references
Call algorithm 4 to optimize the cache configurations
for this loop nest
store the configurations to the CCL
For each block size
activate reconfiguration mechanisms with each loop nest
using its configuration from the CCL
Output performance data as well as the cache configuration
of each loop nest
End.

Figure

8: Algorithm 5: Global Level cache Polymorphism

#define N 8
int a[N][N][N], b[N][N][N];
f
int i, j, k, l;
f

Figure

9: An Example: Array-based Code.
node in CCL which has its near-optimal cache configurations
at different block sizes. After the nest-level optimization is
done, Algorithm 5 activates the cache reconfiguration mech-
anisms, in which a modified version of the Shade simulator
is used. During the simulation, Shade is directed to use the
near-optimal cache configurations in CCL for each loop nest
before its execution. The performance data of each loop nest
under different cache configurations is generated as output.
Since current cache reconfiguration mechanisms can only
vary cache size and cache ways with fixed cache block size,
the cache optimization is done for different (fixed) cache block
sizes. This means that the algorithms in this paper suggest
a near-optimal cache configuration for each loop nest for a
given block size. In the following section, experimental results
verifying the effectiveness of this technique are presented.
4.7 An Example
In this subsection, we focus on the example code in Figure
9 to illustrate how the compiler-directed cache polymorphism
technique works. For simplicity, this code only contains one
nest.
Algorithm 5 starts with one SUIF pass to convert the above
source code into intermediate code, in which the program
node only has one loop-nest node. The loop-nest node is
represented by its index vector ~ with an index
lower bound vector of \Gamma! , an upper bound
vector of \Gamma! stride vector of \Gamma!
. Within the nest, arrays a and b have references
AR a 1 , AR a 2 , AR a 3 and AR b , which are represented in access
matrices and constant vectors as follows:
A a 1 :@ 1
A a 2 :@ 1
A a 3 :@
Also, a global array list is generated as ! a; b ?. Then,
for array a, references AR a 1 and AR a 2 are grouped into one
uniform reference set, and AR a 3 is put to another one. Array
b, on the other hand, has only one uniform reference set.
Then, Algorithm 4 is invoked and starts from the smallest
cache block size, BK SZ, say 16 bytes. It uses Algorithm 3
to obtain the array bitmap ABMa for array a and ABM b for
array b at BK SZ. Within Algorithm 3, we first call Algorithm
1 and Algorithm 2 to analyze the reuse characteristics
of a given array. In our example, the first uniform set of array
a has self-spatial reuse at level l, group-temporal reuse at
level j, the second uniform set has self-spatial reuse at level
l and self-temporal reuse at level j. Reference of array b has
self-spatial reuse at level i. The highest level of reuse is then
used for each array by Algorithm 3 to generate the ABM for
its footprints in the reuse space. We assume an integer has 4
bytes in size. In this case, both ABMa and ABM b have 128
bits shown as follows:
These two ABMs are then passed by Algorithm 3 to Algorithm
4. In turn, Algorithm 4 creates a loop-nest bitmap
LBM with size being equal to the largest array size, MAX(
ABMs), and re-maps ABMa and ABM b to LBM . Since array
a has relative base address at 0 (byte), and array b at
2048, we determine LBM as follows:
Name Arrays Nests Brief Description
Alternate Direction Integral
aps.c 17 3 Mesoscale Hydro Model
bmcm.c 11 3 Molecular Dynamic of Water
Computation
tomcat.c 9 8 Mesh Generation
Array-based Computation
vpenta.c 9 8 Nasa Ames Fortran Kernel
Molecular Dynamics of Water

Table

1: The Array-based Benchmarks Used in the
Experiments.
The maximum value of bits in LBM indicates the number of
interference among different arrays in the nest. Thus, it is the
least associativity that is required to avoid this interference.
In this example, Algorithm 4 starts from a cache associativity
of 2 to compute the near-optimal cache configuration. Each
time, the size of LBM is halved and the LBM is re-mapped
until the resulting associativity reaches the upper bound, e.g.,
16. Then it outputs the smallest cache size with smallest associativity
as the near-optimal configuration at this block size
BK SZ. For this example, the near-optimal cache configuration
is 2KB 2-way associative cache at
The LBM after optimization is shown as follows:
Following this, Algorithm 4 continues to compute the near-optimal
cache configurations for larger cache block sizes by
doubling the previous block size. When the block size reaches
its upper bound, e.g., 64 bytes, this algorithm stops to pass
all the near-optimal configurations at different block sizes to
Algorithm 5. On receiving these configurations, Algorithm
activates Shade to simulate the example code (executable)
with these cache configurations. Then the performance data
is generated as the output of Algorithm 5.
5. EXPERIMENTS
5.1 Simulation Framework
In this section, we present our simulation results to verify
the effectiveness of the CDCP technique. Our technique
has been implemented using SUIF [5] compiler and Shade
[2]. Eight array-based benchmarks are used in this simulation
work. In each benchmark, loop nests dominate the over-all
execution time. Our benchmarks, the number of arrays
(for each benchmark) and the number of loop nests (for each
are listed in Table 1.
Our first objective here is to see the cache configurations
returned by our CDCP scheme and a scheme based on exhaustive
simulation (using Shade). We consider three different
block (line) sizes: 16, 32 and 64 bytes. Note that our work
is particularly targeted at L1 on-chip caches.
5.2 Selected cache Configurations
In this subsection, we first apply an exhaustive simulation
method using the Shade simulator. For this method, the original
program codes are divided into a set of small programs,
each program having a single nest. Shade simulates these
loop nests individually with all possible L1 data cache configurations
within the following ranges: cache sizes from 1K
to 128K, set-associativity from 1 way to 16 ways, and block
size at 16, 32 and 64 bytes. The number of data cache misses
is used as the metric for comparing performance. The optimal
cache configuration at a certain cache block size is the
smallest one in terms of both cache size and set associativity
that achieves a performance (the number of misses) which
cannot be further improved (the number of misses cannot be
reduced by 1%) by increasing cache size and/or set associa-
tivities. The left portion of Table 2 shows the optimal cache
configurations (as selected by Shade) for each loop nest in
different benchmarks as well as at different cache block sizes.
The compiler-directed cache polymorphism technique directly
takes the original source code in the SUIF .spd format
and applies Algorithm 5 to generate the near-optimal
cache configurations for each loop nest in the source code. It
does not do any instruction simulation for configuration op-
timization. Thus, it is expected to be very fast in finding
the near-optimal cache configuration. The execution engine
(a modified version of Shade) of CDCP directly applies these
cache configurations to activate the reconfiguration mechanisms
dynamically. The cache configurations determined by
are shown on the right part of Table 2. To sum up, in

Table

2, for each loop nest in a given benchmark, the optimal
cache configurations from Shade and near-optimal cache configurations
from CDCP technique at block sizes 16, 32, and
64 bytes are given. A notation such as 8k4s is used to indicate
a 8K bytes 4-way set associative cache with a block size of 32
bytes. In this table, B means bytes, K denotes kilobytes and
indicates megabytes.
From

Table

2, we can observe that CDCP has the ability to
determine cache capacities at byte granularity. In most cases,
the cache configuration determined by CDCP is less than or
equal to the one determined by the exhaustive simulation.
5.3 Simulation Results
The two sets of cache configurations for each loop nests
given in Table 2 are both simulated at the program level. All
configurations from CDCP with cache size less than 1K are
simulated at 1K cache size with other parameters unmodified.
For best comparison, the performance is shown as the cache
hit rate instead of the miss rate. Figure 10 gives the performance
comparison between Shade (exhaustive simulation)
and CDCP using a block size of 16 bytes.

Figure

10: Performance Comparison of cache Configurations
at Block Size of 16: Shade Vs CDCP.
We see from Figure 10 that, for benchmarks adi:c, aps:c,
bmcm:c and wss:c, the results obtained from Shade and CDCP
are very close. On the other hand, Shade outperforms CDCP
in benchmarks ef lux:c, tomcat:c and vpenta:c, and CDCP
Codes Shade CDCP
adi
aps
3 4k2s 4k8s 8k8s 2k16s 4k8s 8k8s
bmcm
eflux
3 128k16s 128k16s 128k1s 128k8s 256k2s 256k2s
6 128k16s 128k16s 128k1s 128k8s 256k2s 256k2s
tomcat
3 128k4s 128k8s 128k1s 64k1s 128k2s 256k2s
6 1k2s 1k4s 2k4s 64B4s 128B4s 256B2s
7 64k4s 128k8s 128k8s 32k4s 64k8s 128k16s
tsf
3 4k4s 4k16s 8k4s 4k1s 4k1s 4k1s
vpenta
3 1k4s 2k2s 2k8s 256B4s 512B2s 1k2s
5 1k4s 2k4s 4k2s 256B4s 512B2s 1k2s
6 1k2s 2k2s 2k8s 128B8s 256B4s 512B8s
7 1k2s 1k2s 1k16s 64B1s 128B2s 256B4s
wss
3 1k2s 1k2s 1k2s 64B2s 128B4s 256b4s
6 1k2s 1k2s 1k2s 32B2s 64B1s 128B2s

Table

2: cache Configurations for each Loop Nest in
Benchmarks: Shade Vs CDCP.
outperforms Shade in tsf:c. Figures 11 and 12 show the results
with block sizes of 32 and 64 bytes, separately.
We note that, for most benchmarks, the performance difference
between Shade and CDCP decreases as the block size
is increased to 32 and 64 bytes. Especially for benchmarks
adi:c, aps:c, bmcm:c and wss:c, the performances from the
two approaches are almost the same. For other benchmarks
such as tsf:c and vpenta:c, our CDCP strategy consistently
outperforms Shade when block size is 32 or 64 bytes. This
is because the exhaustive Shade simulation has a searching
range (for cache sizes) from 1K to 128K as explained earlier,
while CDCP has no such constraints (that is, it can come
up with a non-standard cache size too). Obviously, we can
use much larger and/or much finer granular cache size for exhaustive
simulation. But, this would drastically increase the
simulation time, and is not suitable for practice. In contrast,

Figure

Performance Comparison of cache Configurations
at Block Size of 32: Shade Vs CDCP.
the CDCP strategy can determine any near-optimal cache
configuration without much increase in search time.

Figure

12: Performance Comparison of cache Configurations
at Block Size of 64: Shade Vs CDCP.
For more detailed study, we break down the performance
comparison at loop nest level for benchmark aps:c. Figure 13
shows the comparison for each loop nest of this benchmark at
different cache block sizes.

Figure

13: Loop-nest Level Performance Comparison
of cache Configurations for asp.c: Shade Vs CDCP.
The results from the loop nest level comparison show that
the CDCP technique is very effective in finding the near-optimal
cache configurations for loop nests in this benchmark,
especially at block sizes of 32 and 64 bytes (the most common
block sizes used in embedded processors). Since CDCP
is analysis-based not simulation-based, we can expect that it
will be even more desirable in codes with large input sizes.
From energy perspective, the Cacti power model [10] is used
to compute the energy consumption in L1 data cache for each
loop nest of our benchmarks at different cache configurations
listed in Table 2. We use 0.18 micron technology for all the
cache configurations. The detailed energy consumption figures
are given in Table 3.
Codes Shade CDCP
adi
aps
bmcm
eflux
6 2573.0 2666.1 375.0 1323.3 795.5 821.3
tomcat
28.4 27.5 28.1 28.4 27.5 74.3
7 9461.3 18865.2 25190.9 9647.7 21984.0 57050.0
tsf
vpenta
5 188.4 216.9 108.7 188.4 97.4 98.3
wss
6 74.8 73.8 74.6 74.8 27.6 74.6

Table

3: Energy Consumption (microjoules) of L1
Data cache for each Loop Nest in Benchmarks with
Configurations in Table 2: Shade Vs CDCP.
From our experimental results, we can conclude that (i)
our strategy generates competitive performance results with
exhaustive simulation, and (ii) in general it results in a much
lower power consumption than a configuration selected by
exhaustive simulation. Consequently, our approach strikes a
balance between performance and power consumption.
6. CONCLUSIONS AND FUTURE WORK
In this paper, we propose a new technique, compiler-directed
cache polymorphism, for optimizing data locality of array-based
embedded applications while keeping the energy consumption
under control. In contrast to many previous tech-
Energy estimation is not available from Cacti due to the very
small cache configuration.
niques that modify a given code for a fixed cache architec-
ture, our technique is based on modifying (reconfiguring) the
cache architecture dynamically between loop nests. We presented
a set of algorithms that (collectively) allow us to select
a near-optimal cache configuration for each nest of a given
application. Our experimental results obtained using a set of
array-intensive applications reveal that our approach generates
competitive performance results and consumes much less
energy (when compared to an exhaustive simulation based
framework). We plan to extend this work in several direc-
tions. First, we would like to perform experiments with different
sets of applications. Second, we intend to use cache
polymorphism at granularities smaller than loop nests. And
finally, we would like to combine CDCP with loop/data based
compiler optimizations to optimize both hardware and software
in a coordinated manner.
7.



--R

Selective cache ways: On-demand cache resource allocation
Shade: a fast instruction-set simulator for execution profiling
Strategies for cache and local memory management by global program transformation.
cache miss equations: An analytical representation of cache misses.
Stanford Compiler Group.

Morphable cache architectures: potential benefits.
Improving data locality with loop transformations.
Reconfigurable caches and their application to media processing.
An integrated cache timing and power model.
cache interference phenomena.
A data locality optimizing algorithm.
--TR
Strategies for cache and local memory management by global program transformation
A data locality optimizing algorithm
Shade: a fast instruction-set simulator for execution profiling
Cache interference phenomena
Improving data locality with loop transformations
Cache miss equations
Selective cache ways
Reconfigurable caches and their application to media processing
Morphable Cache Architectures

--CTR
Min Zhao , Bruce Childers , Mary Lou Soffa, Predicting the impact of optimizations for embedded systems, ACM SIGPLAN Notices, v.38 n.7, July
Min Zhao , Bruce R. Childers , Mary Lou Soffa, A Model-Based Framework: An Approach for Profit-Driven Optimization, Proceedings of the international symposium on Code generation and optimization, p.317-327, March 20-23, 2005
Min Zhao , Bruce R. Childers , Mary Lou Soffa, An approach toward profit-driven optimization, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.3, p.231-262, September 2006
compilers;energy consumption;embedded software;cache polymorphism;data reuse;cache locality