Levenshtein 算法并行

Question

我已经使用parallel_for 实现了该算法。但大多数情况下我使用同步部分，所以我没有利润。也许有更好的选择？

    tbb::parallel_for (tbb::blocked_range<int>(1, m * n), apply_transform(d, j, this, m, n));

    void apply_transformation(int * d, int i, int j, int n){
        int elem1 = (*v1)[i];
        int elem2 = (*v2)[j];
        if(elem1 == elem2){
            dLock.acquire(dMutex);
            d[i*n + j] = d[(i-1)*n + j-1];       // no operation required
            dLock.release();
        } else {
            dLock.acquire(dMutex);
            d[i*n + j] = std::min(std::min(d[(i-1)*n + j] + 1, //deletion
                    d[i*n + j-1] + 1), //insertion
                    d[(i-1)*n + j-1] + 1); //substitution
            dLock.release();
        }
    }

    class apply_transform{
        int * array;
        int m_j;
        Levenstein * m_l;

        int m, n;
        public:
            apply_transform (int* a, int j, Levenstein * l, int width, int height):
                array(a), m_j(j), m_l(l), m(width), n(height) {}

            void operator()(const tbb::blocked_range<int>& r ) const {
                for (int i=r.begin(); i!=r.end(); i++ ){
                    m_l->apply_transformation(array, i, m_j, n);
                }
            }
    };

Answer 1

所述编辑距离的计算本质上是一个波前图案，其中的计算d(i,j)需要的知识d(i-1,j-1)，d(i-1,j)和d(i,j-1)。这些依赖自然形成了任务的 DAG；一个要计算的任务d(i,j)只有在它的所有前驱（以及它们的前驱等）都完成后才能执行。解决了所有依赖关系且不相互依赖（例如d(1,2)和d(2,1)）的任务可以并行处理。除了遵循依赖关系，不需要其他同步。

有几种方法可以在 TBB 中表达波前模式：使用低级任务（复杂且不推荐），使用parallel_do加原子计数器（如TBB 设计模式文档中所述；那里使用的示例与您所做的非常接近）并使用流程图（如TBB 博客中所述）。我建议您研究这些文档并进行自己的实验。

另请注意，计算单个的工作量d(i,j)太小，无法证明并行执行的开销是合理的。为了实现一些加速，将矩形计算块聚合到单个任务中，在任务中串行处理块元素。这些块将具有相同的依赖模式。但是，您制作的块越大，可用的并行度就越低，因此您可能需要尝试使用块大小来获得最佳性能。