Randomized Cache Placement for Eliminating Conflicts.
AbstractApplications with regular patterns of memory access can experience high levels of cache conflict misses. In shared-memory multiprocessors conflict misses can be increased significantly by the data transpositions required for parallelization. Techniques such as blocking which are introduced within a single thread to improve locality, can result in yet more conflict misses. The tension between minimizing cache conflicts and the other transformations needed for efficientparallelization leads to complex optimization problems for parallelizing compilers. This paper shows how the introduction of a pseudorandom element into the cache index function can effectively eliminate repetitive conflict misses and produce a cache where miss ratio depends solely on working set behavior. We examine the impact of pseudorandom cache indexing on processor cycle times and present practical solutions to some of the major implementation issues for this type of cache. Our conclusions are supported by simulations of a superscalar out-of-order processor executing the SPEC95 benchmarks, as well as from cache simulations of individual loop kernels to illustrate specific effects. We present measurements of Instructions committed Per Cycle (IPC) when comparing the performance of different cache architectures on whole-program benchmarks such as the SPEC95 suite.
Introduction
If the upward trend in processor clock frequencies during
the last ten years is extrapolated over the next ten years,
we will see clock frequencies increase by a factor of twenty
during that period [1]. However, based on the current 7%
per annum reduction in DRAM access times [2], memory
latency can be expected to reduce by only 50% in the next
ten years. This potential ten-fold increase in the distance
to main memory has serious implications for the design of
future cache-based memory hierarchies as well as for the
architecture of memory devices themselves.
Each block of main memory can be placed in exactly
one set of blocks in cache. The chosen set is determined
by the indexing function. Conventional caches typically
extract a field of m bits from the address and use this to
select one block from a set of 2 m . Whilst easy to imple-
ment, this indexing function is not robust. The principal
weakness is its susceptibility to repetitive conflict misses.
For example, if C is the number of cache sets and B is
the block size, then addresses A 1 and A 2 map to the same
cache set if j A 1 =B j C =j A 2 =B j C . If A 1 and A 2 collide
on the same cache set, then addresses A 1
A 2 +k also collide in cache, for any integer k , except when
There are two common
cases when this happens. Firstly, when accessing a stream
of addresses fA collides with A i+k ,
then there may be up to m\Gammak conflict misses in this stream.
Secondly, when accessing elements of two distinct arrays b 0
collides with b 1 [j], then b 0 [i+k] collides with
under the conditions outlined above. Set-associativity
can help to alleviate such conflicts, but is not
an effective solution for repetitive and regular conflicts.
One of the best ways to control locality in dense matrix
computations with large data structures is to use a tiled (or
algorithm. This is effectively a re-ordering of
the iteration space which increases temporal locality. How-
ever, previous work has shown that the conflicts introduced
by tiling can be a serious problem [3]. In practice, until
now, this has meant that compilers which tile loop nests
really ought to compute the maximal conflict-free tile size
for given values of B, major array dimension N and cache
capacity C. Often this will be too small to make it worth-while
tiling a loop, or perhaps the value of N will not be
known at compile time. Gosh et al. [4] present a framework
for analyzing cache misses in perfectly-nested loops with
affine references. They develop a generic technique for determining
optimum tile sizes, and methods for determining
array padding sizes to avoid conflicts. These methods require
solutions to sets of linear Diophantine equations and
depend upon there being sufficient information at compile
time to find such solutions.

Table

I highlights the problem of conflict misses with
reference to the SPEC95 benchmarks. The programs were
compiled with the maximum optimization level and instrumented
with the atom tool [5]. A data cache similar to
the first-level cache of the Alpha 21164 microprocessor was
simulated: 8 KB capacity, 32-byte lines, write-through and
no write allocate. For each benchmark we simulated the
first 2 operations. Because of the no-write-allocate
feature, the tables below refer only to load operations.

Table

I shows the miss ratio for the following cache or-
ganizations: direct-mapped, two-way associative, column-
associative [6], victim cache with four victim lines [7], and
two-way skewed-associative [8], [9].
Of these schemes, only the two-way skewed-associative
cache uses an unconventional indexing scheme, as proposed
by its author. For comparison, the miss ratio of a fully-associative
cache is shown in the penultimate column. The
miss ratio difference between a direct-mapped cache and
that of a fully-associative cache is shown in the right-most
column of table I, and represents the direct-mapped conflict
miss ratio (CMR) [2]. In the case of hydro2d and apsi
some organizations exhibit lower miss ratios than a fully-associative
cache, due to sub-optimality of lru replacement
in a fully-associative cache for these particular programs.
Effectively, the direct-mapped conflict miss ratio represents
DM 2W CA VC SA FA CMR
tomcatv 53.8 48.1 47.0 26.6 22.1 12.5 41.3
su2cor 11.0 9.1 9.3 9.5 9.6 8.9 2.1
hydro2d 17.6 17.1 17.2 17.0 17.1 17.5 0.1
mgrid 3.8 3.6 4.2 3.7 4.1 3.5 0.3
applu 7.6 6.4 6.5 6.9 6.7 5.9 1.7
turb3d 7.5 6.5 6.4 7.0 5.4 2.8 4.7
apsi 15.5 13.3 13.4 10.7 11.5 12.5 3.0
fpppp 8.5 2.7 2.7 7.5 2.2 1.7 6.8
wave 31.8 31.7 30.7 20.1 16.8 13.9 17.9
go 13.4 8.2 8.6 10.9 7.5 4.8 8.6
gcc 10.6 7.2 7.3 8.6 6.6 5.3 5.3
compress 17.1 15.8 16.3 16.2 14.3 13.0 4.1
li 8.6 5.4 5.5 7.2 4.9 3.8 4.8
ijpeg 4.1 3.3 3.1 2.3 1.9 1.2 2.9
perl 10.7 7.3 7.5 9.3 6.9 5.2 5.5
vortex 5.3 2.7 2.7 3.8 1.8 1.4 3.9
Ave
Ave (Int) 9.22 6.44 6.67 7.67 5.66 4.42 4.80
Average 15.9 13.8 13.6 11.3 8.66 6.80 9.14


I
Cache miss ratios for direct-mapped (DM), 2-way
set-associative (2W), column-associative (CA), victim cache
(VC), 2-way skewed associative (SA), and fully-associative
organizations. Conflict miss ratio (CMR) is also shown.
the target reduction in miss ratio that we hope to achieve
through improved indexing schemes. The other type of
misses, compulsory and capacity, will remain unchanged
by the use of randomized indexing schemes.
As expected, the improvement of a 2-way set-associative
cache over a direct-mapped cache is rather low. The
column-associative cache provides a miss ratio similar to
that of a two-way set-associative cache. Since the former
has a lower access time but requires two cache probes to
satisfy some hits, any choice between these two organizations
should take into account implementation parameters
such as access time and miss penalty. The victim
cache removes many conflict misses and outperforms a four-way
set-associative cache. Finally, the two-way skewed-
associative cache offers the lowest miss ratio. Previous
work has shown that it can be significantly more effective
than a four-way conventionally-indexed set-associative
cache [10].
In this paper we investigate the use of alternative index
functions for reducing conflicts and discuss some practical
implementation issues. Section II introduces the alternative
index functions, and section III evaluates their conflict
avoidance properties. In section IV we discuss a number
of implementation issues, such as the effect of novel indexing
functions on cache access time. Then, in section V,
we evaluate the impact of the proposed indexing scheme
on the performance of a dynamically-scheduled processor.
Finally, in section VI, we draw conclusions from this study.
II. Alternative indexing functions
The aim of this paper is to show how alternative cache
organizations can eliminate repetitive conflict misses. This
is analogous to the problem of finding an efficient hashing
function. For large secondary or tertiary caches it may
be possible to use the virtual address mapping to adjust
the location of pages in cache, as suggested by Bershad et
al. [11], thus avoiding conflicts dynamically. However, for
small first-level caches this effect can only be achieved by
using an alternative cache index function.
In the field of interleaved memories it is well known that
bank conflicts can be reduced by using bank selection functions
other than the simple modulo-power-of-two. Lawrie
and Vora proposed a scheme using prime-modulus functions
[12], Harper and Jump [13], and Sohi [14] proposed
skewing functions. The use of xor functions in parallel
memory systems was proposed by Frailong et al. [15], and
other pseudo-random functions were proposed by Raghavan
and Hayes [16], and Rau et al. [17], [18]. These schemes
each yield a more or less uniform distribution of requests
to banks, with varying degrees of theoretical predictability
and implementation cost. In principle each of these
schemes could be used to construct a conflict-resistant
cache by using them as the indexing function. However,
in cache architectures two factors are critical; firstly, the
chosen indexing function must have a logically simple im-
plementation, and secondly we would like to be able to
guarantee good behavior on all regular address patterns -
even those that are pathological under a conventional index
function.
In the commercial domain, the IBM 3033 [19] and the
Amdahl 470 [20] made use of xor-mapping functions in
order to index the TLB. The first generation HP Precision
Architecture processors [21] also used a similar technique.
The use of pseudo-random cache indexing has been suggested
by other authors. For example, Smith [22] compared
a pseudo-random placement against a set-associative place-
ment. He concluded that random indexing had a small advantage
in most cases, but that the advantages were not
significant. In this paper we show that for certain workloads
and cache organizations, the advantages can be very
large.
Hashing the process id with the address bits in order
to index the cache was evaluated in a multiprogrammed
environment by Agarwal in [23]. Results showed that this
scheme could reduce the miss ratio.
Perhaps the most well-known alternative cache indexing
scheme is the class of bitwise exclusive-OR functions proposed
for the skewed associative cache [8]. The bitwise xor
mapping computes each bit of the cache index as either one
bit of the address or the xor of two bits. Where two such
mappings are required different groups of bits are chosen
for xor-ing in each case. A two-way skewed-associative
cache consists of two banks of the same size that are accessed
simultaneously with two different hashing functions.
Not only does the associativity help to reduce conflicts but
the skewed indexing functions help to prevent repetitive
conflicts from occurring.
The polynomial modulus function was first applied to
cache indexing in [10]. It is best described by first considering
the unsigned integer address A in terms of its binary
representation
This is interpreted as the polynomial
defined over the field GF(2). The binary
representation of the m-bit cache index R is similarly
defined by the GF(2) polynomial R(x) of order less than
m such that Effectively R(x) is
is an irreducible polynomial
of order m and P (x) is such that x i mod P (x) generates
all polynomials of order lower than m. The polynomials
that fulfil the previous requirements are called Ipoly poly-
nomials. Rau showed how the computation of R(x) can be
accomplished by the vector-matrix product of the address
and an n \Theta m matrix H of single-bit coefficients derived
from P (x) [18]. In GF(2), this product is computed by
a network of and and xor gates, and if the H-matrix is
constant the and gates can be omitted and the mapping
then requires just m xor gates with fan-in from 2 to n. In
practice we may reduce the number of input address bits
to the polynomial mapping function by ignoring some of
the upper bits in A. This does not seriously degrade the
quality of the mapping function.
Ipoly mapping functions have been studied previously
in the context of stride-insensitive interleaved memories
(see [17], [18]), and have certain provable characteristics of
significant value for cache indexing. In [24] it was demonstrated
that a skewed Ipoly cache indexing scheme shows a
higher degree of conflict resistance than that exhibited by
conventional set-associativity or other (non-Ipoly) xor-based
mapping functions. Overall, the skewed-associative
cache using Ipoly mapping and a pure lru replacement
policy achieved a miss ratio within 1% of that achieved by
a fully-associative cache. Given the advantage of an Ipoly
function over the bitwise xor function, all results presented
in this paper use the Ipoly indexing scheme.
III. Evaluation of Conflict Resistance
The performance of both the integer and floating-point
SPEC95 programs has been evaluated for column-
associative, two-way set-associative (2W) and two-way
skewed-associative organizations using Ipoly indexing
functions. In all cases a single-level cache is assumed. The
miss ratios of these configurations are shown in table II.
Given a conventional indexing function, the direct-mapped
(DM) and fully-associative organizations display
respectively the lowest and the highest degrees of
conflict-resistance of all possible cache architectures. As
such they define the bounds within which novel indexing
schemes should be evaluated. Their miss ratios are shown
in the right-most two columns of table II.
The column-associative cache has access-time characteristics
similar to a direct-mapped cache but has some degree
of pseudo-associativity - each address can map to one of
Ipoly indexing mod 2 k
col. assoc. 2-way skewed indexing
spl lru 2W plru lru FA DM
su2cor 10.5 9.1 9.9 9.4 9.4 8.9 11.0
hydro2d 17.6 17.2 17.1 17.0 17.1 17.5 17.6
mgrid 5.1 4.2 3.8 4.5 4.1 3.5 3.8
applu 7.3 6.5 6.9 6.8 6.4 5.9 7.6
turb3d 8.1 6.0 4.8 4.5 4.2 2.8 7.5
apsi 12.2 11.2 11.4 11.0 10.6 12.5 15.5
fpppp 4.0 2.7 2.8 2.1 2.3 1.7 8.5
wave ? 14.6 13.8 14.2 13.9 13.7 13.9 31.8
go 9.6 6.6 8.6 7.5 6.7 4.8 13.4
gcc 8.2 6.3 7.2 6.7 6.1 5.3 10.6
compress 14.5 13.5 13.7 13.9 13.4 13.0 17.1
li 5.5 4.5 6.1 4.9 4.5 3.8 8.6
ijpeg 1.8 1.3 1.7 1.5 1.4 1.2 4.1
perl 8.5 6.7 8.8 7.1 6.4 5.2 10.7
vortex 2.7 1.7 2.0 1.8 1.6 1.4 5.3
Ave
Ave (Int) 6.68 5.22 6.26 5.55 5.09 4.42 9.22
Ave ? 13.2 11.4 12.3 11.6 11.3 11.4 47.3
Average 8.77 7.39 7.99 7.47 7.14 6.80 15.9


II
Miss ratios for Ipoly indexing on SPEC95 benchmarks.
two locations in the cache, but initially only one is probed.
The column labelled spl represents a cache which swaps
data between the two locations to increase the percentage
of a hit on the first probe. It also uses a realistic pseudo-lru
replacement policy. The cache reported in the column
labelled lru does not swap data between columns and uses
an unrealistic pure lru replacement policy [10].
It is to be expected that a two-way set-associative cache
will be capable of eliminating many random conflicts. How-
ever, a conventionally-indexed set-associative cache is not
able to eliminate pathological conflict behavior as it has
limited associativity and a naive indexing function. The
performance of a two-way set-associative cache can be improved
by simply replacing the index function, whilst retaining
all other characteristics. Conventional lru replacement
can still be used, as the indexing function has no impact
on replacement for this cache organization. For two
programs the two-way Ipoly cache has a lower miss ratio
than a fully-associative cache. This is again due to the
sub-optimality of lru replacement in the fully-associative
cache, and is a common anomaly in programs with negligible
conflict misses.
The final cache organization shown in table II is the
two-way skewed-associative cache proposed originally by
Seznec [8]. In its original form it used two bitwise
xorindexing functions. Our version uses Ipoly indexing
functions, as proposed in [10] and [24]. In this case two
distinct Ipoly functions are used to construct two distinct
cache indices from each address. Pure lru is difficult to implement
in a skewed-associative cache, so here we present
results for an cache which uses a realistic pseudo-lru policy
(labelled plru) and a cache which uses an unrealistic
pure lru policy (labelled lru). This organization produces
the lowest conflict miss ratio, down from 4.8% to 0.67% for
SPECint, and from 12.61% to 0.07% for SPECfp.
It is striking that the performance improvement is dominated
by three programs (tomcatv, swim and wave). These
effectively exhibit pathological conflict miss ratios under
conventional indexing schemes. Studies by Olukotun et
al. [25], have shown that the data cache miss ratio in tomcatv
wastes 56% and 40% of available IPC in 6-way and
2-way superscalar processors respectively.
Tiling will often introduce extra cache conflicts, the elimination
of which is not always possible through software.
Now that we have alternative indexing functions that exhibit
conflict avoidance properties we can use these to avoid
these induced conflicts. The effectiveness of Ipoly indexing
for tiled loops was evaluated by simulating the cache
behavior of a variety of tiled loop kernels. Here we present
a small sample of results to illustrate the general outcome.

Figures

show the miss ratios observed in two tiled
matrix multiplication kernels where the original matrices
were square and of dimensions 171 and 256 respectively.
Tile sizes were varied from 2 \Theta 2 up to 16 \Theta 16 to show
the effect of conflicts occurring in caches that are direct-mapped
(a1), 2-way set-associative (a2), fully-associative
(fa) and skewed 2-way Ipoly (Hp-Sk). The tiled working
set divided by cache capacity measures the fraction of the
cache occupied by a single tile. Cache capacity is 8 KBytes,
with 32-byte lines.
For dimension 171 the miss ratio initially falls for all
caches as tile size increases. This is due to increasing
spatial locality, up to the point where self conflicts begin
to occur in the conventionally-indexed direct-mapped and
two-way set-associative caches. The fully-associative cache
suffers no self-conflicts and its miss ratio decreases monotonically
to less than 1% at 50% loading. The behavior of
the skewed 2-way Ipoly cache tracks the fully-associative
cache closely. The qualitative difference between the Ipoly
cache and a conventional two-way cache is clearly visible.
For dimension 256 the product array and the multiplicand
array are positioned in memory so that cross-conflicts
occur in addition to self-conflicts. Hence the direct-mapped
and 2-way set associative caches experience little spatial
locality. However, the Ipoly cache is able to eliminate
cross-conflicts as well as self-conflicts, and it again tracks
the fully-associative cache.
IV. Implementation Issues
The logic of the GF(2) polynomial modulus operation
presented in section II defines a class of hash functions
which compute the cache placement of an address by combining
subsets of the address bits using xor gates. This
means that, for example, bit 0 of the cache index may be
Working Set / Capacity
Miss
ratio
0% 10% 20% 30% 40% 50%
Hp-Sk
Fig. 1. Miss ratio versus cache loading for 171 \Theta 171 matrix multiply.
Working Set / Capacity
Miss
ratio
0% 10% 20% 30% 40% 50%
Fig. 2. Miss ratio versus cache loading for 256 \Theta 256 matrix multiply.
computed as the xor of bits 0, 11, 14, and 19 of the original
address. The choice of polynomial determines which
bits are included in each set. The implementation of such
a function for a cache with an 8-bit index would require
just eight xor gates with fan-in of 3 or 4.
Whilst this appears remarkably simple, there is more
to consider than just the placement function. Firstly, the
function itself uses address bits beyond the normal limit
imposed by typical minimum page size restriction. Sec-
ondly, the use of pseudo-random placement in a multi-level
memory hierarchy has implications for the maintenance of
Inclusion. In [24] we explain these two issues in more depth,
and show how the virtual-real two-level cache hierarchy
proposed by Wang et al. [26] provides a clean solution to
both problems.
A cache memory access in a conventional organization
normally computes its effective address by adding two reg-
isters, or a register plus a displacement. Ipoly indexing
implies additional circuitry to compute the index from the
effective address. This circuitry consists of several xor
gates that operate in parallel and therefore the total delay
is just the delay of one gate. Each xor gate has a number
of inputs that depend on the particular polynomial being
used. For the experiments reported in this paper the number
of inputs is never higher than 5. The xor gating required
by the Ipoly mapping may increase the critical path
length within the processor pipeline. However, any delay
will be short since all bits of the index can be computed
in parallel. Moreover, we show later that even if this additional
delay induces a full cycle penalty in the cache access
time, the Ipoly mapping provides a significant overall performance
improvement. Memory address prediction can be
also used to avoid the penalty introduced by the xor delay
when it lengthens the critical path. Memory addresses have
been shown to be highly predictable. For instance, in [27]
it was shown that the addresses of about 75% of the dynamically
executed memory instructions from the SPEC95
suite can be predicted with a simple tabular scheme which
tracks the last address produced by a given instruction and
its last stride. A similar scheme, that could be used to give
an early prediction of the line that is likely to be accessed
by a given load instruction, is outlined below.
The processor incorporates a table indexed by the instruction
address. Each entry stores the last address and
the predicted stride for some recently executed load in-
struction. In the fetch stage, this table is accessed with
the program counter. In the decode stage, the predicted
address is computed and the xor functions are performed
to compute the predicted cache line. This can be done in
one cycle since the xor can be performed in parallel with
the computation of the most-significant bits of the effeec-
tive address. When the instruction is subsequently issued
to the memory unit it uses the predicted line number to access
the cache in parallel with the actual address and line
computation. If the predicted line turns out to be incor-
rect, the cache access is repeated with the actual address.
Otherwise, the data provided by the speculative access can
be loaded into the destination register.
A number of previous papers have suggested address prediction
as a means to reduce memory latency [28], [29],
[30], or to execute memory instructions and their dependent
instructions speculatively [31], [27], [32]. In the case
of a miss-speculation, a recovery mechanism similar to that
used by branch prediction schemes is then used to squash
miss-speculated instructions.
V. Effect of Ipoly indexing on IPC
In order to verify the impact of polynomial mapping
on realistic microprocessor architectures we have developed
a parametric simulator for a four-way superscalar
processor with out-of-order execution. Table III summarizes
the functional units and their latencies used in these
experiments. The reorder buffer contained 32 entries, and
there were two separate physical register files (FP and In-
teger), each with 64 physical registers. The processor had
a lockup-free data cache [33] that allowed 8 outstanding
misses to different cache lines. Cache capacities of 8 KB
and were simulated with 2-way associativity and
32-byte lines. The cache was write-through and no-write-
allocate. The cache had two ports, each with a two-cycle
time and a miss penalty of 20 cycles. This was connected
by a 64-bit data bus to an infinite level-two cache.
Data dependencies through memory were speculated using
a mechanism similar to the arb of the Multiscalar [34]
and the HP PA-8000 [35]. A branch history table with 2K
entries and 2-bit saturating counters was used for branch
prediction.
Functional unit Latency Repeat rate
simple FP 4 1


III
Functional units and instruction latencies
The memory address prediction scheme was implemented
by a direct-mapped table with 1K entries, indexed
by instruction address. To reduce cost the entries were
not tagged, although this increases interference in the ta-
ble. Each entry contained the last effective address of the
most recent load instruction to index into that table entry,
together with the last observed stride. In addition, each
entry contained a 2-bit saturating counter to assign confidence
to the prediction. Only when the most-significant
bit of the counter is set would the prediction be considered
correct. The address field was updated for each new reference
regardless of the prediction. However, the stride field
was updated only when the counter went below
after two consecutive mispredictions.

Table

IV shows the IPC and miss ratios for six configurations
1 . All IPC averages are computed using an equally-weighted
harmonic mean. The baseline configuration is an
8 KB cache with conventional indexing and no address prediction
(np, 3rd column). The average IPC for this configuration
is 1.27 from an average miss ratio of 16.53%. With
Ipoly indexing the average miss ratio falls to 9.68%. If the
xor gates are not in the critical path IPC rises to 1.33 (nx,
5th column). Conversely, if the xor gates are in the critical
path, and a one cycle penalty in the cache access time is
assumed, the resulting IPC is 1.29 (wx, 6th column). How-
ever, if memory address prediction is then introduced (wp,
7th columnn) IPC is the same as for a cache without the
xor gates in the critical path (nx). Hence, the memory address
prediction scheme can offset the penalty introduced
by the additional delay of the xor gates when they are in
the critical path, even under the conservative assumption
that whole cycle of latency is added to each load instruc-
tion. Finally, table IV also shows the performance of a
set-associative cache without Ipoly indexing
1 For each configuration we simulated 10 8 instructions after skipping
the first 2 \Theta 10 9 .
(2nd column). Notice that the addition of Ipoly indexing
to an 8 KB cache yields over 60% of the IPC increase that
can be obtained by doubling the cache size.
indexing Ipoly indexing
su2cor y 1.28 1.24 1.26 1.24 1.21 1.25
hydro2d y 1.14 1.13 1.15 1.13 1.11 1.15
mgrid y 1.63 1.61 1.63 1.57 1.55 1.59
applu y 1.51 1.50 1.53 1.50 1.46 1.52
turb3d y 1.85 1.80 1.82 1.81 1.78 1.82
apsi y 1.13 1.08 1.09 1.08 1.07 1.09
fpppp y 2.14 2.00 2.00 1.98 1.93 1.94
wave ? 1.37 1.26 1.28 1.51 1.48 1.54
go y 1.00 0.87 0.88 0.87 0.83 0.84
compress y 1.13 1.12 1.13 1.11 1.07 1.10
li y 1.40 1.30 1.32 1.33 1.26 1.31
ijpeg y 1.31 1.28 1.28 1.29 1.28 1.30
perl y 1.45 1.26 1.27 1.24 1.19 1.21
vortex y 1.39 1.27 1.28 1.30 1.25 1.27
Ave
Ave (Int) 1.29 1.19 1.20 1.20 1.15 1.17
Ave ? 1.28 1.11 1.13 1.46 1.42 1.49
Ave y 1.38 1.30 1.32 1.30 1.27 1.30
Average 1.36 1.27 1.28 1.33 1.29 1.33


IV
Comparative IPC measurements (simulated).
These IPC measurements exhibit small absolute differ-
ences, but this is because the benefit of Ipoly indexing
is perceived by a only small subset of the benchmark pro-
grams. Most programs in SPEC95 exhibit low conflict miss
ratios. In fact the SPEC95 conflict miss ratio for an 8 KB
2-way set-associative cache is less than 4% for all programs
except tomcatv, swim and wave5. The two penultimate
rows of table IV show independent IPC averages for the
benchmarks with high conflict miss ratios (Ave ?), and
those with low conflict miss ratios (Ave y). This highlights
the ability of polynomial mapping to reduce the miss ratio
and significantly boost the performance of problem cases.
One can see that the polynomial mapping provides a significant
27% improvement in IPC for the three bad programs
even if the xor gates are in the critical path and memory
address prediction is not used. With memory address
prediction Ipoly indexing yields an IPC improvement of
33% compared with that of a conventional cache of the
same capacity, and 16% higher than that of a conventional
cache with twice the capacity. Notice that the polynomial
mapping scheme with prediction is even better than the
organization without prediction where the xor gates do
not extend the critical path. This is due to the fact that
the memory address prediction scheme reduces by one cycle
the effective cache hit time when the predictions are
correct, since the address computation is overlapped with
the cache access (the computed address is used to verify
that the prediction was correct). However, the main benefits
observed come from the reduction in conflict misses.
To isolate the different effects we have also simulated an
organization with the memory address prediction scheme
and conventional indexing for an 8 KB cache (wp, column
4). If we compare the IPC of this organization with that in
column 3, we see that the benefits of the memory address
prediction scheme due solely to the reduction of the hit time
are almost negligible. This confirms that the improvement
observed in the Ipoly indexing scheme with address prediction
derives from the reduction in conflict misses. The
averages for the fifteen programs which exhibit low levels
of conflict misses show a small (1.7%) deterioration in average
IPC when Ipoly indexing is used and the xor gates
are in the critical path. This is due to a slight increase in
the average hit time rather than an overall increase in miss
ratio (which on average falls by 2%). For these programs
the reduction in aggregated miss penalty does not outweigh
the slight extension in critical path length.
VI. Conclusions
In this paper we have discussed the problem of cache conflict
misses and surveyed the options for reducing or eliminating
those conflicts. We have described pseudo-random
indexing schemes based on polynomial modulus functions,
and have shown them to be robust enough to virtually eliminate
the repetitive cache conflicts caused by bad strides
inherent in some SPEC95 benchmarks, as well as eliminating
those introduced into an application by the tiling of
loop nests.
We have highlighted the major implementation issues
that arise from the use of such novel indexing schemes.
For example, Ipoly indexing uses more address bits than
a conventional cache to compute the cache index. Also,
the use of different indexing functions at level-1 and level-2
caches results in the occasional eviction at level-1 simply
to maintain Inclusion. We have explained that both of
these problems can be solved using a two-level virtual-real
cache hierarchy. Finally, we have proposed a memory address
prediction scheme to avoid the penalty due to the
small potential delay in the critical path introduced by the
pseudo-random indexing function.
Detailed simulations of an out-of-order superscalar processor
have demonstrated that programs with significant
numbers of conflict misses in a conventional 8 KB 2-way
skewed-associative cache perceive IPC improvements of
33% (with address prediction) or 27% (without address
prediction). This is up to 16% higher than the IPC improvements
obtained simply by doubling the cache capac-
ity. Furthermore, from the programs we analyzed, those
that do not experience significant conflict misses on average
see only a 1.7% reduction in IPC when Ipoly indexing
appears on the critical path for computing the effective ad-
dress, and address prediction is used. If the indexing logic
does not appear on the critical path no deterioration in
overall average performance is experienced by those programs

We believe the key contribution of pseudo-random indexing
is the resulting predictability of cache behavior. In
our experiments we found that Ipoly indexing reduces the
standard deviation of miss ratios across SPEC95 from 18.49
to 5.16. This could be beneficial in real-time systems where
unpredictable timing, caused by the possibility of pathological
miss ratios, presents problems. If conflict misses
are eliminated, the miss ratio depends solely on compulsory
and capacity misses, which in general are easier to
predict and control. Conflict avoidance could also be beneficial
when iteration-space tiling is used to improve data
locality.
VII.

Acknowledgments

This work was supported in part by the European Commission
esprit project 24942, by the British Council
(grant 1016), and by the Spanish Ministry of Education
(Acci'on Integrada Hispano-Brit'anica 202 CYCIT TIC98-
0511). The authors would like to express their thanks to
Jose Gonz'alez and Joan Manuel Parcerisa for their help
with the simulation software, and to the anonymous referees
for their helpful comments.



--R

"The national technology roadmap for semiconductors,"
Computer Architecture: A Quantitative Approach.
"The cache performance and optimization of blocked algorithms,"
"Cache miss equations: An analytic representation of cache misses,"
"ATOM: A system for building customized program analysis tools,"
"Column-associative caches: A technique for reducing the miss rate of direct-mapped caches,"
"Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers,"
"A case for two-way skewed associative caches,"
"Skewed-associative caches,"
"Elimi- nating cache conflict misses through xor-based placement func- tions,"
"Avoiding cache conflict misses dynamically in large direct-mapped caches,"
"The prime memory system for array access,"
"Vector access performance in parallel memories,"
"Logical data skewing schemes for interleaved memories in vector processors,"
"xor-schemes: A flexible data organization in parallel memories,"
"On randomly interleaved memo- ries,"
"The Cydra 5 stride- insensitive memory system,"
"Pseudo-randomly interleaved memories,"

Amdahl Corp.
"Hardware design of the first HP Precision Architecture computers,"
"Cache memories,"
Analysis of Cache Performance for Operating Systems and Multiprogramming
"The design and performance of a conflict-avoiding cache,"
"The case for a single-chip multiprocessor,"
"Organization and performance of a two-level virtual-real cache hierarchy,"
"Speculative execution via address prediction and data prefetching,"
"Hardware support for hiding cache latency,"
"Streamlining data cache access with fast address calculation,"
"Zero-cycle loads: Microarchitecture support for reducing load latency,"
"Memory address prediction for data speculation,"
"The performance potential of data dependence speculation and collapsing,"
"Lockup-free instruction fetch/prefetch cache organi- zation,"
"ARB: A mechanism for dynamic reordering of memory references,"
"Advanced performance features of the 64-bit PA- 8000,"
--TR

--CTR
S. Bartolini , C. A. Prete, A proposal for input-sensitivity analysis of profile-driven optimizations on embedded applications, ACM SIGARCH Computer Architecture News, v.32 n.3, p.70-77, June 2004
K. Patel , E. Macii , L. Benini , M. Poncino, Reducing cache misses by application-specific re-configurable indexing, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.125-130, November 07-11, 2004
Hans Vandierendonck , Philippe Manet , Jean-Didier Legat, Application-specific reconfigurable XOR-indexing to eliminate cache conflict misses, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
Hans Vandierendonck , Koen De Bosschere, XOR-Based Hash Functions, IEEE Transactions on Computers, v.54 n.7, p.800-812, July 2005
Mathias Spjuth , Martin Karlsson , Erik Hagersten, Skewed caches from a low-power perspective, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy
Wang , Nelson Passos, Improving cache hit ratio by extended referencing cache lines, Journal of Computing Sciences in Colleges, v.18 n.4, p.118-123, April
G. E. Suh , L. Rudolph , S. Devadas, Dynamic Partitioning of Shared Cache Memory, The Journal of Supercomputing, v.28 n.1, p.7-26, April 2004
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
G. Edward Suh , Srinivas Devadas , Larry Rudolph, Analytical cache models with applications to cache partitioning, Proceedings of the 15th international conference on Supercomputing, p.1-12, June 2001, Sorrento, Italy
Rui Min , Yiming Hu, Improving Performance of Large Physically Indexed Caches by Decoupling Memory Addresses from Cache Addresses, IEEE Transactions on Computers, v.50 n.11, p.1191-1201, November 2001
S. Bartolini , C. A. Prete, Optimizing instruction cache performance of embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.4, p.934-965, November 2005
cache architectures;performance evaluation;conflict avoidance