-1

圧縮された列ストレージのスパース行列を列ベクトルで乗算する必要があります (オープン 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;
    }
}

圧縮された列ストレージには行 ptr がありません。では、どうすればそれをベクトルで乗算できますか? シリアルコードが必要なだけで、自分でパラレルに変換します。

このプロジェクトの 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]]; 
    } 
}

このコードは、オープン 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];
    }
}
4

3 に答える 3

5

一般に、行列ベクトル計算を行うアルゴリズムは次のとおりです。

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)]

whereは、 - 番目の行numElementsInRow(i)のゼロ以外の数を返し、 - 番目の行の- 番目の列インデックスを示します。icolumnIndex(i,j)ji

上記の実装では、マッピングはとcolumnIndex(i,j)の 2 つの配列によって行われます。つまり 、要素の数は で与えられ ます。マトリックスの圧縮バージョンのみを保存するため、マトリックスにインデックスを付ける必要はありません。ptrindicescolumnIndex(i,j) == indices[ptr[i] + j]numElementsInRow(i) == ptr[i+1] - ptr[i]

圧縮カラム ストレージ:

次に、2 つのループの順序を変更し、行の非ゼロをループします。

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 形式に類似しています。

于 2012-09-04T15:13:24.587 に答える
1
  1. 密な行列とベクトルの乗算のアルゴリズムを書きます。これを行う方法がわからない場合は、基本的な線形代数の教科書を調べるか、教授に尋ねてください。
  2. アルゴリズムは、行列の行と列の両方を反復します。必要に応じてアルゴリズムを再調整し、内側のループが列を超えるようにします。
  3. アルゴリズムを変更して、マトリックスへのアクセスに高密度ストレージ スキームを使用します。
于 2012-09-04T14:56:57.043 に答える
1

CCS は CRS に似ていますが、転置されているだけです。行ポインターはありませんが、同様の列ポインターがあります。したがって、シーケンシャルループは

for(int col=0; col<num_cols; col++){
  for(int j=ptr[col];j<ptr[col+1]; j++) { 
    y[indices[j]] += val[j]*x[col]; 
  }
}

前に y ベクトルをゼロにすることを忘れないでください。

どっちが速いと思いますか？CCSまたはCRS？

于 2012-09-04T16:40:35.293 に答える