RAM(h)模型下SpMV存储访问复杂度的分析  

Memory access complexity analysis of SpMV in RAM (h) model

在线阅读下载全文

作  者:袁娥[1,2,3] 张云泉[1,3] 孙相征[1,2,3] 

机构地区:[1]中国科学院软件研究所并行计算实验室,北京100190 [2]中国科学院研究生院,北京100190 [3]中国科学院计算机科学国家重点实验室,北京100190

出  处:《计算机工程与设计》2009年第3期613-618,共6页Computer Engineering and Design

基  金:国家自然科学基金项目(60303020);国家自然科学基金重点项目(60533020);国家863高技术研究发展计划基金项目(2006AA01A102;2006AA01A125);北京邮电大学网络与交换技术国家重点实验室开放课题基金项目(2005-05)

摘  要:稀疏矩阵向量乘(SpMV)采取压缩行存储格式的算法性能非常差,而寄存器分块算法可以使得数据尽量在靠近处理器的存储层次中访问而提高性能。利用RAM(h)模型进行分析和比较不同算法形式的存储访问复杂度,可以比较两种算法的优劣。通过RAM(h)分析SpMV两种实现形式的存储访问复杂度,同时在奔腾四平台上,测试了7个稀疏矩阵的SpMV性能,并统计了这两种算法中L1,L2,和TLB的缺失率,实验结果与模型分析的数据一致。Sparse matrix-vector multiplication is an important computational kernel in scientific applications that tends to perform poorly on modem processors. But the register-level blocked algorithm can optimize memory hierarchy access, improve the performance. RAM (h) is a computation model that has h-level memory hierarchies. It indicates that different implementation forms of one same algorithm can have different memory access complexity. With RAM (h) model, memory access complexity analysis is performed on two implementation forms of SpMV, which are CSR storage algorithm and register-level blocked algorithm. Statistical results of performance and the miss rate of L1, L2 and TLB on Pentium IV platform are listed. Model analytical results matched well with experimental results.

关 键 词:SpMV 稀疏矩阵向量乘 RAM(h)模型 存储访问复杂度 

分 类 号:TP302.7[自动化与计算机技术—计算机系统结构]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象