c++ - 向量化嵌套循环-SIMD

有谁知道要使用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;
    }
}

最佳答案

这是一个动态的编程问题，海峡前移的实现具有太多的数据依赖性，因此不适合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指令进行计算，还是只知道如何并行/向量化计算。

关于c++ - 向量化嵌套循环-SIMD，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10508440/