NAA'04 - Numerical Algorithms & Applications

Performance optimization and evaluation for linear codes
Authors: Ivan Šimeček and Pavel Tvrdík

High-performance,  Cache model, numerical linear algebra.


In this paper, we develop a probabilistic models for estimation of the numbers of cache misses during the sparse matrix-vector multiplication (for both general and symmetric matrices) and  the Conjugate Gradient algorithm for 3 types of data caches: direct mapped, s-way set associative with random or with LRU replacement strategies. Using HW cache monitoring tools, we compare the predicted number of cache misses with real numbers on Intel x86 architecture with L1 and L2 caches. The accuracy of our analytical models is above 95%.

BibTex entry:
author = "P. Tvrd\'{\i}k and I. \v{S}ime\v{c}ek",
title = "Performance optimization and evaluation for linear codes",
journal = "Numerical Analysis and Applications",
volume = "3",
number= "4",
pages = "617-629",
year = "2004",
isbn = {3-540-24937-0, 978-3-540-24937-5},
issn = {0302-9743},
url = {},
Address = "Rousse, Bulgaria"