levenstein算法并行

Question

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

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

Levenstein距离计算本质上是一种波前模式，其中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)的工作量太小，无法证明并行执行的开销是合理的。为了实现一定的加速，将一个矩形计算块聚合到一个任务中，在任务中串行处理块元素。这些块将具有相同的依赖模式。但是，您制作的块越大，可用的并行性就越低，因此您可能需要尝试块大小以获得最佳性能。