Cache performance optimization of irregular sparse matrix multiplication on modern multi-core CPU and GPU  

作　　者：刘力 LiuLi Yang Guang wen 

机构地区：[1]Department of Computer Science and Technology,Tsinghua University

出　　处：《High Technology Letters》2013年第4期339-345,共7页高技术通讯（英文版）

基　　金：Supported by the National High Technology Research and Development Programme of China(No.2010AA012302,2009AA01 A134);Tsinghua National Laboratory for Information Science and Technology(TNList)Cross-discipline Foundation

摘　　要：This paper focuses on how to optimize the cache performance of sparse matrix-matrix multiplication(SpGEMM).It classifies the cache misses into two categories;one is caused by the irregular distribution pattern of the multiplier-matrix,and the other is caused by the multiplicand.For each of them,the paper puts forward an optimization method respectively.The first hash based method removes cache misses of the 1 st category effectively,and improves the performance by a factor of 6 on an Intel 8-core CPU for the best cases.For cache misses of the 2nd category,it proposes a new cache replacement algorithm,which achieves a cache hit rate much higher than other historical knowledge based algorithms,and the algorithm is applicable on CELL and GPU.To further verify the effectiveness of our methods,we implement our algorithm on GPU,and the performance perfectly scales with the size of on-chip storage.This paper focuses on how to optimize the cache performance of sparse matrix-matrix multiplication （SpGEMM）.It classifies the cache misses into two categories：one is caused by the irregular distribution pattern of the multiplier-matrix,and the other is caused by the multiplicand.For each of them,the paper puts forward an optimization method respectively.The first hash based method removes cache misses of the 1 st category effectively,and improves the performance by a factor of 6 on an Intel 8-core CPU for the best cases.For cache misses of the 2nd category,it proposes a new cache replacement algorithm,which achieves a cache hit rate much higher than other historical knowledge based algorithms,and the algorithm is applicable on CELL and GPU.To further verify the effectiveness of our methods,we implement our algorithm on GPU,and the performance perfectly scales with the size of on-chip storage.

关 键 词：sparse matrix multiplication cache miss SCALABILITY multi-core CPU GPU 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]