0

SIMD を使用してこのようなものをベクトル化することを知っている人はいますか?

for(size_t i = 0; i < refSeq.length() / 4; i++){

    for(size_t j = 0; j<otherSeq.length(); j++){
    if(refSeq[i] == otherSeq[j]){
        if(i == 0 || j == 0)
            L[i][j] = 1;
       else
        L[i][j] = L[i-1][j-1] + 1;
    }
       else
        L[i][j] = 0;
    }
}
4

3 に答える 3

1

解決策を提案してみましょう。最初に L[i][0] と L[0][j] の値を計算します。i=1 と j=1 から反復を開始します。これで、ループの各反復における i==0 または j==0 のチェックを削除できます。また、これのもう 1 つの利点は、行の各反復の L[i][j] ごとに、L[i-1][j-1] の値が利用できることです。ここで、ベクトル レジスタが配列の 4 つの要素を保持できるとします。これで、refSeq、otherSeq、L(前の行)、L(現在の行)の 4 つの要素を読み込むことができます。理論的には、現在ベクトル化されています。自動ベクトライザーはこれを認識しないと思います。そのため、手動で行う必要があります。私が間違っている場合は、私を修正してください。

for(size_t i=0;i<refSeq.length()/4;i++)
{
    if(refSeq[i]==otherSeq[0])
        L[i][0]=1;
    else
        L[i][0]=0;
}
for(size_t j=0; j<otherSeq.length();j++)
{
    if(refSeq[0]==otherSeq[j])
        L[0][j]=1;
    else
        L[0][j]=0;
}

for(size_t i=1;i<refSeq.length()/4;i++)
{
    for(size_t j=1; j<otherSeq.length();j++)
    {
        if(refSeq[i]==otherSeq[j])
            L[i][j] = L[i-1][j-1] + 1;
        else
            L[i][j]=0;
    }
}

欠点の 1 つは、refSeq[i] が otherSeq[j] と等しいかどうかに関係なく、シーケンスが等しい場合にのみ対角要素にアクセスする元のコードのように、前の行をロードしていることです。

于 2012-07-23T08:36:44.620 に答える
1

これは動的プログラミングの問題であり、単純な実装ではデータ依存性が多すぎて SIMD 計算に適していません。

ただし、アルゴリズムを行方向の反復から対角方向の反復に変更すると、対角線全体を並列に計算できます。下の画像を参照してください。

ここに画像の説明を入力

以下の「疑似」コードは、「内部」計算を単純化するために、1 つの余分な行/列を持つ行列を使用します。この余分な行/列は、すべての対角反復の前に初期化されます。

int i, j, k;
for (k = 1; ; k++) {
    int minI = k > refLen ? k - refLen : 1;
    int maxI = k > otherLen ? otherLen : k - 1;

    for (i = maxI; i >= minI; ) {
        j = k - i;

        // vectorized calculation 256 bit (AVX2)
        if (i >= 32 && otherLen - j >= 32) {
            // calculate 32 values of the diagonal with SIMD
            i -= 32;
            continue;
        }

        // vectorized calculation 128 bit (SSE)
        if (i >= 16 && otherLen - j >= 16) {
            // calculate 16 values of the diagonal with SIMD
            i -= 16;
            continue;
        }

        // scalar calculation
        if (refSeq[i - 1] == otherSeq[j - 1]) {
            L[i][j] = L[i - 1][j - 1] + 1;
        } else {
            L[i][j] = 0;
        }
        i--;
    }

    if (k == otherLen + refLen) {
        break;
    }

    // initialize next j-endpoint in diagonal
    if (k <= refLen) {
        L[0][k] = 0;
    }
    // initialize next i-endpoint in diagonal
    if (k <= otherLen) {
        L[k][0] = 0;
    }
}

計算に実際の SIMD 命令が必要かどうかわからない、または計算を並列化/ベクトル化する方法を知っているだけです。

于 2016-03-14T20:58:25.347 に答える