SpMV算法设计和优化-r programming for bioinformatics
7.2 SpMV算法设计和优化7.2.1 SpMV基本算法及其并行化下面一段伪代码展示了一种串行的SpMV算法。CSR格式稀疏矩阵A和稠密向量R相乘，结果为Y。在CSR格式中，A的每一行非零元素都是顺序、连续存储的，存储的位置从Ap中可以很方便得得到，为rbegin（包含）至rend（不含）。对于A的某一行，需要读取R中对应于该行非零元素位置的所有数据。即根据列坐标Aj，从R中读出元素R[Aj[c]]，这个操作通常称为Gather。接着将Av中的数据与R中相应元素相乘并累加。累加的操作属于Reduce的一种，即用一个符合结合率的二元算符（这里是浮点加法）将多个数据合并为一个。累加的结果正式乘积向量Y的一个元素。如此对A的所有行操作，就得到了完整的乘积Y。事实上，上面的算法包含了内在的并行性。显然，A的任意两行的处理是没有互相的数据依赖关系的。体现在代码上，即上面的算法中，外层循环是可以并行处理的。然而，简单得用每个GPU线程来处理A中的每一行，并不能获得理想的性能。那么如何根据AMD GPGPU的特性，利用OpenCL获得尽可能高的性能呢？我们将在随后几节详细讨论。 1 // input : A_v[ N_nz] , A_j [ N_nz] , A_p[ m+1] 2 // input : R[ n ] 3 // output : Y[ m] 4 for ( i = 0; i < m ; i ++ ) 5 { 6 r_begin = A_p [ i ]; 7 r_end = A_p [ i +1]; 8 acc = 0; 9 for ( c = r_begin ; c < r_end ; c ++ ) 10 { 11 acc += A_v [ c ] * R [ A_j [ c ]]; 12 } 13 Y [ i ] = acc ; 14 }
文件大小：5.07MB
评论区