C N4 3 -1 2 5 8 / T P 计 算 机 工 程 与 科 学 第 4 1 卷 第 4 期 2 0 1 9 年 4 月 ISSN 1007-130X Computer Enginering & Science Vol.41，No.4，Apr.2019
文 章 编 号 :1007-130X(2019)04-0590-08
面向异构计算平台的SpMV 划分优化算法研究*
谈 兆 年 ，计 卫 星 ，Akrem Benatia，高 建 花 ，李 安 民 ，王 一 拙 (北京理工大学计算机学院，北京 100081)
摘 要:稀疏矩阵向量乘SpMV 在科学计算和工程问题中有着广泛的应用。稀疏矩阵的非零元素分 布会极大地影响SpMV 的计算效率，针对不同的数据分布模式使用特定算法进行加速可以获得显著的性 能提升。CPU 的控制能力强，适用于通用计算，而 GPU 的计算核心多，并行度高，适用于数据密集型计 算 。 根 据 CPU 和 GPU 的 不 同 特 点 ，充 分 发 挥 二 者 的 优 势 ，可 以 使 SpMV 获 得 更 大 的 性 能 提 升 。 研 究
CPU-GPU 混合架构上SpMV 的任务划分与优化方法，针对2种主要的稀疏矩阵数据分布模式:Quasi-di- agonal和 Tetris，提 出 了 一 种 基 于 SVR 的 任 务 二 次 分 配 算 法 。 研 究 的 2 种 稀 疏 矩 阵 模 式 具 有 很 好 的 代 表 性，在实际科学工程应用中占比达到66%。实验评测结果表明，采用本文的算法之后，与 GPU 相比，异构
平台上 Quasi-diagonal和 Tetris的加速比平均值分别达到1.74×和2.15×。 关 键 词 : 异 构 计 算 ; 矩 阵 划 分 ; 协 同 优 化 ;S V R ;S p M V
中 图 分 类 号 :O246 文 献 标 志 码 :A
doi:10.3969/j.isn.1007-130X.2019.04.003 An SpMV partitioning and optimization algorithm
on heterogeneous computing platforms TAN Zhao-nian，JI Wei-xing，AKREM Benatia，GAO Jian-hua，LI An-min，WANG Yi-zhuo
(School of Computer Science and Technology，Beijing Institute of Technology，Beijing 100081，China)
Abstract:Sparse matrix vector multiplication SpMV is widely used in solving scientific computing and enginering problems.The distribution of non-zero elements of the sparse matrix can greatly afect the computational eficiency of SpMV，and significant performance improvements can be achieved by u- sing specific algorithms for diferent data distribution paterns.CPU has strong controlability which en- ables its application in general-purpose computing while GPU has high degre of paralelism and many cores，thus suitable for data-intensive computing.Taking advantage of the two can gain greater perform- ance for SpMV.We study the task partitioning and optimization methods of SpMV on CPU-GPU hybrid architecture and propose a task-based rescheduling algorithm based on SVR for two main data distribu- tion paterns:Quasi-diagonal and Tetris.The two representative sparse matrix paterns acount for 66% of the data in practical scientific and enginering applications.Experimental results show that our approach can achieve an average spedup of 1.74xand 2.15xfor Quasi-diagonal and Tetris on heteroge- neous platforms over on GPU respectively.
Key words:heterogeneous computation;matrix partitioning;colaborative optimization;SVR;SpMV
* 收 稿 日 期 :2018-10-17;修 回 日 期 :2018-12-20 通信地址:100081 北京市北京理工大学计算机学院
Addres:School of Computer Science and Technology，Beijing Institute of Technology，Beijing 100081，P.R.China
谈兆年等:面向异构计算平台的 SpMV 划分优化算法研究
591
1 引言
稀 疏 矩 阵 向 量 乘 SpM V (Sparse Matrix Vec- tor multiplication)在 许 多 科 学 和 工 程 问 题 中 有 着 广泛的应用，这些应用通常涉及大量循环或者迭代 的SpMV操作[1]，这会带来巨大的时间开销。异 构计算主要是指使用不同类型指令集和体系架构 的计算单元组成系统的计算方式。异构计算通过 使用不同的协处理器，可以提升计算性能和能源效
率。目前典型的异构系统包括 CPU-FPGA、CPU- GPU 等 ，较 为 主 流 是 CPU-GPU 异 构 计 算 系 统 [2]。
由于CPU功能设计较为复杂，控制能力强，适合 于通用计算，但是不能胜任大量稠密数据的处理;
GPU 中计算核心较多，数据并行度较高，适合处理
数据密集型的计算任务，但是由于功能设计较为简
单，处理分散的稀疏数据时效率较低。因此，充分
发挥二者的优点，可以获得一定的 SpMV 性能提 升[3]。
为 了 提 升 Sp M V 的 计 算 性 能 ，研 究 人 员 提 出 了 多 种 新 型 存 储 格 式 和 加 速 方 案 。 Maringanti 等 人[4]提出了一种基于 CSR(Compresed Sparse
Row)和 ELL(ELLpack-itpack)的 混 合 存 储 格 式 ， 基本思想是:当行大小足够大时，CSR格式表现良 好。因此，若矩阵行中的非零元个数大于32，则使 用CSR格式存储该行，否则使用ELL格式存储。
Su 等 人 [5 ] 提 出 了 Cocktail 格 式 ，将 矩 阵 划 分 为 多 个子矩阵，针对子矩阵的特点选择特定的格式，一 个 矩 阵 可 能 使 用 多 种 格 式 。 M o n a k o v 等 人 [6 ] 基 于 BCOO(Blocked COOrdinate)和 BCSR(Blocked Compres sed Sparse Row )提 出 了 一 种 混 合 分 块 存 储 格 式 。 M uralidharan 等 人 [7 ] 利 用 机 器 学 习 算 法 ， 提出了一种在 GPU 上选择最优稀疏矩阵格式的 方案。另外，还有学者提出了基于子矩阵的划分方 法[8]、混合计算方法[9]等。然而这些方法都存在以 下2个问题:(1)没有对实际稀疏矩阵进行广泛的 分析，划分方法适用范围有限，无法涵盖多种模式 的 矩 阵 ;(2)缺 乏 对 静 态 划 分 后 的 进 一 步 协 同 优 化 ， 通常会导致CPU和GPU上的负载不均衡[10]。
针对上述问题，本文根据稀疏矩阵的数据分布 特点，使用特定的划分算法将稀疏矩阵划分为规则 的稠密部分和不规则的稀疏部分，分别分配给
GPU 和 CPU 计 算 。 在 静 态 划 分 的 基 础 上 ，设 计 了
一 种 基 于 SVR (Support Vector Regres sion)[11] 的 任务二次分配算法，进一步提升了不同模式稀疏矩
阵 的 SpMV 计 算 性 能 。 这 种 基 于 SVR 的 协 同 优 化算法与平台无关，可以推广到其他异构计算系统 中。
2 稀疏矩阵编码格式
稀疏矩阵中通常有较多的零元素，为了节省存 储空间，需要对矩阵进行压缩。稀疏矩阵的编码格 式 有 很 多 ，本 文 中 用 到 的 格 式 为 CSR、ELL 和 DIA (DIAgonal)，如 图 1 所 示 。
Figure 1 CSR，ELL and DIA format 图 1 C S R 、E L L 和 D I A 格 式 示 意 图
CSR格式是一种压缩行存储方案，由行偏移、 列标和值3个数组组成。其中，行偏移数组中的元 素是每行第1个非零元素的偏移量，列标数组存储 了每个非零元素的列标值，数组的最后是非零元个 数总和。ELL格式的思想是按行将非零元素移动 到矩阵的左边，挤占原来零的位置，同时记录非零 元原来的列标，实现压缩存储。ELL 格式包含列 标矩阵和值矩阵，由于非零元按行移动，因此行标 信息不变。DIA 格式是一种对角线存储方案，压 缩存储非全零的对角线，包含值矩阵和对角线编号 数组，对角线数组记录了每条对角线相对于主对角 线的偏移量，下三角区域的对角线偏移量为负数， 上三角区域的对角线偏移量为正数。可见，DIA 格式适用于非零元沿对角线分布的矩阵。
稀 疏 矩 阵 编 码 中 ，常 用 的 有 COO (COOrdi- nate)、CSR、ELL 和 DIA 等 ，还 有 一 些 格 式 是 对 它
们 的 改 进，例 如 改 进 CSR[12]、Merge-based CSR[13]、Jagged-DIA[14] 和 BSR (Blocket Sparse R o w ) [1 5 ] 等 格 式 。
SpMV指的是一个稀疏矩阵与一个稠密向量 相 乘 ，其 数 学 形 式 是 y = Ax ，其 中 A 是 一 个 大 小 为 M×N 的稀疏矩阵，x是一个N 元稠密向量，y是
一个 M 元向量。
592 Computer Engine ering & Science计 算 机 工 程 与 科 学2019，41(4) 3 SpMV 任务划分和优化算法设计
3 .1 稀 疏 矩 阵 数 据 布 局 分 析
科学计算中经常使用稀疏矩阵，一般使用统一 的方法来处理不同的稀疏矩阵，没有充分利用稀疏 矩阵的模式特点。对稀疏矩阵按照不同模式进行 分类，每种模式使用特定的划分和优化方法，可以 进一步提升SpMV 的计算性能。目前已有的研究 为特定类型的稀疏矩阵设计了多种划分方法，这些 方法很难推广到其他类型的矩阵。另外，在静态划 分之后，通常会导致多个处理器负载不均衡。
本 文 首 先 对 SuiteSparse 矩 阵 集 合 (原 佛 罗 里 达 大 学 稀 疏 矩 阵 集 合 )[16 ] 做 了 广 泛 的 分 析 ，总 结 出
2种重要的稀疏矩阵模式:Quasi-diagonal和 Tet- ris，这 2 种 模 式 的 矩 阵 分 别 占 SuiteSparse 集 合 的 23.0% 和 43.1% ，具 有 一 定 的 代 表 性 。 稀 疏 矩 阵
中非零元分布不规则，对其进行适当的划分可以将 SpMV 计算任务分解为规则的稠密部分和不规则 的稀疏部分。由于 GPU 便于处理规则的大规模
数据，因此将稠密数据交给 GPU 来处理。而 CPU 有很强的通用性和复杂的 Cache机制，可以很好地 处理不规则部分。
本文设计的算法包括2个阶段:静态划分和协 同优化。在静态划分阶段，使用特定的算法划分2 种模式的矩阵，将稠密部分交给 GPU，稀疏部分交 给CPU进行计算。在协同优化阶段，由于 GPU 和 CPU 的负载可能不均衡，因此使用机器学习算 法 (S V R ) 来 预 测 划 分 后 S p M V 的 计 算 时 间 ， 根 据 预测结果对计算任务进行合理调整，实现 CPU 和
GPU 的负载均衡。 与已有的方法相比，本文对稀疏矩阵的模式进
行了广泛的分析，总结出2种重要的模式，使用特 定的划分方法，在加入协同优化后提升了 SpMV 的平均计算性能，弥补了传统静态划分方法的不 足。本文总结出的稀疏矩阵模式可以处理不同类 型的矩阵，基于SVR的性能预测方法可以推广到 其他异构计算平台。
3 .2 面 向 异 构 计 算 平 台 的 S p M V 划 分
(1 )Q uasi-diagonal 模 式 划 分 方 法 。
Quasi-diagonal 矩 阵 中 ，大 部 分 非 零 元 素 分 布 在主对角线附近，其余非零元零散地分布在其他区 域，如图2所示，diag、GT01R 和lock1074都是典 型 的 Quasi-diagonal 矩 阵 。
Figure 2 Examples of Quasi-diagonal matrix 图 2 Q uasi-diagonal 矩 阵 示 例
Quasi-diagonal 划 分 方 法 如 图 3 所 示 。 根 据 划 分宽度WIDTH 将整个矩阵划分成2个子矩阵:Q1 和Q2 。子矩阵Q1 以存储效率较高的DIA格式存 储，Q2 以CSR格式存储。在计算SpMV时，Q1 被
分 配 给 G P U 处 理 ， Q2
被 分 配 给 C P U 处 理 [8 ] 。
Figure 3 An example of Tetris matrix 图 3 T etris 矩 阵 示 例
(2)Tetris 模 式 划 分 方 法
若稀疏矩阵中大多数行的非零元素个数相近， 如 图 4 所 示 ，bratu 3d、big 和 geom 都 是 典 型 的 例 子 ，本 文 将 这 类 矩 阵 归 为 Tetris 模 式 。
Figure 4 Schematic diagram of Quasi-diagonal partitioning 图 4 Q uasi-diagonal 模 式 划 分 示 意 图
Tetris划分方法如图5所示，根据划分阈值 K 将整个矩阵划分成2个子矩阵:T1 和T2 。本文按 照 CPU 和 GPU 的 计 算 能 力 来 确 定 K 值 ，根 据 本 文实验中使用的机器，将非零元素的80%分配给
GPU，20%分配给CPU。子矩阵T1 以存储效率较 高的ELL格式存储，T2 以CSR格式存储。在计 算SpMV时，T1 被分配给GPU处理，T2 被分配给
CPU 处 理 。
3.3 SpMV 计算任务协同优化
(1)协 同 优 化 算 法 。
在SpMV 执行过程中，计算性能受多种因素 影响，比如稀疏矩阵规模、非零元个数、编码格式、 稀 疏 特 性 和 计 算 平 台 [17] 等 等 ，由 于 无 法 预 测 实 际
谈兆年等:面向异构计算平台的 SpMV 划分优化算法研究
593
Figure 5 Schematic diagram of Tetris partitioning
图 5 T etris 模 式 划 分 示 意 图 的执行时间，很可能会使得处理器的实际负载和计 算能力不匹配，导致异构平台中的 A 处理器比B 处理器提前完成计算。因此，在静态划分之后，进 一步对计算任务进行适当的二次分配，以实现负载
均衡，缩短总体计算时间。 图6为无协同优化的任务执行示意图。其中，
S p M V 计 算 任 务 划 分 成 G P U 和 C P U2 个 部 分 ， 在 计算开始的t0 时刻，GPU中的计算任务队列包含 5个C1计算任务，而 CPU 中的计算任务队列则包 含3个C2计算任务。在t2 时刻，GPU 已经完成了 分 配 的 计 算 任 务 ，而 CPU 还 剩 余 一 个 C2 的 计 算 任务。因此，在没有二次分配的情况下要完成整个
SpMV计算需要花费的时间是t3-t0 。不难看出， GPU 在 完 成 自 身 计 算 任 务 时 ，还 需 要 等 待 CPU ，
等待时 GPU 的计算资源处于空闲状态，造成资源 浪费。
Figure 6 Task execution without coperative optimization 图6 无协同优化的任务执行示意图
Figure 7 Task execution after coperative optimization 图7 加入协同优化后的任务执行示意图
SpMV计算任务协同优化如算法1所示。其 中 ，输 入 包 括 :
(1)使用静态划分方法划分好的 SpMV 计算 任务Q1 和Q2 (或T1 和T2 );
(2)预先训练好的SVR模型:MGPU 和MCPU ; (3 ) 优 化 因 子 ξ 。
输 出 为 经 过 优 化 之 后 的 计 算 任 务 Q′1 和 Q′2 (或
T′1 和 T′1 )。
算法1 SpMV 协同优化算法
输 入 :Q 1 ，Q 2 ，M G P U ，M C P U ，ξ ，δ 。 输 出 :Q′1 和 Q′2 。
01:TGPU ，TGPU =0;
02:do
0 3 : T G P U = M G P U (Q 1 ) ;
0 4 : T C P U = M C P U (Q 2 ) ;
05: if|TGPU -TCPU|<δ06: break;07: else if TGPU >TCPU
08:R←Q1 的ξ×nnz(Q1)个非零元素; 09: Q2 ←Q2 ∪R;
10: Q1 ←Q1 ∪R;
11: else
12:R←Q2 的ξ×nnz(Q2)个非零元素; 13: Q1 ←Q1 ∪R;
14: Q2 ←Q2 ∪R;
15: endif
16:while(1)
17:Q′1 ←Q1 ，Q′2 ←Q2 ;
加入协同优化之后，如图7所示，在计算开始
前，对GPU和CPU的执行时间进行预测，根据预
估时间对任务进行合理的优化。由于此时 CPU
执行C2任务的速度较慢，因此可以将一部分C2 值为ξ∈(0，1)，不同的ξ值也会影响优化的效果。
的计算任务移动到 GPU 的队列中，C1格式的队列 变长，C2格式的队列变短。t2 时刻，GPU和CPU 均完成全部分配的计算任务，整个 SpMV 用时为
t2 -t0 ，比没有协同优化缩短了t3 -t2 。
δ用来判断 GPU 和 CPU 执行时间是否相当。经 过优化之后，GPU 和 CPU 承担的计算任务更加均 衡，二者的执行时间基本相当，可以降低异构系统 整体的SpMV执行时间。
算法1中，nz(Q1)指的是子矩阵Q1 的非零 元素个数。优化因子ξ是预先设置的比例常数，取
594 Computer Engine ering & Science计 算 机 工 程 与 科 学2019，41(4)
(2)使用SVR模型预测SpMV执行时间[18]。
使 用 SVR 来 预 测 GPU 和 CPU 的 SpMV 执 行 时 间 需 要 遵 循 下 面 这 些 步 骤 :
1选择不同模式的稀疏矩阵构成原始集合 Q 和 T ;
2使用划分算法预处理数据集(见表1)，每种 模式得到两个子数据集，每个子数据集中，训练数 据 占 80 % ，测 试 数 据 占 20 % 。
3根据稀疏矩阵及编码格式的特点，构造每个 矩阵的特征向量，每个矩阵的标签是实际 SpMV 执行时间，这些特征向量和对应的标签就是 SVR 模型的训练数据;
4使用 SVR 训练出不同模式、不同平台对应 的模型，共有4个;
Intel，因此使用与之配套的 MKL(Math Kernel Library)[20]库 来 支 持 CPU 上 的 SpMV 运 算 。
5在测试集上验证模型。 Table 1 Data set information
表1 数据集信息 划分算法 原始矩阵集合 矩阵个数
Quasi-diagonalQ629TetrisT1 165
训练数据集
QDIA 、QCSR TELL、TCSR
4 .2 评 测 方 法
实验结果使用 GFLOPS来度量，含义是每秒10
亿次的浮点运算数。实际上，由于 SpMV 计算过程 中的真实浮点操作次数难以测定，因此一般采用计 算任务规模和计算时间的比值来计算 GFLOPS。
在实际的科学计算和工程问题中，往往需要进 行 成 百 上 千 次 的 Sp M V 调 用 ，Sp M V 成 为 很 多 问 题 的计算瓶颈，寻找出一种提升 SpMV 性能的算法意 义重大，本文算法平均时间开销比单次 SpMV 调用 时间小一个数量级，相对于上千次的SpMV 调用，使 用预测模型的额外时间开销可以忽略不计。
表3和表4展示了实验中测试的一部分矩阵 的详细信息。
处 理 器
名 称
设 备 内 存/GB 1112
频 率/M Hz 1 582 2.13
Table 2 Experimental equipment 表2 实验设备
GPUNVIDIA GTX 1080TiCPUIntel Xeon E5606
以 Quasi-diagonal 为 例 ，原 始 矩 阵 集 合 Q 与 子 集QDIA 和QCSR 满足的关系如公式(1)所示。
Q = {A 1 ，A 2 ，… ，A N } 烄
烆
其中，原始矩阵集合Q 包含了N 个矩阵，每一个矩 阵Ai 都被切分成2个子矩阵ADIAi 和ACSRi ，Tetris
模式也满足类似的关系。
在训练阶段，分别生成 Quasi-diagonal模式的
2个模型和 Tetris模式的2个模型。数据集中的 每个矩阵对应一条训练数据，包括该矩阵的特征属 性向量和在对应平台上的 SpMV 执行时间。
4 实验与分析 4 .1 实 验 环 境
实验中所使用的 GPU 和 CPU 信息如表2所 示，Intel Xeon为4核8线程，操作系统为 Win- dows 7-64 位 。 实 验 中 ，GPU 平 台 使 用 了 CUSP
库 [19]实 现 SpMV 运 算 ，CUSP 是 一 个 基 于 Thrust 的开源稀疏线性代数和图计算库，它向研究人员提 供了灵活的编程接口，主要用于稀疏矩阵计算和稀 疏线性系统求解。由于实验中使用的 CPU 来自
Table 3 Information of Quasi-diagonal matrics 表 3 Quasi-diagonal 矩 阵 信 息
QDIA = {ADIA1 ，ADIA2 ，…，ADIAN }
烅 { ， ，…， } (1)
编号
1
2
3
4
5
6
7
8
9
10
稀疏矩阵
bbmat
conf5_4-8×8-05epb2ex40lock1074nasa4704rg_n_2_15_s0rimted_Bxenon1
规模
38744*38744
49152*49152
25228*25228
7740*7740
1074*1074
4704*4704
32768*32768
22560*22560
10605*10605
48600*48600
NNZ 缩略图 1 771 722
1 916 928
175 227
456 188
51 588
104 756
320 480
1 014 951
144 579
1 181 120
QCSR = ACSR1 ACSR2 ACSRN Ai=ADIA +ACSR ，i∈[1，N]
ii
谈兆年等:面向异构计算平台的 SpMV 划分优化算法研究
595
Table 4 Information of Tetris matrices 表 4 Tetris 矩 阵 信 息
CPU-GPU 异 构 平 台 以 及 加 入 优 化 算 法 后 的 GFLOPS 值 。 在 实 验 中 ，所 有 数 据 为 运 行 1 000 次 后的均值。由于 CSR 格式在存储稀疏矩阵时非零 元素平均使用的字节数最为稳定[21]，因此在纯 GPU 平 台 上 使 用 CSR 格 式 计 算 SpMV。 在 静 态 划分之后，Quasi-diagonal模式的 GFLOPS平均值 是 GPU 的 1.43 倍 ，Tetris 模 式 的 GFLOPS 平 均
值 是 GPU 的 1.82 倍 。 在 加 入 优 化 之 后 ，Quasi-di- agonal 模 式 的 加 速 比 提 升 到 1 .74 ，Tetris 模 式 的 加速比提升到2.15。由于划分后的 Tetris模式矩 阵使用的是ELL和CSR的混合格式，这种格式处 理 非 结 构 化 矩 阵 时 效 率 比 C S R 格 式 高 得 多 [1 7 ] ， 因 此划分后获得了显著的加速效果，优化后的加速比 超过了2。静态划分方法没有考虑到 GPU 和
CPU 的 负 载 不 均 衡 ，优 化 后 的 负 载 更 加 均 衡 ， SpMV性能获得了较大的提升。
值 得 注 意 的 是 ，图 8 中 的 bbmat、rg g_n_2_15_ s0和xenon1这3个矩阵，划分后的 GFLOPS值低 于划分前，这是因为划分后它们的规则部分使用
DIA存储的效率并不高(接下来通过实验验证)。 但是，在加入协同优化之后，使得总体执行时间缩 短，计算性能仍优于 GPU 平台上的计算性能。
以 Quasi-diagonal 为 例 ，验 证 实 验 的 思 路 是 : 对原矩阵集合进行划分，得到集合QDIA 和QCSR ，在 GPU 平 台 上 分 别 使 用 DIA 和 CSR 格 式 对 集 合 QDIA 计 算 SpMV。 实 验 中 使 用 的 测 试 集 合 是 QDIA ，而不是原矩阵集合，原因有2点:(1)这样做 更加符合划分的思想，前面的实验中只有规则部分 使用了 DIA 格式，而不是原矩阵;(2)原矩阵中包 含不规则部分，会使 DIA 的存储效率大大降低，无 法发挥 DIA 格式的优势。同理，Tetris模式中，在 GPU 平 台 上 分 别 使 用 ELL 和 CSR 格 式 对 集 合
TELL 计算SpMV。图10展示了GPU平台上DIA
编号
11
12
13
14
15
16
17
18
19
20
稀疏矩阵
apach2
ar2010
ASIC_680ks
mn2010
msc10848
m_t1
ne2010
sc2010
t3dhvsp_finan51
2_scagr7- 2c_rlfddd
规模
715176*715176
186211*186211
682712*682712
259777*259777
10848*10848
97578*97578
193352*193352
181908*181908
79171*79171
139752*139752
NNZ 缩略图 4 817 870
904 310
1 693 767
1 227 102
1 229 776
9 753 570
913 854
893 160
4 352 105
1 104 040
不 难 看 出 ，Tetris 模 式 中 包 含 了 一 些 Quasi- diagonal 模 式 矩 阵 ，这 也 满 足 本 文 对 于 这 2 种 模 式 的定义，实际上，由于稀疏矩阵的稀疏模式复杂繁 多，很难将2种模式的稀疏矩阵完全分开，有一小
部分的重叠是不可避免的。 4.3 实验结果
图 8 和 图 9 为 Quasi-diagonal 和 Tetris 模 式 的实验结果，分别展示了每个矩阵在GPU平台、
Figure 8 Experimental results of Quasi-diagonal patern 图 8 Q uasi-diagonal 模 式 实 验 结 果
596 Computer Engine ering & Science计 算 机 工 程 与 科 学2019，41(4)
(或 ELL)格 式 相 对 于 CSR 格 式 的 加 速 比 。
由图10可以看出，加速比小于1的矩阵是
bbmat、rg g_n_2_15_s0 和 xenon1，这 和 图 8 的 实 验 结果是吻合的，特定的数据布局导致使用 DIA 格 式后性能稍微有所下降，因此划分后的执行效率也 有所降低。
5 结束语
本文广泛地分析了稀疏矩阵的数据分布特点， 总 结 出 2 种 主 要 的 模 式 :Quasi-diagonal 模 式 和 Tetris 模 式 。 在 CPU -GPU 异 构 系 统 中 ，使 用 特 定
的静态划分方法加速这2种模式的 SpMV 计算， 并提出一种基于 SVR 的任务优化算法，弥补了传 统 静 态 划 分 方 法 的 不 足 ，进 一 步 提 升 了 Sp M V 性 能。本文提出的算法与平台无关，可以推广到其它 异构计算系统中。
参考文献:
[1] Beck A，Teboule M.A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J].Siam Journal on Im- aging Sciences，2009，2(1):183-202.
[2] Shen J，Varbanescu A L，Lu Y，et al.Workload partitioning for acelerating applications on heterogeneous platforms[J].
IEEE Transactions on Paralel and Distributed Systems，
2016，27(9):2766-2780. [3] Filippone S，Cardelini V，Barbieri D，et al.Sparse matrix-vec-
tor multiplication on GPGPUs[J].ACM Transactions on Mathematical Software，2017，43(4):1-49.
[4]Maringanti A，Athavale V，Patkar S B，et al.Aceleration of conjugate gradient method for circuit simulation using CUDA [C]∥Proc of IEEE International Conference on High Per-
formance Computing，Data，and Analytics，2009:438-444. [5] Su B，Keutzer K.clSpMV:A cros-platform OpenCL SpMV framework on GPUs[C]∥Proc of International Conference
on Supercomputing，2012:353-364.
[6]Monakov A，Avetisyan A.Implementing blocked sparse ma-
trix-vector multiplication on NVIDIA GPUs[C]∥Proc of In- ternational Workshop on Embedded Computer Systems， 2009:289-297.
[7]Muralidharan S，Roy A ，Hal l MW ，et al.Architecture-adap- tive code variant tuning[J].Architectural Support for Pro- gramming Languages and Operating Systems，2016，51(4): 325-338.
[8] Yang W，Li K，Mo Z，et al.Performance optimization using partitioned SpMV on GPUs and multicore CPUs[J].IEEE Transactions on Computers，2015，64(9):2623-2636.
[9] Yang W D，Li K L，Li K Q，et al.A hybrid computing meth- od of SpMV on CPU-GPU heterogeneous computing systems [J].Journal of Paralel and Distributed Computing，2017，
104:49-60.
Figure 9 Experimental results of Tetris patern 图 9 T etris 模 式 实 验 结 果
igure 10 Spedup of DIA (or ELL)relative to CSR on GPU platform 图 10 GPU 上 DIA(或 ELL)相 对 CSR 的 加 速 比
谈兆年等:面向异构计算平台的 SpMV 划分优化算法研究
[10] Chen L，Vila O，Krishnamoorthy S，et al.Dynamic load bal- ancing on single-and multi-GPU systems[C]∥Proc of Inter- national Paralel and Distributed Procesing Symposium， 2010:1-12.
[11] Drucker H，Burges C J C，Kaufman L，et al.Support vector regresion machines[C]∥Proc of Neural Information Pro- cesing Systems Conference，1997:155-161.
[12] Sad Y.SPARSKIT:A basic tool kit for sparse matrix com- putations[R].Ilinios University of Ilinios，1994.
[13]Meril D，Garland M.Merge-based paralel sparse matrix- vector multiplication[C]∥Prco of the International Confer- ence for High Performance Computing，Networking，Stror- age and Analytics，2016:Article No.58.
[14] Dazevedo E F，Fahey M R，Mils R T，et al.Vectorized sparse matrix multiply for compresed row storage format [C]∥ Proc of International Conference on Computational
Science，2005:99-106. [15] Remington K，Pozo R.NIST sparse BLAS:User’s guide:
Technical Report NISTIR 6744[R].Caithersbury:National Institute of Standards and Technology，1996.
[16] Davis T A，Hu Y.The University of Florida sparse matrix colection[J].ACM Transactions on Mathematical Soft-
ware，2009，38(1):1-25. [17] Bel N，Garland M.Implementing sparse matrix-vector mul-
tiplication on throughput-oriented procesors[C]∥Proc of IEEE International Conference on High Performance Com- puting Data and Analytics，2009:1-11.
[18] Benatia A，Ji W，Wang Y，et al.Machine learning approach for the predicting performance of SpMV on GPU[C]∥Proc of International Conference on Paralel and Distributed Sys- tems，2016:894-901.
[19] CUSP.The NVIDIA library of generic paralel algorithms for sparse linear algebra and graph computations on CUDA architecture GPUs[EB/OL].[2018-05-15].htps://devel- oper.nvidia.com/cusp.
[20] Intel.Intel math kernel library[EB/OL].[2012-12-10].ht- tp://software.intel.com/en-us/intel-mkl.
[21] Bel N，Garland M.Eficient sparse matrix-vector multiplica- tion on CUDA:NVIDIA Technical Report NVR-2008-004
[R].Santa Clara:NVIDIA Corporation，2008.
597 didate，CCF member(80204G)，his research interests in-
clude high performance computing，and machine learning.
计 卫 星 (1980-)，男 ，陕 西 咸 阳 人 ，博 士 ，副 教 授 ，CCF 会 员 (16954M )，研 究 方 向 为 并 行 计 算 、代 码 分 析 与 优 化 。 E-mail:
[email protected] JI Wei-xing，born in 1980，PhD，aso-
ciate profesor，CCF member(16954M)，his research inter- ests include paralel computing，and code analysis & opti-
mization.
Akrem Benatia(1990-)，男 ，阿 尔 及 利 亚人，博士生，研究方向为高性能计算和计 算 机 体 系 结 构 。E-mail:Akrem.benatia@
yahoo.com AKREM Benatia，born in 1990，PhD
作者简介:
candidate，his research interests include high performance computing，and computer architecture.
高 建 花 (1995-)，女 ，山 西 临 县 人 ，硕 士 生 ，CCF 会 员 (79759G )，研 究 方 向 为 高 性 能 计 算 。E-mail:[email protected]
GAO Jian-hua，born in 1995，MS can- didate，her research interest includes high
performance computing.
李 安 民 (1994-)，男 ，湖 南 石 门 人 ，硕 士
生 ，CCF 会 员 (80264G )，研 究 方 向 为 体 系 结 构 和 高 性 能 计 算 。 E-mail:momentum @
bit.edu.cn LI An-min，born in 1994，MS candi-
date，CCF member(80264G)，his research interests include computer architecture，and high performance computing.
王 一 拙 (1979-)，男 ，陕 西 周 至 人 ，博 士 生 ，讲 师 ，CCF 会 员 (E200022292M )，研 究 方 向 为 体 系 结 构 和 并 行 编 程 。 E-mail:
[email protected] WANG Yi-zhuo，born in 1979，PhD
candidate，lecturer，CCF member(E200022292M )，his re- search interests include computer architecture，and paralel programming.
谈 兆 年 (1994-)，男 ，安 徽 肥 东 人 ，硕 士 生 ，CCF 会 员 (80204G )，研 究 方 向 为 高 性 能 计 算 和 机 器 学 习 。 E -mail:tan _zn @
163.com TAN Zhao-nian，born in 1994，MS can-
Reviews
There are no reviews yet.