一种稀疏矩阵向量乘法的异构并行计算方法

一种稀疏矩阵向量乘法的异构并行计算方法

技术领域

本发明涉及一种数据存储方法，特别涉及一种稀疏矩阵向量乘法的异构并行计算方法。

技术背景

疏矩阵向量乘法(SparseMatrix-VectorMultiplication，简称SpMV)是科学计算和工程应 用中最常用的计算之一。在很多数据挖掘应用中，经常会遇到数据极度稀疏的情况，这种类 型的数据通常表示为稀疏矩阵。在数据规模非常大的时候，利用目前流行的CPU-GPU异构 计算平台来实现SpMV异构并行计算是非常必要的。

一般而言，在异构平台上进行SpMV计算，有以下两种计算模式：

第一种模式是CPU/GPU协同计算，CPU把数据处理好，让后把数据发送给GPU计算， GPU计算完成之后把数据传输回CPU。整个过程虽然说是并行，实际上CPU和GPU的工作 却是串行的，在GPU进行计算时，CPU空置，把CPU的计算能力浪费掉了。

第二种模式是CPU/GPU共同计算，CPU把数据处理好后，进行任务划分，把一部分数 据传输到GPU上，之后与GPU共同完成所有的计算任务。这种模式相比前一种模式，在GPU 计算的同时利用到了CPU的计算能力。即便如此，这种模式仍然有所不足，它把CPU和GPU 作为对等的计算节点，分配相似的计算任务，这忽视了CPU和GPU体系结构上的差异，将 导致CPU和GPU都不能达到最高性能。

在稀疏矩阵向量乘法中，稀疏矩阵存储是一个关键问题，直接影响计算性能。目前来看， 主流的稀疏矩阵存储形式有：坐标格式(CoordinateFormat，简称COO)，稀疏行压缩格式 (CompressedSparseRowFormat，简称CSR)，对角线格式(DiagonalFormat，简称DIA)， ellpack格式(ELLPACKformat，简称ELL)等存储形式，每种存储形式各有特，各有自己 最适合的应用场景。文章“EfficientSparseMatrix-VectorMultiplicationonCUDA”Technical ReportbyNathanBell,MichaelGarland的研究显示:在SpMV任务中，使用DIA和ELL稀疏矩 阵存储方式能够更好地利用GPU的带宽，不过ELL存储方式的性能受具体数据分布影响较 大；在SpMV任务中COO和ELL的混合模式最在GPU上性能最好，因为它利用到GPU处 理ELL时展现出的优势，又通过结合COO来规避ELL的缺陷。而CSR是一种最常见的系 数矩阵存储形式，它是COO的进一步压缩形式，相对于别的数据存储方式更加适合使用CPU 处理。但目前所有这些存储方式，都不适合在CPU-GPU异构计算平台上进行处理。

发明内容

本发明的目的在于克服现有技术的缺点与不足，提供一种稀疏矩阵向量乘法的异构并行 计算方法。

本发明的目的通过如下技术方案实现：一种稀疏矩阵向量乘法的异构并行计算方法，包 括以下步骤：

S1、确定稀疏矩阵的可调参数K的取值；

S2、CPU读取存储于硬盘上的稀疏矩阵数据，并根据稀疏矩阵的可调参数K申请内存存 储空间，所述内存存储空间包括ELL存储结构和CSR存储结构需要的存储空间；同时也申请 ELL存储结构需要的GPU存储空间；

S3、将稀疏矩阵数据进行压缩后存储在CPU所申请的内存存储空间中生成混合存储结构；

S4、把ELL存储结构中存储的数据复制到GPU存储空间中进行存储；

S5、使用处理完成的存储结构进行稀疏矩阵向量乘法，CPU计算CSR存储结构对应运算， GPU计算ELL存储结构对应运算，CPU和GPU处理结果相加得到最终结果。

步骤S3中，在将所述稀疏矩阵压缩后存储时，首先将所有能够存储于ELL的数据填充在 ELL结构中，然后将剩余的数据按照CSR存储结构通常的存储方式，存储到CSR存储结构中。

步骤S3中，在对所述稀疏矩阵进行压缩时，对于针对列进行压缩的情况，所述矩阵数据 依列填充到数组上；对于针对行进行压缩的情况，所述矩阵数据依行填充到数组上。

步骤S4中，把所述ELL存储结构中的数据复制到GPU存储空间的具体做法是将内存中混 合存储结构中ELL存储结构中的数据内容复制并传输到GPU存储空间上ELL存储结构的对应 位置上，同时，CPU释放内存中对应的数据空间。

本发明与现有技术相比，具有如下优点和有益效果：

1、本发明的计算方法可以使计算机在进行SpMV计算任务时，同时利用CPU和GPU的计 算能力，使CPU和GPU可以各自发挥最优的计算特性。

2、本发明生成方法简单，可以很容易地扩展到集环境。

附图说明

图1为本发明所述的一种稀疏矩阵向量乘法的异构并行计算方法的流程图。

具体实施方式

下面结合实施例及附图对本发明作进一步详细的描述，但本发明的实施方式不限于此。

一种稀疏矩阵向量乘法的异构并行计算方法，具体包括以下步骤：

S1、确定稀疏矩阵的可调参数K的取值。

K值用于标识可以把ELL矩阵压缩到最小的数量。在Hybrid(ELL+COO/CSR)时K值用于 决定多少数据存于ELL，多少存于COO/CSR在本存储结构中，可以认为K值决定GPU和CPU 的计算量。K值越大，会使GPU计算量越大，CPU计算量越小。K值取最优的时候可以使CPU 和GPU完成计算的时间相等。K值可以简单使用平均值来确定。即对于数据依列压缩，则用 每行平均数据量作为K值；对于数据依行压缩，则用每列平均数据作为K值。

S2、CPU读取存储于硬盘上的稀疏矩阵，并根据所述可调参数K申请内存存储空间，包 括ELL存储结构和CSR存储结构需要的存储空间；同时GPU也申请ELL存储结构需要的GPU 存储空间。

S3、将矩阵数据填充在CPU所申请的内存存储空间中生成混合存储结构。

S4、把ELL存储结构中存储的数据复制到GPU所申请的GPU存储空间中进行存储。

S5、使用处理完成的存储结构进行稀疏矩阵向量乘法，CPU计算CSR存储结构对应运算， GPU计算ELL存储结构对应运算，CPU和GPU处理结果相加得到最终结果。

所述步骤S2中ELL存储结构包括数组ell_data和ell_indexes，CSR存储结构包括数组 csr_data，csr_indexes和csr_ptr。

所述步骤S3中，首先将所有能够存储于ELL的数据填充在ELL结构中，然后将剩余的数 据按照CSR存储结构通常的存储方式，存储到CSR存储结构中。

所述步骤S3中，在对稀疏矩阵进行压缩时，对于针对列进行压缩的情况，所述矩阵数据 依列填充到数组上；对于针对行进行压缩的情况，所述矩阵数据依行填充到数组上。

所述步骤S4中，将内存中混合存储结构中ELL存储结构中的数据内容复制并传输到GPU 存储空间上ELL存储结构的对应位置上，同时，CPU释放内存中对应的数据空间。

所述步骤S5中，GPU根据存储于GPU存储空间上的ELL结构进行稀疏矩阵向量乘法，同 时CPU根据存储与内存空间上的CSR结构进行系数矩阵向量乘法，CPU与GPU得到的计算结 果求和。

为更清楚地阐述本发明的原理，以下以实施例说明本发明的实现过程。

本过程以针对列进行数据压缩为例。首先CPU读取矩阵文件如下：

1 2 3 4 5 6 7 8 9 10

1 3 1

2 5 3 9

3 2

4 7 3 9

5 5

6 1 3 2

7 2 1

8 9 2

9 5 1

10 5 6 3

由读取数据信息可知总行数10，总非零数据数23，平均每行数据数2.3，可取K＝2。申 请内存存储空间，具体地，ell_data大小为20，ell_indexes大小为20，csr_data大小为4。填 充数据到ELL存储结构上。

其抽象形式为：

数据依列填充到数组上得：

ell_data[]＝{3,5,2,7,5,1,2,9,5,5,1,3,-,3,-,3,1,2,1,6}

ell_indexes[]＝{1,2,4,2,3,1,3,2,4,1,6,8,-,7,-,5,6,8,7,6}

2.2)把剩余数据填充到CSR结构的数组上上：

csr_data[]＝{9,9,2,3}

csr_indexes[]＝{10,9,9,8}

csr_ptr[]＝{0,0,1,1,2,2,3,3,3,3,4}

GPU将内存中混合存储结构中ELL存储结构中的数据内容复制并传输到GPU存储空间上 ELL存储结构的对应位置上，同时，CPU释放内存中对应的数据空间，完成矩阵存储过程。

现假设使用该矩阵和如下向量做矩阵向量乘法

Vector＝{2,1,0,2,5,0,2,3,0,5}

使用本存储结构进行系数矩阵向量乘法过程描述如下：

GPU根据存储于GPU存储空间上的ELL结构进行稀疏矩阵向量乘法，可得到结果：

GPU_Result＝{6,14,4,13,0,17,0,15,12,10}

CPU根据存储与内存空间上的CSR结构进行系数矩阵向量乘法，可得结果：

CPU_Result＝{0,45,0,0,0,0,0,0,0,9}

最终CPU_Result和GPU_Result相加得到：

Result＝{6,59,4,13,0,17,0,15,12,19}

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制， 其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应 为等效的置换方式，都包含在本发明的保护范围之内。