矩阵运算及其OMP并行优化技术

作者: MoBaiGeneral 分类: 并行技术 发布时间: 2021-08-30 12:50 访问量:13,670
FavoriteLoading收藏

0 引言

 

本文将基于c编程环境,粗浅论述关于稠密矩阵的加法、乘法运算及其简单并行优化,稀疏矩阵的快速转置算法、乘法运算以及乘法并行优化。其中,算法的优化过程以OpenMP技术为主。相关源代码可参考矩阵运算C代码


1 稠密矩阵运算

 

本文讨论的稠密矩阵涉及的运算操作主要有加法以及乘法运算。

其中,加法运算针对维度为n的a,b向量求和,分别采用串行、OpenMP并行以及AVX指令方式获得结果向量c。为了突显不同向量加法运算的性能差别性,将此向量加法运算执行多次,并分别进行时间统计。值得注意的是程序不仅仅需要加入omp.h、immintrin.h等头文件,还需要在对程序进行编译前加入-fopenmp -march=native命令。对于维度为(m,k)的矩阵A与维度为(k,n)的矩阵B的乘法运算,分别采用了七种方法进行求解。其中涉及矩阵A、B分别以行、列形式存储下的乘法运算,引入avx2指令集,并通过#pragma omp parallel for语句设置并行,omp_set_num_threads()设置并行线程数量。


2 稀疏矩阵运算

 

稀疏矩阵在一系列的运算操作前,通常需要以某种特定的方式进行压缩。与稠密矩阵不同,稀疏矩阵中非零元素数据量占矩阵总元素量的比重极少,对稀疏矩阵的压缩操作能够节省大量的数据存储空间,在另一方面,同样能够提高矩阵的运算性能。在本文中,矩阵的每一个元素是包含了行号、列号和元素值的三元组结构体。而稀疏矩阵则可以由三元组顺序表或者行逻辑链接顺序表定义。其中,三元组顺序表由行数mu、列数nu、非零元素数tu以及一个指向矩阵元素链表的指针构成,更一般地, 行逻辑链接的顺序表较其多了一个表征各行第一个非零元的位置的变量表rpos。这两种方式定义的稀疏矩阵的压缩算法大体相似,主要区别于后者需要对定义rpos表。对稀疏矩阵进行压缩处理后,分别可以进行转置运算、乘法运算。

以三元组顺序表定义的稀疏矩阵A为例进行稀疏矩阵的转置运算,运算过程中需要利用变量num存储矩阵A中某列的非零元素的个数,变量cpot表示矩阵A中某列的第一个非零元素在转置矩阵B中的位置。对变量进行0值初始化,先后为变量num和cpot赋值,通过矩阵A中第p个元素的列值col,获得第col列的第一个非零元在矩阵B中位置q,最后则可将A中第p个元素存储到B中第q个元素位置。

以行逻辑链接顺序表定义的稀疏矩阵M、N为例进行稀疏矩阵的乘法运算,其中矩阵M的列数必须与矩阵N的行数相等。定义乘积结果矩阵Q并进行初始化赋值,其中,行数为矩阵M的行数,列数为矩阵N的列数,非零元素数为0,rpos表长度为矩阵M的行数。针对矩阵M中的每一行,执行以下操作:为当前行各元素设置累加器并清零,设置矩阵M每行的上限标号,即每行非零元素的位置范围,当前行中每一非零元,找到其在矩阵N中的行号N-row并设置矩阵N该行的上限标号,即该行非零元素的位置范围,进而求得Q中第row行的非零元。并对其进行压缩存储。

对于稀疏矩阵乘法的并行,对OpenMP技术为例,对矩阵M的每一行设置并行。值得注意的是,由于并行操作,每一行的累加器需要有独立的存储空间,每行内部的元素计算同串行方法,但是运算结果要保存在中间稠密矩阵S中暂存,最后要将得到的矩阵Q中rpos表以scan算法做二次处理,再次使用并行手段,基于rpos表,将矩阵s快速转存为稀疏矩阵Q,此则完成了稀疏矩阵M与稀疏矩阵N作乘积得到稀疏矩阵Q的全过程。

     

如果觉得小墨的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

一条评论

发表评论