これは動的プログラミングの問題であり、単純な実装ではデータ依存性が多すぎて 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 命令が必要かどうかわからない、または計算を並列化/ベクトル化する方法を知っているだけです。