Analytical model for analysis of cache behavior during cholesky factorization and its variants

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.