Improving the locality of the sparse matrix-vector product on shared memory multiprocessors
作者： J.C. Pichel , D.B. Heras , J.C. Cabaleiro , F.F. Rivera
DOI: 10.1109/EMPDP.2004.1271429
关键词: Matrix-free methods 、 Matrix multiplication 、 Shared memory 、 Row and column spaces 、 Sparse matrix 、 Sparse approximation 、 Computer science 、 Parallel computing 、 Locality 、 Set (abstract data type)
摘要: We extend a model of locality and the subsequent process improvement previously developed for case sparse algebra codes in monoprocessors to NUMA shared memory multiprocessors (SMPs). In particular product matrix by dense vector (SpM/spl times/V) is studied. model, established at run-time considering parameters that describe structure involved computations. The problem increasing formulated as graph problem, whose solution indicates some appropriate reordering rows columns matrix. algorithms were tested broad set matrices. have also performed comparison with other algorithms. results lead general conclusions about improving SMP performance codes.
sci-hub.se 参考文章(15)
Katherine A. Yelick, Eun-Jin Im, Optimizing Sparse Matrix Vector Multiplication on SMP. PPSC. ,(1999)
Y. Saad, Iterative Methods for Sparse Linear Systems ,(1996)
David Applegate, Robert Bixby, Vašek Chvátal, William Cook, Finding Tours in the TSP ,(1999)
D.B. Heras, V. Blanco, J.C. Cabaleiro, F.F. Rivera, Modeling and improving locality for the sparse-matrix-vector product on cache memories Future Generation Computer Systems. ,vol. 18, pp. 55- 67 ,(2001) , 10.1016/S0167-739X(00)00075-3
S. Toledo, Improving the memory-system performance of sparse-matrix vector multiplication Ibm Journal of Research and Development. ,vol. 41, pp. 711- 726 ,(1997) , 10.1147/RD.416.0711
Patrick R Amestoy, Timothy A Davis, Iain S Duff, None, An Approximate Minimum Degree Ordering Algorithm SIAM Journal on Matrix Analysis and Applications. ,vol. 17, pp. 886- 905 ,(1996) , 10.1137/S0895479894278952
Erez Petrank, Dror Rawitz, The hardness of cache conscious data placement Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '02. ,vol. 37, pp. 101- 112 ,(2002) , 10.1145/503272.503283
Juan J. Navarro, Elena García-Diego, Josep-L. Larriba-Pey, Toni Juan, Block algorithms for sparse matrix computations on high performance workstations international conference on supercomputing. pp. 301- 308 ,(1996) , 10.1145/237578.237624
E. Torrie, M. Martonosi, Chau-Wen Tseng, M.W. Hall, Characterizing the memory behavior of compiler-parallelized applications IEEE Transactions on Parallel and Distributed Systems. ,vol. 7, pp. 1224- 1237 ,(1996) , 10.1109/71.553272
Ali Pinar, Michael T. Heath, Improving Performance of Sparse Matrix-Vector Multiplication conference on high performance computing (supercomputing). pp. 30- 30 ,(1999) , 10.1145/331532.331562