Cache interference phenomena.
The impact of cache interferences on program performance (particularly numerical codes, which heavily use the memory hierarchy) remains unknown. The general knowledge is that cache interferences are highly irregular, in terms of occurrence and intensity. In this paper, the different types of cache interferences that can occur in numerical loop nests are identified. An analytical method is developed for detecting the occurrence of interferences and, more important, for computing the number of cache misses due to interferences. Simulations and experiments on real machines show that the model is generally accurate and that most interference phenomena are captured. Experiments also show that cache interferences can be intense and frequent. Certain parameters such as array base addresses or dimensions can have a strong impact on the occurrence of interferences. Modifying these parameters only can induce global execution time variations of 30% and more. Applications of these modeling techniques are numerous and range from performance evaluation and prediction to enhancement of data locality optimizations techniques.
Introduction
Three types of cache misses can be distinguished
[6, 7]: cold-start misses which are compulsory, capacity
misses and interference (or conflict) misses. Capacity
occur when cache space is unsufficient to store
all data to be reused. Interference misses occur when
two data are mapped to the same cache location. Typi-
cally, fully-associative caches do not exhibit interference
misses.
This work was supportedby the Esprit Agency DG XIII under
Grant No. APPARC 6634 BRA III.Capacity misses in numerical codes have been studied
to a great extent [2, 9, 16], and can be relatively easily
predicted and estimated. Most of these studies also attempt
to take into account the impact of the cache line
size. But, there are few studies on interference misses,
though several case-studies report that cache interferences
can severely affect cache behavior [6, 8]. Also,
in [3], suggestions are provided on how to consider interferences
for cache performance evaluation and optimization

Cache interferences are difficult to predict and esti-
mate, because it is necessary to know where data are
mapped in cache and when data are referenced. For in-
stance, consider addresses A and B that are mapped to
the same cache location and reused 3 times. Whether
the reference sequence is AAABBB or ABABAB, interference
are equal to respectively 0 or 4.
Nevertheless, several reasons press for the study of
cache interferences. First of all, cache tends to be a
performance bottleneck because of high network and
memory latencies, so that significant performance improvements
can be obtained through a slight reduction
of cache misses. Besides, several on-chip data caches
are direct-mapped in order to achieve a low hit time.
Such caches are considered to be more sensitive to interferences
[8], especially when they are small, which is
currently the case because of on-chip space constraints
kbytes in the DEC Alpha [11], MIPS R4000 [5]).
Moreover, large cache line sizes induce high interferences
[12], which is one of the reasons why cache line
size is currently kept small. Being capable to detect and
avoid cache interferences could allow further increases
of the cache line size. Most important of all, cache interferences
make program performance unpredictable.
Understanding the workings of cache phenomena would
allow precise performance analysis and prediction of application
codes.
This paper is particularly targeted towards numerical
codes which are characterized by large working sets,
so that their performance is highly dependent on the
memory hierarchy behavior. The goal of the paper is
threefold. First, to illustrate the fact that cache interferences
can occur frequently and have a significant
impact on program performance (section 2 and 3). The
second goal is to introduce a methodology for predicting
and estimating cache interferences in direct-mapped
caches for frequently occurring numerical loop nests
(section 3). The third goal is to illustrate the model
accuracy through several examples (sections 3 and 4).
A first version of the framework for computing cache
interferences has been presented in [14]. In [15], this
model has been applied to drive data copying strategies.
The present paper provides the details of the computations
and illustrates the model accuracy.
Experiments For all examples, three types of statistics
are provided: the simulated execution time (for
a whole loop or for an array), the estimated execution
time (obtained with the model) and the global
execution time of the loop timed on an HP/PA-RISC
workstation. 1 The execution time curves corresponding
to simulations and modeling have been obtained with
the following technique. Since the purpose of the model
is to predict variations of rather than absolute execution
time, a starting point picked from the Real execution
time graph (where x is the parameter varied in
the graph, and t is the execution time). Let M (x) the
number of simulated or estimated cache misses for parameter
lat . 2 The
purpose of these statistics are twofold. First, to show
the impact of cache interferences on global performance.
Second, to verify that execution time variations correspond
to miss ratio variations.
2 Notion of Cache Interferences
Cache interferences operate by disrupting the reuse
of data. Several types of reuse can be distinguished:
spatial and temporal reuse. And for each type, self-
dependence reuse (one reference reuses its own data)
and group-dependence reuse (one reference uses the
data of another reference) can also be distinguished
(see [16]).
Characteristics of the HP/PA-RISC cache:
array elements.
Direct-mapped cache.
bytes.
For the whole paper, 1 array
floating-point data
dimensions are given in array elements.
For all experiments, 1 array
1 For the experiments on the HP, the array base addresses have
been varied by using one large single array and having other arrays
point to that array. By modifying the pointed location, the
relative base address between two arrays can be varied.
2 For our HP system, the miss penalty has been experimentally
timed at 8e \Gamma 7 seconds.
Loop 2a (I=JU-1; KU=700; JU=500).290310330350-500 0 500 1000 1500 2000
Execution time for 100 runs (seconds)
Real 33333333
Estimated 2222222222222Figure 2b:Execution time.
. -
oe .
. -
oe .
oe .
Cache
Arrays
oe .
KU
Figure 2c:Layout in cache.

Figure

2: Influence of Cache Interferences.
Frequency of interferences The notion of cache
interferences conveys rare and intense phenomena like
"ping-pong", where two references (such as references
A(I) and B(I) in a Do-Loop with index I) start at the
same cache location, translate in cache and constantly
compete for the same cache line, therefore preventing
spatial reuse.
However cache interferences are much more diverse
and frequent, because any type of reuse can be dis-
rupted. In general, the larger the reuse distance for a
given datum, the higher the probability it is flushed from
cache, because the more data are loaded before reuse oc-
curs. Consider loop 2a which is a modified version of a
loop in ARC2D, a Perfect Club benchmark [1].
The reuse distance associated with the spatial reuse
of LDA(k) is equal to 1 iteration of loop k (unlikely to
be disrupted), while the reuse distance associated with
the temporal reuse of LDA(k) is equal to KU iterations
of loop k (more likely to be disrupted, depending on the
value of KU ).
Irregularity of interferences Whether two data sets
intersect in cache is determined by the cache position of
these sets. This position generally depends on two types
of parameters: the arrays base address and leading di-
mensions. Since these parameters are arbitrarily (i.e.,
not "cache-consciously") determined by the compiler or
the programmer, cache interferences occur in an apparently
"random" manner. Consider loop 2a. 3 If the cache
distance between arrays LDA and LDB is smaller than
are the base addresses of arrays LDA
and LDB), then the two data sets intersect. Assuming
a direct-mapped cache, data belonging to the intersection
cannot be reused.
Importance of cache interferences In loop 2a,
the distance between all arrays is characterized by one
parameter, so that most effects can be shown by varying
that single parameter: (ldb
(lds In figure 2b, ffi is
varied from \GammaK U to 4 \Theta KU . Performance variations of
20% (500% in the case of ping-pong) can be observed.
The match between the estimated and real execution
time graphs strongly suggests that these variations are
due to interference phenomena. Note that for each value
of ffi , the exact same number of references are performed,
only the arrays base address is modified. Other experiments
conducted in this paper (see sections 3.5, 3.6.1,
3.6.2, 3.7), show frequent and significant performance
losses due to cache interferences. Each of these examples
illustrate a type of interference phenomenon, and
for each case, it is shown in section 3 how to evaluate
the corresponding number of cache misses. Section 4
synthesizes these results by showing how to compute
the number of cache misses of loop 2a.
Modeling Cache Behavior
In this section, the techniques used to estimate the
number of interference misses are presented. Though
the method applies to all types of reuse, the method
is illustrated with self-dependence temporal reuse, because
it is the most frequent type of reuse and because
it is often the most likely to be victim of interferences.
The extensions to group-dependence reuse is explained.
3 This example is analyzed in detail in section 4.
4 Figure 2c illustrates the respective cache positions of the different
arrays for one iteration of loop J.
Because of paper length constraints, the extension to
spatial reuse is not discussed in this paper (see [13]).
Though it was not our primary goal, the methodology
can be applied to compute capacity misses as well
as interference misses (though interference misses are
far more complex to evaluate). Consequently, the analytical
expression of the total miss ratio for a given loop
can be derived, as illustrated in section 4 (compulsory
misses can be easily estimated).
3.1 Basic Concepts
Evaluating the miss ratio of a loop nest amounts to
counting, for each reference, the number of cache misses
due to disruption of locality exploitation. So, for each
reference, it is necessary to determine when reuse occurs
(i.e., the loop level where reuse occurs for the first time).
Consider loop 3.5a. The reuse of reference Y (j3; j2)
occurs on loop j 1 and the reuse of reference Z(j3; j1)
occurs on loop j 2 .
This "reuse" loop defines the set of data to be
reused. For reference Y (j3; j2), this set is equal
to fY (0; while it is equal to
reference Z(j 3
Cache
Arrays
Y (j 3
Reuse Set of
Y (j 3
Interference Set of
Interference Set of
Interference Set of
Interference Set of
Reuse Set of

Figure

3.1: Notion of Interference/Reuse Sets.
Similarly, this loop level also defines the sets of
data of all other references that can interfere with
the "reuse" set. For reference Y (j3; j2), the "in-
terference" sets are fZ(0; j 1
of Y from cache before they are reused), see figure
3.1. For reference the "interference" sets
are fY (0;
Consider any reference. On each iteration of the
reuse loop, the number of cache misses due to the disruption
of reuse for this reference is equal to the size of
the intersection (in cache lines) between the "reuse" set
and the "interference" sets.
Considering the problem this way, implicitly makes
abstraction of time considerations, i.e., when interferences
occur. The problem is then equivalent to computing
the intersection size between several sets. Summing
these intersections over all iterations of the reuse loop
provides the total number of cache interference misses
for a given reference. The next sections provide a formal
treatment of this method.
3.1.1 Reuse Set
Definition 3.1 Assuming loops are perfectly
nested (with j n the innermost loop), the reuse loop level
l of a reference is defined as
Example Consider loop 3.5a. The reuse loop level
of
3.2 Reuse Set
Within a set of array elements to be reused, it is possible
that two elements map to the same cache location.
These elements then alternately flush each other from
cache before they can be reused. Therefore, they should
not be counted within the set of elements that can be
effectively reused. It is necessary to distinguish between
theoretical reuse set and actual reuse set.
Definition 3.2 For any array reference
reuse loop is l, the theoretical reuse
set is equal to
(0 g.
Definition 3.3 The actual reuse set ARS(R) is the
cache footprint of the theoretical reuse set TRS(R), excluding
all cache lines for which mapping conflicts occur.
Definition 3.4 kTRS(R)k is the size of the theoretical
reuse set of R expressed in "array" lines, i.e., the number
of cache lines used by TRS(R) assuming an infinite
cache size.
Definition 3.5 kARS(R)k is the size of the actual
reuse set of R expressed in cache lines.
Example Consider loop 3.5a. The reuse set of
where z 0 is the base address of array Z and M
is the leading dimension of arrays X;Y; Z. In
this case array elements of N
array lines. 6 The actual reuse set is equal to
the cache lines corresponding to cache locations
1)g. Assuming
a cache size of 4 array elements and an
1-element (2 words) cache line, the actual reuse set of Z
is equal to N cache lines if N - 4, it is equal to 8 \Gamma N
cache lines if 4 and it is empty if 8 - N .
5 Note that only simple dependences are considered; for instance
the reuse associated with reference
sidered. The most frequently found dependences are simple ones,
as mentioned in [17].
6 Floor and ceiling functions have often been omitted in this
paper because experiments showed they generally don't have a
significant impact on precision.
3.3 Interference Set
The definition of the set of array elements that can
interfere with a reuse set is very similar to the definition
of a reuse set.
Definition 3.6 For any array reference
, that can interfere with a reuse
set defined on loop level l, the theoretical interference
set is equal to
(0 g.
In opposition to the actual reuse set, when two elements
of a theoretical interference set map to the same
cache line, this line is still counted in the actual interference
set.
Definition 3.7 The actual interference set AIS(R)
is exactly the cache footprint of the theoretical interference
set TIS(R).
Definition 3.8 As for the reuse set, kTIS(R)k and
kAIS(R)k denote respectively the size of the theoretical
and actual interference set of R.
Example Consider loop 3.5a. The reuse of Y (j 3
occurs on loop j 1 . So the corresponding interference set
of is defined on loop j 1 . The interference set
of 1)g.
In this case array elements of N
LS array
lines. Assuming again a cache size of 4 array elements
words) and a 1-element (2 words) cache line, the actual
interference set of Z is equal to N cache lines if N ! 4,
and it is equal to 4 cache lines if 4 - N .
3.4 Evaluating the Actual Sets 7
Consider a reference
of which we want to compute the cache footprint on
loop level l (i.e., the footprint is defined by loops
Observation 3.1 After iterating on any
loop data layout in cache is assumed
to be a set of intervals of cache locations, characterized
by the average size S of an interval, and the average
distance oe between two consecutive intervals.
This assertion is an approximationwhich aims at simplifying
the evaluation process. Using this observation,
a recursive process can be applied for each loop level
Problem 3.1 Assuming an initial regular 8 data lay-out
of intervals of size S separated by a distance of
oe cache locations (a layout obtained after iterating on
loops 1), the problem is to determine
the final layout, i.e., average size S 0 , average distance
after iterating on loop i.
7 This section can be skipped if in-depth comprehension of the
computations is not sought for.
8 i.e., the distance between any two consecutive intervals is approximately
constant.
3.4.1 Actual interference set
For problem 3.1, a recursive process can also be ap-
plied. Let oe After a number of
iterations, the intervals wrap around the cache area of
size oe 0 . Within each area of oe 1 cache locations, the
layout of intervals is identical. So, the study can be restricted
to only one such area. Within one such area,
the spacing between two consecutive intervals is equal
to oe us consider a recursive
application of this process.
Observation 3.2 On recursion level k, the size of the
area considered is equal to oe k\Gamma1 , and the spacing between
two consecutive intervals in one such area is equal
to oe k . The recursion process stops on a level s when all
iterations of loop i have been considered, or when overlapping
occurs, i.e., if oe s ! S. Starting at this point, it
is possible to determine the footprint within an area of
size oe s\Gamma1 , and assuming the layout is the same across
all areas, the footprint within the whole cache.
Proposition 3.1 Let
oe
oe
c). In b oe 0
oe
areas of size oe s\Gamma1 , n s intervals
of size S have been brought, and in the remaining
r areas n s have been brought.
Proposition 3.2 Let f i (x;
Then the cache footprint size of all intervals is equal to
ii
oe
For this layout of intervals, the average size of an
interval is equal to
ii
oe
oe
and the spacing between intervals is equal to oe
Remark oe so that all oe k
can be computed a priori with the cost of one application
of Euclide algorithm [10]. In practice, this fact
also makes the process non-recursive, since the level at
which recursion stops can be determined beforehand.
After the process has been applied for all loops
resulting layout in cache is the actual interference
set of the reference, defined on loop l.
3.4.2 Actual reuse set
The reasoning is nearly identical for the actual reuse
set, except that cache lines where overlapping occurs
must be excluded.
Proposition 3.3 The number of elements that can be
reused is equal to
ii oe 0
oe
where
An example of application of the whole process can
be found in section 3.5.
Note that this process is inaccurate (as mentioned
above, several approximations were made), so the error
can become significant after multiple applications (i.e.,
for multiple loop levels). Fortunately, a reuse set defined
over two loop levels corresponds to a 3-deep loop nest
where reuse occurs on the third loop. For such a reuse
set, the algorithm needs only to be applied once (except
if the access stride is not equal to one). Reuse sets
defined over three loops are less common in primitives
and real codes [17], or are less likely to be exploited (for
instance, loop blocking is rarely performed over more
than the two innermost loops).
Assume the reuse loop level is l for reference R.
Proposition 3.4 The number of cache misses due to
self-interferences of R is equal to
Intuitively, each cache line excluded from the actual
reuse set because of conflicts generates one cache miss,
each time the reuse set is referenced, hence the proposition

Example Consider loop 3.5a, corresponding to the
multiplication of two N \Theta N submatrices of M \Theta M
matrices.
ENDDO
ENDDO
ENDDO
Loop 3.5a (N=100).
Execution time for 100 runs (seconds)
Matrix dimension M
Real
Y
Y (est) 2222 222222222

Figure

3.5b:Execution time.
Cache
Array Y
oe .
oe .
oe .

Figure

3.5c:Layout in cache.

Figure

3.5: Self-Interferences.
Since all arrays are reused, the amount of compulsory
misses is negligible. Spatial interference misses
for are negligible because of the
small spatial reuse distance; the spatial reuse distance
for large but since this reference accounts for
a small share of all memory accesses, the impact of spatial
interference misses should not be significant. References
most memory
accesses, but the temporal reuse distance for Y (j 3
is one order of magnitude larger than for
intuitively, Y (j 3 likely to be responsible for most
temporal interference misses, so in this case, for most of
the loop misses.
Since the theoretical interference set size of Z(j 3
is equal to N elements and the theoretical reuse set size
of Y (j 3 is equal to N 2 elements, the effect of self-
interferences can be much more significant than cross-
interferences (i.e., cross-interferences can at most prevent
the reuse of N elements, while self-interferences
can prevent the reuse of all N 2 elements).
The reuse set of Y (j 3 is a set of N intervals of
with a relative distance of oe
which spread within an interval of oe
cations. The oe k values are obtained with oe
oe k\Gamma2 mod oe k\Gamma1 . Using the technique of section 3.4, n s ,
are computed. Table 3.5
shows the values of the main variables for
and different values of M . Figure 3.5b illustrates the
model precision and the impact of self-interferences on
global performance. As can be seen, for
interferences of Y are nearly total, temporal reuse cannot
be exploited. Spatial reuse can still be exploited, so
that the miss ratio is close to the theoretical minimum
of 1
0:125. But cross-interferences can yield an even
lower miss ratio.
ns SzARS S 0 oe 0 #miss

Table

3.5: Examples of values obtained.
3.6 Cross-Interferences
Consider the reuse set of a reference R (reuse occurs
on loop l) and the corresponding interference set of a
reference R 0 .
Definition 3.9 If a reuse or an interference set is defined
on loop l, its cache position is defined by 9
Lemma 3.1 The relative cache position of the interference
set of R 0 with respect to the reuse set of R is equal
to
and the relative distance between the two sets is equal to
Example Consider loop 3.5a. The reuse of Y (j 3
occurs on loop j 1 . So the corresponding interference
set of Z(j 3 is defined on loop j 1 . The position
of the actual reuse set of Y (j 3
OE(ARS(Y (j 3 and the position
of the actual interference set of Z(j 3
3.6.1 Internal cross-interferences
Definition 3.10 If ffi is independent of l , the
cross-interferences between R and R 0 are called internal
cross-interferences.
Proposition 3.5 If the cross-interferences between R
and R 0 are internal cross-interferences, the size of the
intersection
and AIS(R 0 ) is constant over the iterations of loops
9 Note that it actually corresponds to the cache position of the
first element of the set.
. The number of cache misses due to such
cross-interferences is then equal to
Proposition 3.6 The intersection between two intervals
of size S 1 and S 2 , separated by a distance of
locations, is equal to
For instance,
If the sets correspond to a collection of intervals (in-
stead of one single interval), each interval of the reuse
set is compared with each interval of the interference set.
The size of the intersection is obtained by summing over
all these subcases.
Example
ENDDO
ENDDO
Loop 3.6.1a (N=1000,M=250).9111350 200 400 600 800 1000 1200
Execution time for 100 runs (seconds)

Figure

3.6.1b: Execution time.
Cache
Arrays
oe .
. -
oe .

Figure

3.6.1c:Layout in cache.

Figure

3.6.1: Internal Cross-Interferences.
Consider loop 3.6.1a. Temporal interferences between
XA and XB are likely to account for most interferences
(C only breeds compulsory misses). The
role of both arrays is symmetric. Consider array XA.
Its reuse set is an interval of S locations,
as well as the corresponding interference set of XB,
. The relative cache distance between
the two sets is
according to the above proposition, the total number
of internal cross-interference misses of XA is equal to
.

Figure

3.6.1
illustrates the model precision and the impact of internal
cross-interferences on global performance. As can
be seen, the execution time decreases when ffi decreases,
until the two sets do not overlap.
3.6.2 External cross-interferences
For external cross-interferences, an accurate or approximate
evaluation can be used, which are tradeoffs
between accuracy and complexity. Only the approximate
evaluation is described here. The accurate evaluation
is described in [13], and see also [4] for the example
considered below.
Approximation Let us assume that ffi (the distance
between the reuse set of R and the interference set of
variable with a uniform distribution.
Interferences are averaged over all values of ffi . Hence
the proposition:
Proposition 3.7 The approximate number of cache
misses due to external cross-interferences between R
and R 0 over execution of the loop nest is equal to
\Theta
is the function defined
in section 3.6.1.
Example Consider loop 3.6.2a, which corresponds to
the multiplication of an N \Theta N matrix A with a vector
X.
reg += A(j2,j1) * X(j2)
ENDDO
ENDDO
Loop 3.6.2a.
10000 20000 30000 40000 50000
Average Execution time per reference (in

Figure

3.6.2b:Execution time.
Cache
Arrays
. -
oe .
. -
oe .

Figure

3.6.2c:Layout in cache.

Figure

3.6.2: External Cross-Interferences.
Assuming that N ! C S (i.e., no capacity miss oc-
, and the approximate
number of external cross-interference misses
of X due to A is equal to N \Theta 1
\Theta
As can be seen on figure 3.6.2, the time per reference
increases with N , mostly because the temporal reuse
of array X is disrupted by array A, until a threshold
value is reached, where the temporal reuse cannot be
exploited at all.
3.7 Extension to Group-Dependence Reuse
The techniques of sections 3.2 to 3.6 can be extended
to group-dependence reuse. In opposition to self-
dependences, the reuse set is defined by two references
reusing the data of R 1 .
The reuse loop level is simply the loop level where
reuse occurs. The reuse set is defined as the set of elements
referenced by R 1 that are reused by R 2 . Consequently
both the reuse set and the interference set are
not defined over the whole execution of one or several
loops, but over a subset of iterations of one or several
loops.
The main difference with self-dependences is that the
reuse set (as well as the interference set) is "moving"
over each iteration of the reuse loop. Consequently,
a more formal definition of the interference set is re-
quired. For each element of the theoretical reuse set,
the theoretical interference set is equal to the elements
loaded in cache, between two references to that element.
This definition is apparently dependent on each element
of the reuse set, but generally, all elements within a
reuse set behave the same way. A surprising consequence
is that internal-cross interferences disrupt group-
dependence reuse in a boolean way. Either no element of
the reuse set or all elements of the reuse set are flushed
from cache. 10 For external cross-interferences, the accurate
evaluation can be difficult to derive, but the approximate
evaluation can still be used: it is computed
for one element of the reuse set and then extended to all
elements of the reuse set. These notions are illustrated
with an example below.
Example Consider loop 3.7a. There is a group-
dependence between X(j
can be disrupted by XY (j
are assumed to have the same leading dimen-
sion, the references are in translation, and cross-
interferences are internal cross-interferences. The
reuse set is defined on loop j 2 and corresponds
to 1)g. For element
1), the interference set is equal to
1)g.
i.e., the relative distance between
its interference set, then internal cross-
interferences occur if (while the condition
is self-dependence reuse). More intuitively,
if the interference set is located before the reuse set,
it is going to "sweep away" all elements of the reuse
set before they can be reused (see figure 3.7c). So in
this case, if internal cross-interferences occur, no group-
dependence reuse can be achieved. This phenomenon is
illustrated on figure 3.7, where N
is varied from \Gamma500 to +1000.
ENDDO
ENDDO
Loop 3.7a (N1=N2=500).
More exactly, all elements of the reuse set that can be flushed
by the interference set. Some cache locations used by the reuse
set may never be used by the interference set, even though both
sets are "moving" in cache.
Execution time for 100 runs (seconds)
Figure

3.7b:Execution time.
Cache
Arrays
oe .
. -
oe .

Figure

3.7c:Layout in cache.

Figure

3.7: Disruption of Group-Dependence Reuse.
3.8 Computing the Total Number of Misses
In previous sections, it is shown how to predict and
compute the number of cache misses due to a given type
of interference. Though this is the major issue, another
difficult problem is to combine these results for several
references occurring in the same loop.
3.8.1 Cumulating interference sets
It is not possible to simply add the number of cache
misses corresponding to each reference and each type of
interferences, because some interferences can be redun-
dant. Consider the example below.
ENDDO
ENDDO
Arrays A and B can both induce external cross-
interferences on array Y . The relative cache distance
between the actual interference sets of these two arrays
is equal to ffi
If i.e., the two actual interference sets over-
lap, and in the same time they overlap with the reuse
set of Y then A and B have a redundant impact on Y ,
and cache misses should not be counted twice.
In order to avoid such redundancy, references are not
considered individually.
Definition 3.11 Two references R and R 0 belong to the
same translation group if the relative cache distance
between R and R 0 is constant.
The actual interference set of a translation group is
the union of the actual interference sets of all references
within this translation group. So interferences due to
a single reference are not considered anymore, instead,
only interferences due to a translation group are consid-
ered. This notion is useful to avoid redundant estimates
of cross-interferences. Note that, in general, there are
few translation groups within a loop body.
3.8.2 Selecting the proper dependence
Consider the following example.
ENDDO
ENDDO
There is a self-dependence for X(j 2 ) and a group-
dependence from X(j 2 ) to 1). The reuse distance
of the group-dependence (1 iteration of j 2 ) is much
shorter than that of the self-dependence (N 2 iterations
of j 2 ). So, for most elements (excluding X(0)), reference
exploits the group-dependence reuse rather than
the self-dependence. Therefore, interferences on the
group-dependence instead of the self-dependence must
be considered.
Interferences are evaluated for the dependence which
corresponds to the smallest dependence distance. In gen-
eral, array subscripts are simple enough to make this
task tractable.
Redundancies
Globally, most redundancies are avoided because of
the following reasons:
Determining cross-interferences on the actual reuse
set instead of the theoretical reuse set avoids redundant
evaluation between self-interferences and cross-
interferences.
ffl Determining internal cross-interferences before evaluating
external cross-interferences and then updating
the actual reuse set avoids redundant evaluation between
internal cross-interferences and external cross-
interferences.
ffl Redundancies within external cross-interferences
are ignored, because they proved to be negligible in most
cases; 11 this assertion is illustrated in section 4.
3.9.1 Global Algorithm
The global algorithm for computing the number of
cache interference misses is the following.
cache misses due to
self-interferences.
Compute the number of
set of R by removing elements
victim of cross-interferences
Update the actual reuse
Compute the number of
cache misses due to
external cross-interferences
cache misses due to
internal cross-interferences
Compute the number of
oe
oe
oe
oe
in the loop body
oe
dependence distance
Determine the shortest
Determine the reuse set
For the translation group
and actual reuse set
of reference R
Determine the interference set
and actual interference set
For each other translation group
Determine the interference set
and actual interference set
the total number of
Cumulate and derive
cache misses
For each reference R
4 Putting It All Together
In this section, the number of cache misses of loop 2a
is computed, based on the techniques presented in section
3. The leading dimension of arrays F; U is KU .
As mentioned in section 2, one parameter ffi is used to
characterize the distance between the different arrays
12 . As can be seen on figure 2, four intervals can be dis-
tinguished. Because of paper length constraints, only
the interval [0; KU \Gamma 1] is considered here. This interval
corresponds the most complex case because many
interference phenomena occur at the same time.
Compulsory misses
ffl The number of compulsory misses due to each array
LDA;LDB;LDS is equal to KU
LS .
references U (k; i) and U (k; j) do not belong to
the same translation group, the potential reuse between
the two references is ignored. Therefore it is considered
that both references breed compulsory misses: KU
LS for
U (k; i), and JU \ThetaKU
LS for U (k; j); the same for F (k; i)
and F (k; j).
ffl Consequently, the total number of compulsory
misses is equal to
Internal cross-interferences: self-dependence
reuse
11 It is possible, though, to come up with examples where redundancies
between external cross-interferences are significant.
This assumption does not influence the complexity of the
computations.
ffl The actual reuse set of LDA(k) is a set of KU
LS consecutive
cache lines. All references LDB(k); LDS(k),
U (k; i); F (k; i) belong to the same translation group as
LDA(k). The actual interference sets of U (k; i); F (k; i)
do not overlap with the actual reuse set of LDA(k) 13 .
The actual interference sets of both LDB(k) and
overlap with the actual reuse set of LDA(k),
but the impact of LDS(k) is redundant with that
of LDB(k) (see figure 2c). The actual interference
set size of LDB(k); LDS(k) combined is equal
to min(KU+ffi;2\ThetaKU)
LS , and overlaps by (KU \Gammaffi)
LS (where
with the actual reuse set of LDA(k).
Therefore, internal cross-interferences on LDA(k) induce
cache misses.
ffl As for LDA(k), internal cross-interferences on
LS cache misses.
ffl For LDB(k), the actual interference set size of
combined is equal to min(KU+2ffi;2\ThetaKU)
LS , and it overlaps
by 2\Theta(KU \Gammaffi)
LS with the actual reuse set of LDB(k).
Therefore, internal cross-interferences on LDB(k) induce
JU
LS cache misses.
ffl The actual interference set of F (k; i) overlaps by ffi
cache lines with the actual reuse set of U (k; i). So, there
are JU \Theta(KU \Gammaffi)
LS cache misses due to internal cross-
interferences on U (k; i). The role of U (k; i) and F (k; i)
is symmetric; therefore there are JU \Theta(KU \Gammaffi)
LS cache
misses due to internal cross-interferences on F (k; i).
So, the total number of internal cross-interferences
corresponding to self-dependence reuse disruption is
equal to
Internal cross-interferences: group-dependence
reuse
Consider the group-dependence between U (k; j) and
U 1). The actual reuse set of U
at location u the leading dimension of
U is KU ). The actual interference set corresponding
to F (k; j) starts at f 0 . F (k;
This inequation
is equivalent to 0 -
which is satisfied by the hypotheses. So, there are internal
cross-interferences of the group-dependence reuse
between U (k; 1). As mentioned in section
3.7, such interferences are boolean, so none of the
13 For sake of clarity, the relative distance between u 0 and lda 0
has been chosen so that no internal cross-interference occurs between
U(k; i); F (k; i) and LDA(k); LDB(k);LDS(k). However,
such cross-interferences would be no more difficult to compute
than the ones studied in this paragraph.
KU \Gamma1 elements of the reuse set can be reused. The condition
for interferences to occur is not satisfied for the
group-dependence between U
Consequently, the number of cache misses due to internal
cross-interferences on group-dependence reuse is
equal to
External cross-interferences
ffl The external cross-
interferences of the group-dependence reuse of U due
to LDA(k); LDB(k); LDS(k), F (k; i); U (k; i) are negligible
and can be ignored.
ffl The external
cross-interferences on LDA(k); LDB(k); LDS(k),
F (k; i); U (k; i), due to U (k; j); F (k; are estimated for
the updated actual reuse sets. The actual interference
set size corresponding to the translation group
U (k; j); U (k; j+1); U (k; j+2); F (k; j) is equal to 3 \Theta KU
(the impact of F (k; j) is redundant). Then, using function
f a defined in section 3.6.2, the total number of external
cross-interferences is equal to
4 \Theta f a
Total number of cache misses
The precision of this evaluation is illustrated on figure
2b. 14
5 Conclusions and Future Directions
The main outcome of this work is to show that computing
the number of cache misses due to interference
phenomena is a tractable task, and a methodology has
been presented to perform it. The other outcome of
the paper is to show that interference phenomena occur
frequently and can be intense. Compilers need to address
the issue of cache interferences; optimizing codes
for reducing capacity misses is not sufficient. A first
application of this work is the integration of the miss
ratio evaluation techniques in a compiler, for performance
evaluation and prediction purposes. Such an
implementation would fully validate the possibility of
automatically computing the number of cache misses,
and would also enhance the model by unveiling potential
issues that would not show in a theoretical study.
A second application is the refinement of data locality
optimization techniques, and mainly the accurate evaluation
of optimal block sizes.
14 The peaks occurring at correspond to ping-pong
phenomena (spatial reuse disruption, see section 2) which
have not been discussed here, but can be simply identified by
checking the relative position of the different arrays.



--R

Supercomputing Performance Evaluation and the Perfect Benchmarks.
A Strategy for Array Management in Local Memory.
On Estimating and Enhancing Cache Effectiveness (Extended Ab- stract)
Accurate Evaluation of Blocked Algorithms Cache Interferences.

Computer Ar- chitecture: A Quantitative Approach
Aspects of Cache Memory and Instruction Buffer Performance.
The Cache Performance of Blocked Algorithms.
Automatic and Interactive Paral- lelization

Sites, editor. Alpha Architecture Reference Man- ual
Cache Memories.
Cache Interference Phenomena.
Impact of cache interferences on usual numerical dense loop nests.
To Copy or Not to Copy: A Compile-Time Technique for Assessing When Data Copying Should be Used to Eliminate Cache Conflicts
A Data Locality Optimizing Algorithm.
An Empirical Study on Array Subscripts and Data Dependendencies.
--TR
Computer architecture: a quantitative approach
A data locality optimizing algorithm
MIPS RISC architectures
Alpha architecture reference manual
Automatic and interactive parallelization
To copy or not to copy
Supercomputer performance evaluation and the Perfect Benchmarks
Cache Memories
Concrete Math
On Estimating and Enhancing Cache Effectiveness
Aspects of cache memory and instruction buffer performance

--CTR
B. B. Fraguela , R. Doallo , J. Tourio , E. L. Zapata, A compiler tool to predict memory hierarchy performance of scientific codes, Parallel Computing, v.30 n.2, p.225-248, February 2004
Basilio B. Fraguela , Ramn Doallo , Emilio L. Zapata, Probabilistic Miss Equations: Evaluating Memory Hierarchy Performance, IEEE Transactions on Computers, v.52 n.3, p.321-336, March
van der Deijl , Gerco Kanbier , Olivier Temam , Elena D. Granston, A Cache Visualization Tool, Computer, v.30 n.7, p.71-78, July 1997
Basilio B. Fraguela , Ramn Doallo , Emilio L. Zapata, Modeling set associative caches behavior for irregular computations, ACM SIGMETRICS Performance Evaluation Review, v.26 n.1, p.192-201, June 1998
D. Andrade , B. B. Fraguela , R. Doallo, Analytical modeling of codes with arbitrary data-dependent conditional structures, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.7, p.394-410, July 2006
J. S. Hu , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , H. Saputra , W. Zhang, Compiler-directed cache polymorphism, ACM SIGPLAN Notices, v.37 n.7, July 2002
Christine Fricker , Olivier Temam , William Jalby, Influence of cross-interferences on blocked loops: a case study with matrix-vector multiply, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.4, p.561-575, July 1995
John S. Harper , Darren J. Kerbyson , Graham R. Nudd, Analytical Modeling of Set-Associative Cache Behavior, IEEE Transactions on Computers, v.48 n.10, p.1009-1024, October 1999
Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: an analytical representation of cache misses, Proceedings of the 11th international conference on Supercomputing, p.317-324, July 07-11, 1997, Vienna, Austria
Min Zhao , Bruce Childers , Mary Lou Soffa, Predicting the impact of optimizations for embedded systems, ACM SIGPLAN Notices, v.38 n.7, July
Richard E. Ladner , James D. Fix , Anthony LaMarca, Cache performance analysis of traversals and random accesses, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.613-622, January 17-19, 1999, Baltimore, Maryland, United States
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
Gabriel Rivera , Chau-Wen Tseng, Data transformations for eliminating conflict misses, ACM SIGPLAN Notices, v.33 n.5, p.38-49, May 1998
J. Hu , M. Kandemir , N. Vijaykrishnan , M. J. Irwin, Analyzing data reuse for cache reconfiguration, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.4, p.851-876, November 2005
Somnath Ghosh , Margaret Martonosi , Sharad Malik, Automated cache optimizations using CME driven diagnosis, Proceedings of the 14th international conference on Supercomputing, p.316-326, May 08-11, 2000, Santa Fe, New Mexico, United States
Somnath Ghosh , Margaret Martonosi , Sharad Malik, Precise miss analysis for program transformations with caches of arbitrary associativity, ACM SIGOPS Operating Systems Review, v.32 n.5, p.228-239, Dec. 1998
Gayathri Venkataraman , Sartaj Sahni , Srabani Mukhopadhyaya, A blocked all-pairs shortest-paths algorithm, Journal of Experimental Algorithmics (JEA), 8,
Gabriel Rivera , Chau-Wen Tseng, Eliminating conflict misses for high performance architectures, Proceedings of the 12th international conference on Supercomputing, p.353-360, July 1998, Melbourne, Australia
I. Kadayif , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , J. Ramanujam, Morphable Cache Architectures: Potential Benefits, ACM SIGPLAN Notices, v.36 n.8, p.128-137, Aug. 2001
Gabriel Rivera , Chau-Wen Tseng, Locality optimizations for multi-level caches, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.2-es, November 14-19, 1999, Portland, Oregon, United States
A. Ya. Kalinov , A. L. Lastovetsky , I. N. Ledovskikh , M. A. Posypkin, Compilation of Vector Statements of C[] Language for Architectures with Multilevel Memory Hierarchy, Programming and Computing Software, v.27 n.3, p.111-122, May-June 2001
Alexandre Farcy , Olivier Temam, Improving single-process performance with multithreaded processors, Proceedings of the 10th international conference on Supercomputing, p.350-357, May 25-28, 1996, Philadelphia, Pennsylvania, United States
Gabriel Rivera , Chau-Wen Tseng, Tiling optimizations for 3D scientific computations, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.32-es, November 04-10, 2000, Dallas, Texas, United States
Lakshminarayanan Renganarayana , Sanjay Rajopadhye, A Geometric Programming Framework for Optimal Multi-Level Tiling, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.18, November 06-12, 2004
Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: a compiler framework for analyzing and tuning memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.703-746, July 1999
Chung-hsing Hsu , Ulrich Kremer, A Quantitative Analysis of Tile Size Selection Algorithms, The Journal of Supercomputing, v.27 n.3, p.279-294, March 2004
Anthony LaMarca , Richard Ladner, The influence of caches on the performance of heaps, Journal of Experimental Algorithmics (JEA), 1, p.4-es, 1996
Kathryn S. McKinley , Olivier Temam, A quantitative analysis of loop nest locality, ACM SIGPLAN Notices, v.31 n.9, p.94-104, Sept. 1996
Hans Vandierendonck , Koen De Bosschere, Highly accurate and efficient evaluation of randomising set index functions, Journal of Systems Architecture: the EUROMICRO Journal, v.48 n.13-15, p.429-452, May
Xavier Vera , Nerina Bermudo , Josep Llosa , Antonio Gonzlez, A fast and accurate framework to analyze and optimize cache memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.2, p.263-300, March 2004
Johann Blieberger , Thomas Fahringer , Bernhard Scholz, Symbolic Cache Analysis for Real-Time Systems, Real-Time Systems, v.18 n.2-3, p.181-215, May 2000
Jingling Xue , Xavier Vera, Efficient and Accurate Analytical Modeling of Whole-Program Data Cache Behavior, IEEE Transactions on Computers, v.53 n.5, p.547-566, May 2004
Ismail Kadayif , Mahmut Kandemir, Quasidynamic Layout Optimizations for Improving Data Locality, IEEE Transactions on Parallel and Distributed Systems, v.15 n.11, p.996-1011, November 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
numerical codes;performance evaluation;data locality;cache interferences or conflicts;modeling