用两条语句并行化 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 循环本身可以有很多迭代（它是 [= 的一部分24=]).

我在这里省略了所有 #pragma omp ... 尝试，因为所有这些尝试都导致了糟糕的表现。

编辑：

基于@templatetypedef的回答，我尝试了布伦特算法。因为我需要在 Floyd 的 第二和第三个 while 循环 上注入一些计算（构建一个数字数组预循环和循环值，以及使用 Horner 方案计算多项式） Brent 没有给我添加此代码的要点。因此我更喜欢 Floyd。完整代码可见here.

Answer 1

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

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

用两条语句并行化 while 循环（Floyd 循环检测算法）

Parallelizing while loop with two statements (Floyd cycle detection algorithm)

c++

algorithm

performance

multithreading

openmp

编辑：