我将尝试使用 OpenMP 将以下简单的while循环并行化为两个线程(我第一次尝试使用此技术(。我尝试同时使用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 循环检测算法的一部分(。
我在这里省略了我所有的#pragma omp ...尝试，因为它们都导致了糟糕的性能。
编辑：
根据@templatetypedef的回答，我尝试了布伦特的算法。由于我需要在弗洛伊德的第二和第三个while循环上注入一些计算(构建预循环和循环值的数字数组，以及使用 Horner 方案计算多项式(，Brent 没有为我提供添加此代码的要点。因此，我更喜欢弗洛伊德。完整的代码可以在这里找到。
我认为这里的问题是您尝试并行化的代码不能很好地并行化。可以这样想：每个线程基本上需要执行十几次算术运算来推进其指针，但随后需要与另一个线程同步以确认值不相同，并且在两个线程完成之前无法进行任何部分进度。简单地锁定或解锁互斥锁的成本约为 17ns，这可能大约是评估其中一个或野兔步骤所需的时间。因此，每个线程最终可能完成的工作量可能与单个循环迭代几乎相同 - 甚至可能更多 - 所以我严重怀疑你会以这种方式获得加速。
现在，可能有效的方法是使用像布伦特的周期查找算法这样的算法，该算法比弗洛伊德算法的比较更少，并且通常收敛得更快。这很可能会让你更快地找到周期。