HPSEC'04-
Proceedings of the 2004 International Conference on Parallel Processing
Workshops
Analytical Model for Analysis of Cache
Behavior during Cholesky Factorization and Its Variants
Authors: Ivan Šimeček and Pavel Tvrdík
Keywords
Numerical linear algebra, Cholesky factorization, cache model,
reuse distances, software
optimization, loop transformations, dynamic loop reversal.
Abstract
In this paper, we apply several transformations to Cholesky
factorization and describe a new transformation called dynamic loop
reversal which can increase temporal and spatial locality. We also
describe a probabilistic analytical model of the cache behavior during
the standard and recursive Cholesky factorization and use it for
studying effects of these transformations. Automatic methods for
predicting the cache behavior have been described in the literature,
but they are inaccurate in case of recursive calls, since they do not
take into account the interactions between subroutines. Our model is
more accurate, since it takes most of the interactions, namely on the
last level of recursion, into account. We have evaluated the accuracy
of the model by measurements on a cache monitor. The comparisons of the
numbers of measured cache misses and the numbers of cache misses
estimated by the model indicate that the accuracy of the model is
within the range on units of percents.
Download:
final version (in .PS format)
BibTex entry:
@inproceedings{JA_HPSEC,
author = "P. Tvrd\'{\i}k and
I. \v{S}ime\v{c}ek",
title = "Analytical
model for analysis of cache behavior during Cholesky factorization and
its variants",
journal = "HPSEC",
volume = "12",
pages = "617-629",
year = "2004",
Address = "Montreal, Canada"
}
