面向稀疏矩阵访存特性的Cache划分

J4 ›› 2012, Vol. 34 ›› Issue (9): 64-70.

面向稀疏矩阵访存特性的Cache划分

邓林，窦勇，郑义

(国防科学技术大学计算机学院，湖南长沙，410073)

收稿日期:2010-07-05 修回日期:2010-11-13 出版日期:2012-09-25 发布日期:2012-09-25
基金资助:
国家自然科学基金资助项目（60833004，60633050）；国家863计划资助项目(2008AA01A201)

Memory Access Behavior CharacteristicsOriented Cache Partition for SPMV

DENG Lin，DOU Yong，ZHENG Yi

(School of Computer Science,National University of Defense Technology,Changsha 410073,China)

Received:2010-07-05 Revised:2010-11-13 Online:2012-09-25 Published:2012-09-25

摘要/Abstract

摘要：

稀疏矩阵向量乘是许多科学计算的核心，计算中大量的间接和随机访存成为计算的主要瓶颈。本文通过分析稀疏矩阵向量乘运算的数据结构和计算过程，得到计算中不同数据的访存特征，并提出了一种面向数据访存特性的Cache划分方法。对12个稀疏矩阵向量乘的测试表明，本文的Cache划分方法能有效地提高可重用向量的Cache命中率，同时减少计算对Cache空间的需求。

关键词: 稀疏矩阵, 向量乘, Cache划分, 访存特性

Abstract:

The sparse matrix vector multiplication (SPMV) is the kernel of many scientific applications.Due to its indirect and random memory accesses,the SPMV is the bottleneck of scientific applications.In this paper,based on analyzing data structure and computation process,we present the memory access characteristics of the SPMV and propose a memory access behavior characteristicsorient cache partition method.According to the performance evaluation with 12 sparse matrix vector multiplications,the proposed cache partition method increase the hit ratio of reusable data and reduce the cache capacity request efficiently during the SPMV.

Key words: sparse matrix；vector multiplication;cache partition;memory access behavior character

邓林，窦勇，郑义. 面向稀疏矩阵访存特性的Cache划分[J]. J4, 2012, 34(9): 64-70.

DENG Lin，DOU Yong，ZHENG Yi. Memory Access Behavior CharacteristicsOriented Cache Partition for SPMV[J]. J4, 2012, 34(9): 64-70.

参考文献

［1］Suh G E,Rudolph L,Devadas S. Dynamic Partition of Shared Cache Memory［J］. Journal of Supercomputing,2004,28(1):726.
［2］Cho S,Jin L.Managing Distributed,Shared L2 Caches through OSLevel Page Allocation［C］∥Proc of MICRO,2006:455468.
［3］Carter J,Hsieh W，Swanson M,et al. Memory System Support for Irregular Applications［J］.LNCS,1998,1511:1726.
［4］Carter J,Hsieh W,Stoller L,et al. Impulse:Building a Smarter Memory Controller［C］∥Proc of HPCA,1999:7079.
［5］Kim D,Chaudhuri M. Architectural Support for Uniprocessor and Multiprocessor Active Memory Systems［J］.IEEE Transactions on Computers, 2004,53(3):288307.
［6］Morris G R,Prasanna V K. Sparse Matrix Computations on Reconfigurable Hardware［J］. IEEE Transactions on Computers,2007,40(3):5864.
［7］Heath,Pinar A,Michael T.Improving Performance of Sparse MatrixVector Multiplication［C］∥Proc of ACM/IEEE SC’99,1999:3039.
［8］Stathis P, Vassiliadis S, Cotofana S. A Hierarchical Sparse Matrix Storage Format for Vector Processors［C］∥Proc of IPDPS,2003:6168.
［9］Eduardo F D'Azevedo, Fahey M R,Mills R T . Vectorized Sparse Matrix Multiply for Compressed Row Storage Format［J］.LNCS,2005,3516:758789.
［10］Vassiliadis S, Cotofana S,Stathis P. Vector ISA Extension for Sparse Matrix Vector Multiplication［C］∥Proc of EuroPar, 1999:708715.
［11］Cotofana S, Stathis P, Vassiliadis S. Direct and Transposed Sparse MatrixVector Multiplication［C］∥Proc of MPCS,2002:19.
［12］Bokhari,Berger M J,Shahid H.A Partitioning Strategy for Nonuniform Problems on Multiprocessors［J］.IEEE Transactions on Computers,1987,36(5):570580.
［13］Sun, Pothen A, Chunguang.A Mapping Algorithm for Parallel Sparse Cholesky Factorization［J］. SIAM Journal on Scientific Computing, 1993,14(5):12531257.
［14］Im E J, Yelick K, Vuduc R. SPARSITY: Optimization Framework for Sparse Matrix Kernels［J］.HPCA,2004,18(1):135158.

[1]	李小玲, 方建滨, 马俊, 谭霜, 谭郁松. 基于监督学习的稀疏矩阵自动任务分配[J]. 计算机工程与科学, 2023, 45(05): 782-789.
[2]	顾越, 赵银亮. 基于RISC-V向量指令的稀疏矩阵向量乘法实现与优化[J]. 计算机工程与科学, 2022, 44(01): 1-8.
[3]	陈逸飞，朱蕾，李宏亮. 一种多线程阵列众核处理器的二级Cache划分机制[J]. 计算机工程与科学, 2019, 41(03): 400-408.
[4]	何志军,何洪英,黄旭. 改进十字链表的存储方法在短路电流计算中的应用[J]. 计算机工程与科学, 2017, 39(04): 648-655.
[5]	邹佩钢1,2，陈军1. 基于CombBLAS的同辈压力图聚类并行算法的设计与实现[J]. 计算机工程与科学, 2017, 39(03): 424-429.
[6]	苏锦柱，邬贵明，贾迅. 二元域大型稀疏矩阵向量乘的FPGA设计与实现[J]. 计算机工程与科学, 2016, 38(08): 1530-1535.
[7]	阳王东1,2 ,李肯立2. 基于HYB格式稀疏矩阵与向量乘在CPU+GPU异构系统中的实现与优化[J]. J4, 2016, 38(02): 202-209.
[8]	许彬彬，戴清平，朱敏，谢端强. 基于哈夫曼编码的稀疏矩阵的存储与计算[J]. J4, 2013, 35(11): 134-138.
[9]	秦晋，龚春叶，胡庆丰，刘杰. 基于CUDA编程模型的稀疏对角矩阵向量乘优化[J]. J4, 2012, 34(7): 78-83.
[10]	所光，杨学军. 多核处理机系统Cache管理技术研究现状[J]. J4, 2010, 32(7): 65-68.
[11]	熊伟，殷建平，所光，赵志恒. 多核处理器面向低功耗的共享Cache划分方案[J]. J4, 2010, 32(10): 26-29.
[12]	杜静敖富江杨学军. 矩阵向量乘在流处理器上的实现[J]. J4, 2007, 29(11): 131-133.
[13]	刘杰迟利华胡庆丰李晓梅. 并行计算稀疏矩阵乘以向量的负载平衡算法[J]. J4, 2006, 28(3): 76-77.
[14]	戴春来. 对基于稀疏矩阵分解求解约束系统方法的改进[J]. J4, 2004, 26(9): 52-53.
[15]	迟利华李晓梅. 块带状线性方程组的分布式并行算法[J]. J4, 1999, 21(3): 61-65.