CN114048035B 基于csr特点对稀疏稠密矩阵乘法并行算法的优化方法 （中山大学）

EP2657842A1,2013.10.30基于CSR特点对稀疏稠密矩阵乘法并行算法本发明公开了一种基于CSR特点对稀疏稠密矩阵乘法并行算法的优化方法，包括CSR稀疏矩2S7依据当前线程号以及负载均衡分配公式求出当前线程计算任务中稠密矩阵的起始S8各个线程从缓冲区中取出稀疏矩阵数据并与稠2.根据权利要求1所述的基于CSR特点对稀征在于，所述CSR稀疏矩阵数据缓冲区设计能够根据稀疏矩阵的大小自适应地配置缓冲区3.根据权利要求1所述的对基于CSR特点对稀特征在于，所述缓冲区并行数据预加载的负载均衡是能够根据不同稀疏矩阵的行元素个数，将CSR稀疏矩阵某一行数据划分为均匀的数据块，分配给不同的并行线程加载至缓冲所述稠密矩阵计算任务对线程的负载均衡是将矩阵乘法的核心运算3[0001]本发明涉及计算机并行计算领域以及计算机体系结构领域，具体涉及一种基于现实的图神经网络的训练中，图往往是稀疏的，卷积算法一般是基于稀疏稠密矩阵乘法[0003]CompressedSparseRow(CSR)是一种将稀疏矩阵按行顺序进行压缩存储的数据[0005]鉴于现有技术的不足，本发明旨在于提供一种基于CSR特点对稀疏稠密矩阵乘法[0007]基于CSR特点对稀疏稠密矩阵乘法并行算法的优化方法，包括CSR稀疏矩阵数据4[0014]S7依据当前线程号以及负载均衡分配公式求出当前线程计算任务中稠密矩阵的[0015]S8各个线程从缓冲区中取出稀疏矩阵数据并与稠密矩阵中所属数据进行点乘运[0019]需要说明的是，所述CSR稀疏矩阵数据缓冲区设计能够根据稀疏矩阵的大小自适[0028]图5为本发明中的基于CSR特点对稀疏稠密矩阵乘法并行算法的优化方法流程示5[0031]SpMM(Sparse-DenseMatrix-MatrixMultiplication稀疏稠密矩阵乘法)：矩阵[0041]S7依据当前线程号以及负载均衡分配公式求出当前线程计算任务中稠密矩阵的[0042]S8各个线程从缓冲区中取出稀疏矩阵数据并与稠密矩阵中所属数据进行点乘运[0046]需要说明的是，所述CSR稀疏矩阵数据缓冲区设计能够根据稀疏矩阵的大小自适6以看到矩阵中存在大量的零元素值。右侧是在计算机中实际存储的CSR格式数据，包括偏[0053]示例中的a-g表示矩阵中的非零值，在实际计算中一般为数值。而物理存储中的所在的列号，val数组则存储实际的值。colInd数组和val数组等长，长于rowPtr数组，rowPtr数组中的最后一个元素表示val[0054]在本发明的实际设计中，缓冲区大小设定为rowPtr中所有相邻元素的最大差即稀疏矩阵中的最多非零元素行的非零元素个数，上述方法能够减少对矩阵的一次遍历。[0056]SpMM是实现卷积算法的一种重要的方式，而目前针对CSR存储格式采用的并行化[0061]图3是缓冲区的详细设计以及数据预加载策略的示意图，7[s/threadsl,其中s为该行中非零元素个数。[0064]图4为稠密矩阵计算数据的负载均衡策略示意图，稠密矩阵中的计算数据按列划方式能够保证在计算时能够利用空间局部性原理[0069]图5为基于CSR存储利用缓冲区及负载均衡对稀疏稠密矩阵乘法并行计算的优化[0076]7)依据当前线程号以及负载均衡分配公式求出当前线程计算任务中稠密矩阵的[0077]8)各个线程从缓冲区中取出稀疏矩阵