准对角矩阵与向量相乘在CPU+GPU异构集群上的实现与优化

稀疏矩阵与向量相乘(Sp MV)是科学计算和工程应用中一个重要问题,而且非常适宜进行并行计算,目前在GPU对Sp M V的实现和优化是一个研究热点.针对准对角矩阵存在的一些不规则性,采用CSR+DLA混合存储格式来进行Sp M V计算,能够提高压缩的效果.为了发挥CPU多核的并行计算能力,采用一种CPU+GPU混合计算模式,这样可以把混合存储格式不同格式的数据分割到CPU和GPU上,从而提高了资源的利用效能.本文另外还在分析CPU+GPU异构计算模式的特征基础上,提出一些优化策略,能够改进准对角矩阵与向量相乘在异构计算环境中的计算性能.

一种准对角矩阵的混合压缩算法及其与向量相乘在GPU上的实现

稀疏矩阵与向量乘(SpMV)属于科学计算和工程应用中的一种基本运算,其高性能实现与优化是计算科学的研究热点之一。在微分方程的求解过程中会产生大规模的稀疏矩阵,而且很大一部分是一种准对角矩阵。针对准对角矩阵存在的一些不规则性,提出一种混合对角存储(DIA)和行压缩存储(CSR)格式来进行SpMV计算,对于分割出来的对角线区域之外的离散非零元素采用CSR存储,这样能够克服DIA在不规则情况下存储矩阵的列迅速增加的缺陷,同时对角线采用DIA存储又能充分利用矩阵的对角特征,以减少CSR的行非零元素数目的不均衡现象,并可以通过调整存储对角线的带宽来适应准对角矩阵的不同的离散形式,以获得比DIA和CSR更高的压缩比,减小计算的数据规模。利用CUDA平台在GPU上进行了实验测试,结果表明该方法比DIA和CSR具有更高的加速比。

大规模图挖掘算法并行化研究

目前大规模图挖掘算法的思路是基于MapReduce将矩阵与向量相乘的过程并行化,但却没有针对MapReduce特点对图数据进行划分,会产生大量中间结果,算法代价较高。针对这些问题,提出了GIM-V LI算法。该算法采用数据划分思想,将图矩阵横向划分,结合MapReduce特点以行为单位替代点或块的数据组织方式,并设计出<key,value>结构,使一个单位数据仅产生一个中间结果,从而大大减少了中间结果,提高了算法的性能。通过大量实验分析验证了该改进算法的正确性与有效性。