Malik Silva
ABSTRACT
In this paper, we consider alternate ways of storing a sparse matrix and their effect on computational speed. They involve keeping both the indices and the non-zero elements in the sparse matrix in a single data structure. These schemes thus help reduce memory system misses that occur when the usual indexing based storage schemes are used to store sparse matrices and give promising performance improvements.
- E.-J. Im and K. Yelick. Model-Based Memory Hierarchy Optimizations for Sparse Matrices, October 1998. Workshop on Profile and Feedback-Directed Compilation, Paris, France.Google Scholar
- J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach (Second Edition). Morgan Kauffman Publishers, San Mateo, California, 1996. Google ScholarDigital Library
- M. Silva and R. Wait. Go for both types of data locality! In L. Jenkins and Ivengar, editors, Proceedings of HPC Asia 2002, Bangalore, volume 2, 2002.Google Scholar
- N. Goharian, T. El-Ghazawi, and D. Grossman. Enterprise text processing: A sparse matrix approach. In IEEE International Conference on Information Techniques on Coding and Computing (ITCC 2001), Las Vegas, Nevada, Apr. 2001. Google ScholarDigital Library
- R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. van der Vorst. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, Philadelphia, 1994.Google ScholarCross Ref
- U.Ruede. Technological trends and their impact on the future of supercomputers. In F. H.J. Bungartz and C.Zenger, editors, High Performance Scientific and Engineering Computing, Proceedings of the International FORTWIHR Conference on HPSEC, Vol. 8 of Lecture Notes in Computational Science and Engineering, pages 459--471. Springer, Mar. 1998.Google Scholar
- R. Vuduc, J. Demmel, K. Yelick, S. Kamil, R. Nishtala, and B. Lee. Performance optimizations and bounds for sparse matrix-vector multiply. In Proceedings of the IEEE/ACM Conference on Supercomputing, 2002. Google ScholarDigital Library
Index Terms
- Sparse matrix storage revisited
Recommendations
Efficient sparse matrix-vector multiplication using cache oblivious extension quadtree storage format
In this paper, we elaborate on improving the sparse matrix storage format to optimize the data locality of sparse matrix-vector multiplication ( S p M V M ) algorithm, and its parallel performance. First of all, we propose a cache oblivious extension ...
Optimizing Sparse Matrix Vector Multiplication Using Diagonal Storage Matrix Format
HPCC '10: Proceedings of the 2010 IEEE 12th International Conference on High Performance Computing and CommunicationsSparse matrix vector multiplication (SpMV) is used in many scientific computations. The main bottleneck of this algorithm is memory bandwidth and many methods reduce memory bandwidth usage by compressing the index array. The matrices from finite ...
Sparse matrix computations with application to solve system of nonlinear equations
Numerical linear algebra is an essential ingredient in algorithms for solving problems in optimization, nonlinear equations, and differential equations. Spanning diverse application areas, from economic planning to complex network analysis, modeling and ...
Reviews
Timothy R. Hopkins
Increasing effort is being invested in attempting to squeeze every ounce of performance from the currently available processors; much of this investment is going into minimizing the effect of very slow memory access times on overall computational speed. This requires that each piece of data brought into a cache should be used as much as possible (temporal locality), and that every piece of data brought into a cache should be utilized (spatial locality). This paper looks at the practical advantages of using two simple methods of increasing temporal and spatial locality on the implementation of a sparse matrix/dense vector multiply. Performance comparisons are made against other commonly used schemes using a variety of different sparsity patterns. The storage method showing the most advantage for a general unstructured sparse matrix consists of an array of structures, where each structure consists of a pair of integers giving the row and column indexes and a float, providing the value of the nonzero element. The work reported is obviously very much a work-in-progress and is restricted to a very simple computational use (sparse matrices where there is no requirement to access the elements in any particular order or to select sets of elements, for example, all elements in a particular row). The paper would be a good, gentle introduction for a student wishing to start working in this area. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments