一种基于四叉树的稀疏矩阵存储方式和高效乘算法
大规模稀疏矩阵向量乘和稀疏矩阵间乘法在科学研究和实际工程中广为应用，但传统的稀疏矩阵存 储格式或者会在运算中带来间接引用，以致降低Cache 命中率，严重影响程序的执行效率，或者需要已知矩阵中 非零元的分布，不易广泛应用。本文从提高Cache 命中率和Cache 中数据的局部性出发，提出一种带索引数组的 四叉树存储结构。采用这种数据结构，稀疏矩阵的乘法就可以被分解为一个个与Cache 容量相适应的小区域相对独立的运算，故可以从整体上显著提高稀疏矩阵乘法的执行效率。文中给出了新存储格式的生成算法和基于 此数据结构的矩阵向量乘及矩阵乘算法，分析了目标区域大小的选取原则。工程应用实例验证表明，新的存储方 式对于提高矩阵乘效率是十分有效的。
稀疏矩阵 四叉树 Cache 命中率 矩阵乘算法
张纪林 张晓飞 徐向华 万健 Ivan Simecek
杭州电子科技大学计算机学院,浙江杭州 310018 香港科技大学计算机科学与工程学系,香港 捷克技术大学电子工程学院计算机科学系,捷克
国内会议
2010年全国高性能计算学术年会(HPC china2010)
北京
中文
496-506
2010-10-27（万方平台首次上网日期，不代表论文的发表时间）