c++ - 用两条语句并行化 while 循环(Floyd 循环检测算法)

Question

我将尝试并行化以下简单 while 使用OpenMP 循环到两个线程中(我第一次尝试使用这项技术行走)。我尝试同时使用 sections 和 tasks。尽管我将它分成两个线程并产生了正确的结果，但性能慢得令人无法接受。

while ( tortoise != hare ) {
    tortoise = f ( tortoise );
    hare = f ( f ( hare ) );
}

注意 f 是函数对象的const &(即它有一个T operator()(const T &r))

operator()实现如下(d是函数对象的成员变量):

T operator() ( const T &r ) const {
    return ( ( r % d ) * 10 );
}

我的第一个想法是创建线程的开销。所以我在封闭函数的最开始创建了 team(它本身只被调用一次，而上面的 while 循环本身可以有很多迭代(它是 Floyd cycle detection algorithm 的一部分)。

我在这里省略了我所有的 #pragma omp ... 尝试，因为所有这些尝试都会导致性能不佳。

编辑:

根据 @templatetypedef 的回答，我尝试了 Brent 算法。因为我需要在 Floyd 的 第二个和第三个 while 循环 上注入(inject)一些计算(构建预循环的数字数组和循环值，以及使用 Horner 方案计算多项式) Brent 让我无法添加此代码。因此我更喜欢Floyd。完整代码可见here .

Answer 1

我认为这里的问题是您尝试并行化的代码并没有很好地并行化。这样想:每个线程基本上需要做十几个算术运算来推进其指针，但随后需要与另一个线程同步以确认值不相同并且不能取得任何部分进展直到两个线程都完成。简单锁定或解锁互斥量的成本是 about 17ns ，这可能是评估其中一个乌龟或兔子步骤需要多长时间。因此，每个线程最终可能完成与单个循环迭代几乎相同的工作量 - 可能更多 - 所以我严重怀疑您是否会通过这种方式获得加速。

现在，可能可行的方法是使用像 Brent 的循环查找算法这样的算法，它比 Floyd 的算法进行更少的比较，并且通常收敛得更快。这很可能会让您更快地找到周期。