压缩列存储中的稀疏矩阵与列向量的乘法

Question

我必须将压缩列存储中的稀疏矩阵与列向量相乘（我必须在开放式cl中并行化它）。我在互联网上进行了搜索。花了很多天但找不到任何东西。（我被允许搜索互联网因为我必须将其转换为并行）。但我只能找到压缩行存储的代码。

spmv_csr_serial(const int num_rows ,
                const int * ptr ,
                const int * indices ,
                const float * data ,
                const float * x,
                float * y)
{
    for(int row = 0; i < num_rows; i++){
        float dot = 0;
        int row_start = ptr[row];
        int row_end = ptr[row+1];

        for (int jj = row_start; jj < row_end; jj++)
            dot += data[jj] * x[indices[jj]];

        y[row] += dot;
    }
}

压缩列存储没有行指针。那么如何将它与向量相乘呢？我只需要串行代码，然后我自己将其转换为并行代码。

这是我用于该项目的 OpenCL 内核

enter code here
__kernel void mykernel(__global const int* val,__global const int* index,__global const int * ptr,__global const int* x,__global int* y) 
{ 
    int id=get_global_id(0); 
    int colstart=ptr[id]; 
    int colend=ptr[id+1]; 
    for(int j=colstart;j<colend;j++) 
    { 
        y[index[j]]=val[j]*x[index[j]]; 
    } 
}

此代码在 open cl 内核中返回垃圾值。这是我的序列号。

   spmv_csr_serial(const int num_rows ,
                const int * ptr ,
                const int * indices ,
                const float * data ,
                const float * x,
                float * y)
{
    for(int row = 0; i < num_rows; i++){
        float dot = 0;
        int colstart = ptr[row];
        int colend = ptr[row+1];

      for(int j=colstart;j<colend;j++) 
    { 
        y[index[j]]=val[j]*x[index[j]]; 
    }

    }
}

密集矩阵向量乘法算法

For(int i=0;i<A.RowLength;i++) 
{
    For(int j=0;j<vector.length;j++) 
    { 
        Result[i]=Result[i]+A[i][j]*vector[j];
    }
} 

Answer 1

一般来说，进行矩阵向量计算的算法如下

y = 0
for i = 0 : Nr - 1
    for j = 0 : Nc - 1
        y[i] += M[i,j] * x[j]

压缩行存储：

我们不是对所有列进行普通循环，而是仅对非零条目进行循环：

y = 0
for i = 0 : Nr - 1
    for j = 0 : numElementsInRow(i) - 1
        y[i] += M[i, columnIndex(i,j)] * x[columnIndex(i,j)]

其中返回第 - 行numElementsInRow(i)中的非零数，并给出第 - 行中的第 - 列索引。icolumnIndex(i,j)ji

在上面的实现中，columnIndex(i,j)映射是由两个数组ptr和完成的indices，即 columnIndex(i,j) == indices[ptr[i] + j]元素数量由 给出 numElementsInRow(i) == ptr[i+1] - ptr[i]。不需要对矩阵进行索引，因为您只存储它的压缩版本。

压缩列存储：

现在更改两个循环的顺序并循环遍历行中的非零：

y = 0
for j = 0 : Nc - 1
    for i = 0 : numElementsInColumn(j) - 1
        y[rowIndex(j,i)] += M[rowIndex(j,i), j] * x[j]

其余的与CRS格式类似。