使用OpenMP循环时的线程安全

我正在使用C ++和GMP开发小型Collat​​z猜想计算器，并且正在尝试使用OpenMP在其上实现并行性，但是遇到了有关线程安全性的问题。就目前而言，尝试运行代码将产生以下结果：

*** Error in `./collatz': double free or corruption (fasttop): 0x0000000001140c40 ***
*** Error in `./collatz': double free or corruption (fasttop): 0x00007f4d200008c0 ***
[1]    28163 abort (core dumped)  ./collatz

这是重现该行为的代码。

 #include 
 #include 

 mpz_class collatz(mpz_class n) {
     if (mpz_odd_p(n.get_mpz_t())) {
         n *= 3;
         n += 1;
     } else {
         n /= 2;
     }
     return n;
 }

 int main() {
     mpz_class x = 1;
 #pragma  omp parallel
     while (true) {
         //std::cout <

鉴于在取消注释输出到屏幕时的速度很慢时没有得到此错误，我认为当前的问题与线程安全有关，尤其是与试图同时增加的并发线程x有关。

我的假设正确吗？如何解决此问题并使其安全运行？


1> Zulan..：
我假设您要检查的是collat​​z猜想是否对所有数字都成立。您发布的程序在串行和并行的许多级别上都是错误的。

if (mpz_cmp_ui(x.get_mpz_t(), 1)) break;


意味着它将在时破裂x != 1。如果您使用正确的替换它0 == mpz_cmp_ui，那么代码将不断地2反复测试。无论如何，您都必须具有两个变量，一个用于表示要检查的内容的外部循环，另一个用于执行检查的内部循环。如果为此创建函数，则更容易实现此目的：

void check_collatz(mpz_class n) {
    while (n != 1) {
        n = collatz(n);
    }
}

int main() {
    mpz_class x = 1;
    while (true) {
        std::cout <

该while (true)循环很难推理和并行化，因此让我们做一个等效的for循环：

for (mpz_class x = 1;; x++) {
    check_collatz(x);
}


现在，我们可以讨论并行化代码。OpenMP并行化的基础是工作共享结构。您不能只打#pragma omp parallel一会儿循环。幸运的是，您可以轻松地将某些规范的for循环标记为#pragma omp parallel for。但是，为此，您不能将其mpz_class用作循环变量，而必须为循环指定结尾：

#pragma omp parallel for
for (long check = 1; check <= std::numeric_limits::max(); check++)
{
    check_collatz(check);
}


请注意，它check是隐式私有的，在其上工作的每个线程都有一个副本。OpenMP还将负责在线程之间分配工作[1 ... 2 ^ 63]。当线程调用check_collatz新的私有mpz_class对象时，将为其创建对象。

现在，您可能会注意到，mpz_class在每次循环迭代中重复创建一个新对象的成本很高（内存分配）。您可以重新使用它（通过check_collatz再次破坏）并创建一个线程专用的mpz_class工作对象。为此，您将化合物parallel for分为单独的parallel和for实用的：

#include 
#include 
#include 

// Avoid copying objects by taking and modifying a reference
void collatz(mpz_class& n)
{
    if (mpz_odd_p(n.get_mpz_t()))
    {
        n *= 3;
        n += 1;
    }
    else
    {
        n /= 2;
    }
}

int main()
{
#pragma omp parallel
    {
        mpz_class x;
#pragma omp for
        for (long check = 1; check <= std::numeric_limits::max(); check++)
        {
            // Note: The structure of this fits perfectly in a for loop.
            for (x = check; x != 1; collatz(x));
        }
    }
}


请注意，x在并行区域中进行声明将确保其隐式私有且已正确初始化。您应该更喜欢在外部声明它并对其进行标记private。这通常会导致混乱，因为private来自外部作用域的明确变量是单位化的。

您可能会抱怨这只检查了前2 ^ 63个数字。只是让它运行。这使您有足够的时间将OpenMP掌握到专家级别，并为GMP对象编写自己的自定义工作共享。

您担心每个线程都有多余的对象。这对于获得良好的性能至关重要。您无法使用锁/关键部分/原子来有效地解决此问题。您将必须保护对每个唯一相关变量的读取和写入。不会再有并行性了。

注意：巨大的for循环可能会导致负载不平衡。因此，某些线程可能比其他线程提前几个世纪完成。您可以通过动态调度或较小的静态块来解决此问题。

编辑：出于学术考虑，这是一个如何直接在GMP对象上实现工作共享的想法：

#pragma omp parallel
    {
        // Note this is not a "parallel" loop
        // these are just separate loops on distinct strided 
        int nthreads = omp_num_threads();
        mpz_class check = 1;
        // we already checked those in the other program
        check += std::numeric_limits::max(); 
        check += omp_get_thread_num();
        mpz_class x;
        for (; ; check += nthreads)
        {
            // Note: The structure of this fits perfectly in a for loop.
            for (x = check; x != 1; collatz(x));
        }
    }