Modeling set associative caches behavior for irregular computations.
While much work has been devoted to the study of cache behavior during the execution of codes with regular access patterns, little attention has been paid to irregular codes. An important portion of these codes are scientific applications that handle compressed sparse matrices. In this work a probabilistic model for the prediction of the number of misses on a K-way associative cache memory considering sparse matrices with a uniform or banded distribution is presented. Two different irregular kernels are considered: the sparse matrix-vector product and the transposition of a sparse matrix. The model was validated with simulations on synthetic uniform matrices and banded matrices from the Harwell-Boeing collection.
Introduction
Sparse matrices are in the kernel of many numerical appli-
cations. Their compressed storage [?], which permits both
operations and memory savings, generates irregular access
patterns. This fact reduces and makes hard to predict the
performance of the memory hierarchy. In this work a probabilistic
model for the prediction of the number of misses on
a K-way associative cache memory considering sparse matrices
with a uniform or banded distribution is presented.
We want to emphasize that an important body of the model
is reusable in different algebra kernels.
The most important approach to study cache behavior
has traditionally been the use of trace-driven simulations [?],
[?], [?] whose main drawback is the large amount of time
needed to process the traces. Another possibility is nowadays
provided by the performance monitoring tools of modern
microprocessors (built-in hardware counters), that make
This work was supported by the Ministry of Education and
Science (CICYT) of Spain under project TIC96-1125-C03, Xunta
de Galicia under Project XUGA20605B96, and E.U. Brite-Euram
Project BE95-1564
available data such as the number of cache misses. These
tools are obviously restricted to the evaluation of the specific
cache architectures for which they are available. Finally, analytical
models present the advantage that they reduce the
times for obtaining the estimations and make the parametric
analysis of the cache more flexible. Their weak point has
traditionally been their limited precision. Although some
models use parameters extracted from address traces [?],
more general analytical models have been developed that
require no input traces. While most of the previous works
focuse on dense algebra codes [?], [?], little attention has
been devoted to sparse kernels due to the irregular nature
of their access patterns. For example, [?] studies the self
interferences on the vector involved in the sparse matrix-vector
product on a direct-mapped cache without considering
interferences with other data structures and they do not
derive a general framework to model this kind of codes.
Nevertheless, as an example of the potential usability of
such types of models, we have modeled the cache behavior
of a common algebra kernel, the sparse matrix-vector
product, and a more complex one, the transposition of a
sparse-matrix. This last code includes different access patterns
and presents an important degree of data reusability
for certain vectors.
The remainder of the paper is organized as follows: Section
?? presents the basic model parameters and concepts.
Sparse matrix-vector product cache behavior is modeled in
Section ??, while Section ?? is dedicated to the modeling
of the transposition of a sparse matrix. Both models are
extended to banded matrices in Section ??. In Section ??
the models are verified and the cache behavior they depict
is studied. Finally, Section ?? concludes the paper.
2 Probabilistic model
Our model considers three types of misses: intrinsic misses,
and self and cross interferences. An intrinsic miss takes place
the first time a memory block is accessed. Self interferences
are misses on lines that have been previously replaced in
the cache by another line that belongs to the same program
vector. Cross interferences refer to misses on lines that have
been replaced between two consecutive references by lines
belonging to other vectors.
In direct mapped caches each memory line is always
mapped to the same cache line, so replacements take place
whenever accesses to two or more memory lines mapped to
the same cache line take place. However, in K-way assso-
ciative caches lines are mapped to a set of K cache lines.
In this case the line to be replaced is selected following a
Cache size in words
Ls Line size in words
Nc Number of cache lines (Cs=Ls )
Nnz Number of non zero elements of the sparse matrix
M Number of rows of the sparse matrix
N Number of columns of the sparse matrix
fi Average of non zeros elements per row (Nnz=M)
K Associativity
Nk Number of cache sets (Nc=K)
pn Probability that a position in the sparse
matrix contains a non zero element (fi=N)
Probability that there is at least one entry in a group
of Ls positions of the sparse matrix
r size of an integer
size of a real

Table

1: Notation used.
random or a LRU criterium. Our model is oriented to K-way
associative caches with LRU replacement. In order to
replace a line in a cache of this kind, K different new lines
mapped to the same set must be accessed before reusing the
line considered. When the behavior is that of direct
mapped caches.
The replacement probability for a given line grows with
the number of lines affected by the accesses between two
consecutive references to it, and the way these lines are distributed
among the different sets. This depends on the memory
location of the vectors to be accessed, as it determines
the set corresponding to a given line. We handle the areas
covered by the accesses to a given program vector V as an
area vector, S is the ratio
of sets that have received K or more lines of vector V, while
is the ratio of sets that have received
lines from V. This means that S Vi is the ratio of cache sets
that require i accesses to new different lines to replace all
the lines they contained when the access to V started.
Besides K, the number of lines in a set, there is a number
of additional parameters our model considers. They are
depicted in Table ??. By word we mean the logical access
unit, this is to say, the size of a real or an integer. We have
chosen the size of a real, but the model is totally scalable.
A uniform distribution in an M \Theta N sparse matrix with
Nnz non zero elements (entries) allows us to state the following
considerations: the number of entries in a group of
Ls positions belongs to a binomial B(Ls ; pn) where pn is the
probability of a given position of the matrix containing an
entry, that is, This way, the probability of generating
an access to a given line of the vector times which we
are multiplying the sparse matrix is p, which is calculated
as the table shows.
2.1 Area vectors union
An essential issue is the way we obtain the total area vector.
We add the area vectors corresponding to the accesses to
the different program vectors. Given two area vectors S
corresponding
to the accesses to vectors U and V, we define the union area
vector
where is the ratio of sets that have
received lines from these two vectors, and (S U [S V )0
U
U V00110011
U
U

Figure

1: Area vectors corresponding to the accesses to a
vector U and a vector V in a cache with N
and resulting total area vector.
l

Figure

2: Area vectors corresponding to a sequential access
and an access to lines with a uniform reference probability
of a vector covering 11 lines in a cache with N
2.
is the ratio of sets that have received K or more lines. Figure
?? illustrates the area vector union process. From now
on the symbol [ will be used to denote the vector union op-
eration. This method makes no assumptions on the relative
positions of the program vectors in memory, as it is based in
the addition as independent probabilities of the area ratios.
2.2 Sequential access
The calculation of the area vector depends on the access
pattern of the corresponding program vector, so we define
an area vector function for each access pattern we find in
the codes analyzed. For example, the area vector for the
access to n consecutive memory positions is
(2)
is the average number of lines
that fall into each set. If l - K then
as all of the sets receive an average of K or more
lines. The term Ls added to n stands for the average
extra words brought to the cache in the first and last lines
of the access.
2.3 Access to lines with a uniform reference probability
The area vector for an access to an n word vector where
each one of the cache lines into which it is divided has the
same probability P l of being accessed may be calculated as
li (n; P l
li (n; P l
being B(n,p) the binomial
distribution 1 and )eg. An example
for this access and the sequential access is presented
We define the binomial distribution on a non integer number of
elements

Figure

3: Correspondence between the location of the non
zeros in a banded matrix to be transposed and the groups
where they are moved to in the vectors that define the output
matrix.
in

Figure

??. In the case of k accesses of this type, the area
vector is S k
l (n; P l
2.4 Access to groups of elements with a uniform reference
probability
In the transposition of a sparse matrix we find the case of
a vector of n words divided into groups of t words where
the probability Pg of accessing each group is the same. It
happens in the main loop of the algorithm, which accesses
the non zeros of the input matrix per rows (sequentially)
moving them to the group corresponding to the column they
belong to in the vectors that define the output matrix. Each
group has as many positions as non zeros has the associated
column in the input matrix. Only one of the lines of the
group is accessed during the processing of each row of the
input matrix, and consecutive accesses to the same group
address consecutive memory positions. The area covered by
an access of this type is given by
Sg (n; t; Pg
ae
where if t - Ls , each line of the vector has a uniform probability
being accessed. Whereas if t ? Ls
this probability is Ls=tPg .
As in the case of S l , Sg may be extended in order to
calculate the area covered by k accesses, S k
(n; t; p). Due to
space limitations we only show the main expressions of our
model; all of them can be found in [?].
2.5 Access to areas displaced with successive references
The model may be extended to consider the case in which
the area with some access probability is displaced with successive
references. Let S gb (b; t; Pg ) be the area vector corresponding
to an access to b consecutive groups of t elements
with a uniform probability per group Pg of accessing one
and only one of the elements of the group. Its value is given
by Sg (b \Delta t; t; Pg ).
We define S k
gb (b; t; Pg ) as the area vector corresponding
to k accesses of this type. In the banded sparse matrix
transposition case each one of the k accesses corresponds to
the processing of a new row of the sparse matrix, as in each
row a column leaves the band (to the left), which makes the
probability of accessing the group corresponding to it null,
and a new one joins the band to the right, thus adding its
group to the set of groups that may be accessed during the
processing of the row. The situation is depicted in Figure ??
with 5: during the processing of the first row, groups 1
DO J=R(I), R(I+1)-1
ENDDO
ENDDO

Figure

4: Sparse matrix-vector product.
to 5 may be accessed if there is a non zero in the associated
column, while in the second row these sets are 2 to 6, and
in the third only sets 3-7 may be accessed.
The accesses following this pattern cover three adjacent
areas:
1. A set of lines with a growing
access probability (Area 1 in Figure ??).
2. A set of lines with a constant access
probability (Area 2 in Figure ??).
3. A last set symmetric to the first one, of the same size,
and with a decreasing access probability (Area 3 in

Figure

??).
Once the average access probabilities for the lines of this
three consecutive areas are known (see [?]), it only remains
to combine them to obtain the corresponding area vector.
2.6 Number of lines in a vector competing for the same
cache set
Finally, for the calculation of the self interference probability
a function to compute the average number of lines with
which a line of the vector competes for the same cache set
is needed. This function is defined as
ae
is the average number of lines of the
vector mapped to the same cache set.
3 Modeling the sparse matrix-vector product
The code for this sparse matrix algebra kernel is shown in

Figure

??. The format used to store the sparse matrix is the
Compressed Row Storage (CRS) [?]: A contains the sparse
matrix entries, C stores the column of each entry, and R indicates
in which point of A and C a new row of the sparse
matrix starts, which permits knowing the number of entries
per row. These three vectors and D, the destination vector
of the product, present a purely sequential access, thus
most of the misses on them are intrinsic. There are no self
interferences and very few misses due to cross interferences
(specially taking into account that we are considering a K-way
associate cache). Therefore the number of misses for
these vectors is calculated as the number of cache lines they
cover (intrinsic misses).
Nevertheless vector X suffers a series of indirect accesses
dependent on the location of the entries in the sparse ma-
trix, as it is addressed from the value of C(J). The number
of misses accessing this vector is calculated multiplying the
number of lines referenced per dot product by the number
of rows of the sparse matrix and the miss probability of one
of these accesses. The first value is calculated as p \Delta N=Ls ,
as X covers N=Ls lines, and each one has a probability p of
being accessed during the dot product times a given row of
the sparse matrix, as we have stated in the previous section.
The miss probability is calculated as the opposite of the
hit probability. Hits take place whenever the accessed line
has been referenced during a previous dot product, and it
has suffered no self or cross interferences.
Cross interferences are generated by the accesses to the
remaining vectors, which present a sequential access. The
cross interference area is given by the total area vector associated
with the accesses to vectors A, C, R and D. This
area vector is calculated in the way explained in Section ??,
by adding the individual area vectors corresponding to the
accesses to each program vector during the period consid-
ered. In our case we are interested in calculating the cross
interference area vector after i dot products:
cross
is the area vector covered by the accesses to
a vector V during i dot products. The four vectors have a
sequential access, so expression Ss derived in Section ?? is
applied:
These values are obtained considering that one element
of D and R, and fi components of A and C are accessed per
dot product. A scale factor r is applied to integer vectors in
order to take into account that integer data are often stored
using less bytes than real ones. This factor is the quotient
of the number of bytes required by a real datum and the one
required by an integer.
As for the self interference probability, each line of X
competes on average with C(N) lines of the same vector
(see definition of C(n) in (??)) in the same cache set, and
they all have the same probability p of being accessed during
a dot product times a row of the sparse matrix. As a result,
the number of different candidate lines of X to replace a given
line that have been accessed after i dot products belongs to
a binomial
The hit probability in the first access to any line of X
during the dot product of the j-'th row of the sparse matrix
times vector X is:
where p(1\Gammap) i\Gamma1 is the probability that the last access to the
line has taken place i dot products ago and S int X (i) is the
interference area vector generated by the accesses produced
during these i dot products, which is calculated as
where the cross interfence area vector obtained in (??) is
added to the self interference area vector, which is given by
an access with a uniform access probability per line of 1\Gamma(1\Gamma
p) i to the lines of vector X that can generate self interferences
with another line, which are calculated using (??). Finally,
the average hit probability is calculated as:
END DO
J=C(I)+2
END DO
END DO
DO K=R(I), R(I+1)-1
CT(P)=I
END DO
END DO

Figure

5: Transposition of a sparse matrix.
We must point out that the model only takes into account
the first access to each line of X in each dot product. The
other Nnz \Gammap\DeltaM \Delta(N=L s) accesses have a very low probability
of resulting in a miss, as they refer to lines that have been
accessed in the previous iteration of the inner loop.
4 Modeling the transposition of a sparse matrix
In this section the model is extended to a operation with
a greater degree of complexity, the sparse matrix transposi-
tion. As in the previous section, we assume that the sparse
matrix and its transposed are stored in a CRS format. Figure
?? shows the transposition algorithm described in [?],
where both matrices are represented by vectors(A, C, R) and
(AT, CT, RT), respectively. Observe that in loop 4 there are
multiple indirection levels both in the left and right side of
the sentences.
In what follows we employ a similar approximation to
the one developed in the previous section to estimate the
number of misses for vectors AT, CT and RT. The remaining
vectors have sequential accesses, which have already been
considered in the previous algorithm.
4.1 Vectors AT and CT
These two vectors follow exactly the same access pattern,
as may be observed in loop 4 of Figure ??. We will thus
explain the estimation of the number of misses for AT, as
the one for CT is identical but taking into account that it is
an integer vector. The access pattern is the one modeled by
Sg , described in Section ??, where
and
This pattern has similarities with the one explained in
Section ?? for vector X, as the access probability is uniformly
distributed along the vector, being the difference that for
vector X the probability is constant for each line of the vec-
tor, while for vectors AT and CT it corresponds to sets of
as many elements as a column of the original sparse matrix
holds. As a result, the general form of the hit probability
during the process of the j-'th row of the sparse matrix is
very similar to the one in (??), with the following differences:
ffl The probability of accessing the considered line of the
vector during the processing of a row is not p but
ffl The probability of accessing another line mapped to
the same cache set during the processing of the i previous
rows is not 1\Gamma(1\Gammap) i but 1\Gamma(S i
ffl Vector AT has Nnz elements, so the number of lines
that compete in the set with the line considered is
C(Nnz) in the equation that calculates the interference
area vector.
ffl When calculating the cross interference probability,
the same scheme of adding the area vectors corresponding
to the access to the remaining vectors is used.
R (i), S C (i) and S A (i) are calculated according to
(??) and the remaining area vectors are
l (N \Delta
(Nnz \Delta
4.2 Vector RT
This vector is referenced in the four loops of the algorithm.
In the first loop it has a totally sequential access that produces
misses.
In the second loop, the accesses to RT follow a similar pattern
to those of vector X in the sparse matrix-vector product.
The only differences consist in that there is only one possible
source of cross interferences (vector C), and that RT is an
integer vector and not a real value vector. The number of
misses in loop 2 is
first hit RT2
where P hit RT2 is calculated following expressions (??) and
(??) introducing the modifications mentioned above. Vector
RT has been completely accessed in a sequential manner in
the previous loop. For this reason we must add the probability
first hit RT2 of getting a hit due to the existence of
portions of RT in the cache when initiating the loop. Again,
a final expression can be found in [?].
In loop 3, vector RT is sequentially accessed without any
accesses to other vectors. The estimated number of misses
is
where P first hit RT3 may be estimated as P first hit RT2 \Delta
pr \Delta M .
Finally, in loop 4 the access to RT is again similar to the
sparse matrix-vector product described in Section ??. In
this loop we must also consider a hit probability P first hit RT4
due to a previous load of RT generated by loop 3.
5 Extension to banded matrices
A large number of real numerical problems in engineering
lead to matrices with a sparse banded distribution of the
entries [?]. In this section we present the modifications
the model requires in order to describe the cache behavior
for matrices of this type. The model parameter pn (see

Table

??) is calculated as fi
W , where W is the bandwidth.
Consequently p takes the value
5.1 Sparse matrix-vector product
The number of misses over vector X is the only one affected
by the band distribution of the entries. The modeling of the
behavior of this vector is identical to the one described in
Section ??. The number of accesses to different lines in the
dot products in which vector X is involved,
multiplied by the miss probability calculated as
For the calculation of P hit X in expression (??) M must
be replaced by W , as one line of X may be accessed during
the product of a maximum of W rows. In addition, the
number of lines of X that compete with another in a cache
set is C(W ) instead of C(N ), which influences P hit X (j) in
expression (??), as the entries of each row are distributed
among W positions instead of N .
5.2 Transposition of a sparse matrix
The calculation of the number of misses on AT is modified
in a similar way to that of vector X in the sparse matrix-vector
product: each line of this vector spreads its access
probability through the processing of W rows of the sparse
matrix, instead of M , thus reducing to this limit the sum
that calculates the hit probability. For the same reason,
the number of lines with which a given line of this vector
competes for the same cache set during its access period is
not C(Nnz ), but C(Nnz=N \Delta W ).
Besides, AT is accessed following the pattern described
by area vector funcion S gb in Section ??, so the probability
of accessing during the processing of the i previous rows a
given line that is mapped to the same cache set as the line
we are considering is 1\Gamma(S i
Also the cross interference probability calculation needs to
be modified according to the new access patterns.
Similar changes are needed for the estimation of the number
of misses on vector CT, taking into account that it is
made up of integer values.
The prediction of the number of misses on vector RT in
loops 2 and 4 is based on the model for vector X in the
sparse matrix-vector product, so the calculation of P hit RT2
and P hit RT4 requires the modifications explained in the
previous section, and the number of different lines accesses
in each dot product is no longer N \Delta r=Ls but W \Delta r=Ls . Some
changes are needed also to calculate the probabilities of hit
due to a reuse P first hit RT2 and P first hit RT4 . Finally,
the value of P first hit RT3 is now P first hit RT2 \Delta pr \Delta W .
6 Results
The model was validated with simulations on synthetic matrices
with a uniform distribution of the non zero elements
and banded matrices from the Harwell-Boeing collection [?].
Traces for the simulations were obtained by running the
algorithms after replacing the original accesses by calls to
functions that calculate the position to be accessed and write
it to disk. These traces were fed to the dineroIII cache sim-
ulator, belonging to the WARTS tools [?].

Tables

?? and ?? show the model accuracy for the sparse
matrix-vector product for some combinations of the input
parameters for uniform and banded sparse matrices respec-
tively. Tables ?? and ?? display the results for the sparse
matrix transposition model. Without any loss of generality
we have considered square matrices M) in the analy-
sis, and r = 1. Cs is expressed in Kwords and Ls in words.
The maximum error obtained in the trial set was 5.15%
for the synthetic matrices and 28.12% for the Harwell-Boeing
matrices. The reason for this last result is that the entries
distribution in the real matrices is not completely uniform,
which produces high deviations for the sparse matrix transposition
model (see Table ??). Nevertheless, we consider
that such amount of deviation is still acceptable for our analysis
purposes. Besides the small size of the matrices of the
collection does not favor the convergence of our probabilistic
model. We also want to point out that the average error
predicted
measured

Table

2: Predicted and measured misses and deviation of model for sparse matrix-vector product with a uniform entries
distribution. M , Nnz and numbers of misses in thousands.
Name N W Nnz ff Cs Ls K
predicted
measured

Table

3: Predicted and measured misses and deviation of model for sparse matrix-vector product of some Harwell-Boeing
matrices.
predicted
measured

Table

4: Predicted and measured misses and deviation of model for the transposition of a sparse matrix with a uniform entries
distribution. M , Nnz and numbers of misses in thousands.
Name N W Nnz ff Cs Ls K
predicted
measured

Table

5: Predicted and measured misses and deviation of model for the transposition of a sparse matrix of some Harwell-Boeing
matrices.
Pn
Log Ls

Figure

Number of misses in a 4-way associative cache with
2Kw during the sparse matrix-vector product of a 10K \Theta10K
matrix as a function of Ls and pn .
K=2
K=4
Log Ls

Figure

7: Number of misses during the sparse matrix-vector
product of a 10K \Theta 10K matrix with as a function
of the line size of a 2Kw cache for different associativities.
for the synthetic matrices was 0.65%, and 5% for the real
matrices.
In

Figures

??-?? we present the relationship between the
number of misses and the different parameters introduced in
the models. In the case of Cs and Ls we display the base
2 logarithm of the number of cache Kwords and line words
respectively.

Figure

?? shows the relationship of the number of misses
with Ls and pn in the sparse matrix-vector product. The
evolution is approximately linear with respect to pn , as the
number of accesses is directly proportional to Nnz and most
of them follow a sequential pattern. It may be observed how
the number of misses significantly decreases as Ls increases
because the accesses to all of the vectors except X are sequential
(see Figure ??) and the larger the lines, the more
exploitation of the spatial locality we obtain. Nevertheless,
when Ls is very large (? 64 words) and the matrix has a
lower degree of sparsity (pn ? 0:1) the increase of the self
and cross interferences probabilities over vector X begins to
unbalance the advantages obtained from a more efficient use
of the spatial locality exhibited by the remaining vectors for
This effect, shown in Figure ??, increases with the
value of pn .
The relationship between W and Cs for the banded sparse
matrix-vector product is shown in Figure ??. In this graph0.51.5x

Figure

8: Number of misses during the sparse matrix-vector
product for a sparse matrix 20K\Theta20K with
tries, a function of W and Cs .
K=2
K=4
Log

Figure

9: Number of misses during the sparse matrix-vector
product of a 20K \Theta 20K matrix with 2M entries and
8000 as a function of the cache size with Ls = 8 for different
associativities.
we have considered broad bands in order to illustrate the
effect of self interferences in the access to vector X. The
bandwidth reduction has a large influence on the number
of misses because it reduces the self interference probability
and increases the reuse probability for the lines of vector X,
as the non zeros are spread on narrower rows (spatial locality
improvement) and columns (temporal locality improve-
ment). A number of misses near the minimum is reached
when being the increases of Cs beyond that
size of little use. It is intuitive that good miss rates can
only be reached with Cs ? W , as with this size there is a
line in the cache for each line in the band of the currently
processed row. The extra room is needed to avoid the combined
effect of self and cross interferences, as we shall now
demostrate through an analysis for a fixed bandwidth for
different degrees of associativity and cache sizes.
In

Figure

?? the number of misses for a matrix with
displayed in relation to the cache size for different
associativities. We can observe that for
of the improvement is reached for the 8Kw cache, due to the
elimination of the self interferences. The cache size increments
from that size on help to gradually reduce the cross
interferences. On the other hand, caches with K ? 1 have
Log

Figure

10: Number of misses during the transposition of a
sparse matrix 20K\Theta20K with
and a function of W and Cs .
a different behavior: the misses reduction gradient is very
high while Cs -16Kw. The reason is that in the 8Kw cache
there are K different lines of X mapped to each cache set.
As the lines are usually accessed in the same order and the
cache uses a LRU replacement, any cross interference may
generate misses for all of the lines of X that are mapped to
the same cache set. The result is that the cross interferences
affect as many lines as a set can hold, thus generating more
misses. In fact we can see that the 4-way associate cache performs
a little worse than the 2-way cache for this cache size.
For caches with Cs - 16Kw, the cache sets have enough
lines left to absorb the accesses to the vectors that comprise
the sparse matrix and the destination vector without
increasing the interferences on X due to their combination
with the lines of this vector that reside in the same cache set.
For small cache sizes all the associativities perform similarly
due to the large number of interferences. The conclusion is
that associative caches help reducing the interference effect
when the number of lines that compete for a given cache line
is smaller than or equal to K; otherwise the performance is
quite similar to that of a direct mapped cache. Moreover,
in this case, if the lines mapped to the same cache set are
usually accessed in the same order, high associativities may
perform worse.
As for the sparse matrix transposition, Figures ?? and ??
represent the same data for this algorithm as Figures ??
and ?? for the sparse matrix-vector product respectively.
The first one shows a decrease of the number of misses with
the bandwidth reduction, being this more noticeable in the
point where Cs becomes greater than W . The reasons are
those explained for the previous algorithm. Anyway, this
reduction is much softer than in the sparse matrix-vector
product because the accesses to vector RT in loops 2 and
4, which are the most directly favoured by the bandwidth
reduction, stand only for a small portion of the misses. On
the other hand, the number of misses on vectors AT, and
CT, which account for the vast majority of the misses, decreases
slowly when Cs increases or W decreases, although
they are also heavily dependent on the bandwidth. The reason
is that in all of the cases shown in the figure the data
belonging to these vectors during the process of all of the
columns inside the band of the original matrix do not fit in
the cache ((Nnz=N) \Delta W entries). Only for the case when
does this set fit, and we can
see that the number of misses becomes stable in this area
K=2
K=4
Log

Figure

11: Number of misses during the transposition of a
sparse matrix 20K\Theta20K matrix with 2M entries and
8000 as a function of the cache size with Ls = 8 for different
associativities.
of the graph. The misses on C, R and A remain almost completely
constant due to their sequential access, obtaining
as only benefit from the bandwidth reduction a somewhat
lower cross interference probability.

Figure

?? shows that the general behavior of the algorithm
with respect to K, the associativity degree, although
having similarities with that of the sparse matrix-vector
product, does not depend only on W to determine the cache
sizes for which the hit rate obtains reasonable values. As explained
before, the reason is that for none of the
cache sizes considered contain a considerable portion of the
data the algorithm accesses during the W iterations that
process a whole band in loop 4, the one that causes most of
the misses. Only accesses to RT, mainly in loop 2, benefit
from the increase of Cs to values larger than W . This is specially
noticeable for as in the sparse matrix-vector
product. Another similarity is the worse behavior of caches
with K ? 1 for a cache size very close to W due to the added
effect of cross interferences with self interferences because of
cache lines which are usually accessed in the same order.
This penalizes the LRU replacement algorithm. Once the
cache size is noticeable larger than the bandwidth, higher
associativities perform better, as in Figure ??.
In order to get hints about the values of the cache parameters
for which the algorithm stabilizes its misses, Figures
?? and ?? show the same data for a smaller matrix
using 4. During the process of a band of this matrix
the working set for vectors AT and CT, those that account
for most of the misses, comprise 25W elements, as there is
an average of 25 elements per column. The hit rate obtains
values near to its maximum in Figure ?? when the cache size
exceeds this value. Increases of Cs beyond that limit provide
little performance improvement. These improvements
are only noticeable when the cache size increase is very high,
due to the strong reduction of the cross interference. We
must take into account that this graph is constructed for
a 4-way associative cache. Somewhat greater cache sizes
would be needed to obtain good cross interference reduction
in a direct mapped cache (see Figure ??).
associative caches help reducing the miss rate for the
small cache sizes in Figure ?? because on average there are
always less than 2 lines competing in any set, as during the
process of each row there are only about 200 lines of vector
Log

Figure

12: Number of misses during the transposition of a
sparse matrix 5K\Theta5K with 125K entries,
as a function of W and Cs .
K=2
K=4
Log

Figure

13: Number of misses during the transposition of a
sparse matrix 5K\Theta5K matrix with 125K entries and
200 as a function of the cache size with Ls = 4 for different
associativities.
AT with a non null access probability, 200 lines belonging
to vector CT and a few more lines belonging to the other
vectors, while the smallest of the caches considered has 512
lines. As expected, the increase of the cache size reduces
the hit ratio difference between direct mapped caches and
set associate caches. For Cs - 8Kw the cache size increase
helps only by reducing the cross interferences.
Finally, the relationship of the line size and the matrix
density with the number of misses for this last algorithm
has proved to be the same as in the sparse matrix-vector
product, being the only difference that the gradient
of the increase of misses with relation to pn is about three
times larger, which is normal, as the number of accesses per
non zero in the original matrix is eight, while in the sparse
matrix-vector product algorithm it is three.
7 Conclusions and future work
We have presented a fully-parametrizable model for the estimation
of the number of misses on a generic K-way associative
cache with LRU replacement and we have applied it to
the sparse matrix-vector product and the transposition of a
sparse matrix. The model deals with all the possible types
dineroIII
time
model
time
100 1000 1% 1000
100 1000 10% 100
100 1000 1% 1000
100 1000 10% 100
100 1000 1% 1000
100 1000 10% 100

Table

Simulation and model user times to calculate the
number of misses during the transposition of a banded sparse
matrix on a 200 MHz Pentium. N and Nnz in thousands,
time in seconds.
of misses and has demonstrated a high level of accuracy in
its predictions. It considers a uniform distribution of the
entries on the whole matrix or on a given band.
As

Table

?? shows, besides providing more information,
the modelization is much faster than the simulation, even
when the time required to generate the trace, which takes
almost as much time as the execution of the simulator itself,
is not included in the table.
We have illustrated how the model may be used to study
the cache behavior for this code, and shown the importance
of the bandwidth reduction in the case of the banded matri-
ces, even for high degrees of associativity. The model can be
also applied to study possible architectural cache parameter
modifications in order to improve cache performance.
Future work includes the extension of the model to consider
prefetching and subblock placement. On the other
hand, we are now working on the modeling for non uniform
distributions of the entries in the sparse matrices focusing
in the most common patterns that appear in real matrices
suites. Finally, in order to obtain more accurate estima-
tions, we are studying the inclusion of the data structures
base addresses as a parameter of the model.



--R

"Analysis of Cache Performance for Operating Systems and Multiprogramming,"
Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods.
"User's Guide for the Harwell-Boeing Sparse Matrix Collection,"
"Cache Miss Prediction in Sparse Matrix Computations,"
"Cache Miss Equations: An Analytical Representation of Cache Misses,"
"Cache Profiling and the SPEC Benchmarks: A Case Study,"

Sparse Matrix Technology.
"Sparse Matrix Computations: Implications for Cache Designs,"
"Characterizing the Behaviour of Sparse Algorithms on Caches,"
"Cache Interference Phenomena,"
"Trace-Driven Memory Simulation: A Survey,"
--TR
Analysis of cache performance for operating systems and multiprogramming
Characterizing the behavior of sparse algorithms on caches
Sparse matrix computations
Cache interference phenomena
Block algorithms for sparse matrix computations on high performance workstations
Trace-driven memory simulation
Cache miss equations
Cache Profiling and the SPEC Benchmarks

--CTR
Gerardo Bandera , Manuel Ujaldn , Emilio L. Zapata, Compile and Run-Time Support for the Parallelization of Sparse Matrix Updating Algorithms, The Journal of Supercomputing, v.17 n.3, p.263-276, Nov. 2000
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
Chun-Yuan Lin , Jen-Shiuh Liu , Yeh-Ching Chung, Efficient Representation Scheme for Multidimensional Array Operations, IEEE Transactions on Computers, v.51 n.3, p.327-345, March 2002
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
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
Chun-Yuan Lin , Yeh-Ching Chung , Jen-Shiuh Liu, Efficient Data Parallel Algorithms for Multidimensional Array Operations Based on the EKMR Scheme for Distributed Memory Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.14 n.7, p.625-639, July
probabilistic model;irregular computation;sparse matrix;cache performance