Abstract
Many scientific applications handle compressed sparse matrices. Cache behavior during the execution of codes with irregular access patterns, such as those generated by this type of matrices, has not been widely studied. In this work a probabilistic model for the prediction of the number of misses on a direct mapped cache memory considering sparse matrices with an uniform distribution is presented. As an example of the potential usability of such types of models, and taking into account the state of the art with respect to high performance superscalar and/or superpipelined CPUs with a multilevel memory hierarchy, we have modeled the cache behavior of an optimized sparse matrix-dense matrix product algorithm including blocking at the memory and register levels.
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
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barrett, R., Berry, M., Chan, T., Demmel, J., Donato, J., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., H. van der Vorst, H.: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM Press (1994).
Fraguela, B.B.: Cache Misses Prediction in Sparse Matrices Computations. Technical Report UDC-DES-1997/1. Departamento de Electrónica e Sistemas da Univerdade da Coruña (1997).
Fraguela, B.B, Doallo, R., Zapata, E.L.: Modeling Set Associative Caches Behavior for Irregular Computations. To appear in Proc. ACM Sigmetrics/Performance Joint Int’l. Conf. on Measurement and Modeling of Computer Systems, Madison, Wisconsin, (1998).
Lebeck, A.R., Wood, D.A.: Cache Profiling and the SPEC Benchmarks: A Case Study. IEEE Computer, 27(10) (1994) 15–26.
Navarro, J.J., García, E., Larriba-Pey, J.L., Juan, T.: Block Algorithms for Sparse Matrix Computations on High Performance Workstations. Proc. ACM Int’l. Conf. on Supercomputing (ICS’96) (1996) 301–309.
Temam, O., Jalby, W.: Characterizing the Behaviour of Sparse Algorithms on Caches. Proc. IEEE Int’l. Conf. on Supercomputing (ICS’92) (1992) 578–587.
Uhlig, R.A, Mudge, T.N.: Trace-Driven Memory Simulation: A Survey. ACM Computing Surveys 29 (1997) 128–170.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fraguela, B.B., Doallo, R., Zapata, E.L. (1998). Cache misses prediction for high performance sparse algorithms. In: Pritchard, D., Reeve, J. (eds) Euro-Par’98 Parallel Processing. Euro-Par 1998. Lecture Notes in Computer Science, vol 1470. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0057857
Download citation
DOI: https://doi.org/10.1007/BFb0057857
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64952-6
Online ISBN: 978-3-540-49920-6
eBook Packages: Springer Book Archive