ベクトル化ネステッド・ループは - SIMD

Question

誰でもに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; 
    } 
} 

Answer 1

は私が解決策を提案してみましょう。最初に、L [i] [0]およびL [0] [j]の値を計算する。今度は、i = 1とj = 1から反復を開始します。ループの各繰り返しで、i == 0またはj == 0のチェックを取り除くことができます。そしてこれのもう一つの利点は、各行の各反復において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; 
    } 
} 

一つの欠点は、今、我々は関係なくREFSEQ [i]は[J]、またはしない対角要素のみ配列いる場合にアクセスされる元のコードと同様otherSeqに等しい場合、前の行をロードしていないことであろうは同じ。

Answer 2

これはダイナミックプログラミングの問題であり、ストレートフォワード実装ではSIMD計算に適したデータ依存性があります。

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

以下「擬似」コードが「内側」の計算を簡単にするために1余分な行/列を有する行列を使用します。この余分な行/列はすべての対角反復の前に初期化されます。あなたは計算のために、実際のSIMD命令を望んでいた、または単に/並列計算をベクトル化する方法を知っていれば

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; 
    } 
} 

わかりません。