c++ - 使用 OpenMP 循环时的线程安全

Question

我正在研究一个小的 Collatz conjecture calculator使用 C++ 和 GMP，我正在尝试使用 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 <iostream>
 #include <gmpxx.h>
 
 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.get_str(10);
         while (true) {
             if (mpz_cmp_ui(x.get_mpz_t(), 1)) break;
             x = collatz(x);
         }
         x++;
         //std::cout << " OK" << std::endl;
     }
 }

考虑到当我取消注释到屏幕的输出时我没有收到这个错误，它很慢，我认为手头的问题与线程安全有关，特别是与试图递增 x< 的并发线程有关 同时。

我的假设是否正确？我该如何解决这个问题并使其安全运行？

Answer 1

我假设您想要做的是检查 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 << x.get_str(10);
        check_collatz(x);
        x++;
    }
}

while (true) 循环不利于推理和并行化，所以让我们创建一个等效的 for 循环:

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

现在，我们可以讨论并行化代码。 OpenMP 并行化的基础是工作共享结构。您不能只在 while 循环中使用 #pragma omp parallel。幸运的是，您可以使用 #pragma omp parallel for 轻松标记某些规范的 for 循环。但是，为此，您不能将 mpz_class 用作循环变量，并且必须指定循环的结束:

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

请注意，check 是隐式私有(private)的，每个处理它的线程都有一个拷贝。此外，OpenMP 将负责在线程之间分配工作 [1 ... 2^63]。当线程调用 check_collat​​z 时，将为它创建一个新的私有(private) mpz_class 对象。

现在，您可能会注意到，在每次循环迭代中重复创建一个新的 mpz_class 对象的成本很高(内存分配)。您可以重用它(通过再次破坏 check_collat​​z)并创建一个线程私有(private)的 mpz_class 工作对象。为此，您将复合 parallel for 拆分为单独的 parallel 和 for 编译指示:

#include <gmpxx.h>
#include <iostream>
#include <limits>

// 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<long>::max(); check++)
        {
            // Note: The structure of this fits perfectly in a for loop.
            for (x = check; x != 1; collatz(x));
        }
    }
}

请注意，在并行区域中声明 x 将确保它是隐式私有(private)并正确初始化。您应该更喜欢在外部声明它并将其标记为 private。这通常会导致混淆，因为来自外部范围的显式 private 变量被初始化。

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

您担心每个线程都有额外的对象。这是良好性能的必要。你不能用锁/关键部分/原子有效地解决这个问题。您必须保护对唯一相关变量的每一次读取和写入。将没有平行性。

注意:巨大的 for 循环可能会导致负载不平衡。所以有些线程可能会比其他线程早几个世纪完成。您可以使用动态调度或更小的静态 block 来解决这个问题。

编辑:出于学术原因，这里有一个想法如何直接在 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<long>::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));
        }
    }