Characterizing the behavior of sparse algorithms on caches

Olivier Temam 1 William Jalby 1
1 CALCPAR - Calculateurs Parallèles
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : While there are many studies on the locality of dense codes, few deal with the locality of sparse codes. Because of indirect addressing sparse codes exhibit irregular patterns of references. In this paper, the behavior on cache of one of the most frequent primitives SpMxV (Sparse Matrix-Vector multiply) is analyzed. A model of its references is built and then performance bottlenecks of SpMxV are analyzed using model and simulations. Main parameters are identified and their role is explained and quantified. Then, this analysis is used to discuss optimizations of SpMxV. Moreover a blocking technique which takes into account the specifics of sparse codes is proposed.
Type de document :
[Research Report] RR-1666, INRIA. 1992
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:49:06
Dernière modification le : vendredi 16 novembre 2018 - 01:29:21
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:56:22



  • HAL Id : inria-00074891, version 1


Olivier Temam, William Jalby. Characterizing the behavior of sparse algorithms on caches. [Research Report] RR-1666, INRIA. 1992. 〈inria-00074891〉



Consultations de la notice


Téléchargements de fichiers