Modeling and improving locality for the sparse-matrix-vector product on cache memories

被引:10
作者
Heras, DB [1 ]
Blanco, V [1 ]
Cabaleiro, JC [1 ]
Rivera, FF [1 ]
机构
[1] Univ Santiago Compostela, Dept Elect & Computac, Santiago De Compostela 15706, Spain
关键词
sparse matrix; memory hierarchy; cache memory; locality; ordering algorithms;
D O I
10.1016/S0167-739X(00)00075-3
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
A model for representing and improving the locality exhibited by the execution of sparse irregular problems is developed in this work. We focus on the product of a sparse matrix by a dense vector (SpM x V). We consider the cache memory as a representative level of the memory hierarchy. Locality is evaluated through four functions based on two parameters called entry matches and line matches. In order to increase the locality, two algorithms are applied: one based on the construction of minimum spanning trees and the other on the nearest-neighbor heuristic. These techniques were tested and compared with some standard ordering algorithms. (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:55 / 67
页数:13
相关论文
共 24 条