使用 OpenMP 循环时的线程安全

Question

我正在使用 C++ 和 GMP 开发一个小型 Collatz conjecture calculator，并且我正在尝试使用 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

关于与 x 的碰撞，您可能是对的。您可以通过以下方式将 x 标记为私有：

#pragma omp parallel private(x)

这样每个线程都有自己的 "version" 变量 x，这应该使这个线程安全。默认情况下，在 #pragma omp parallel 之前声明的变量是 public，因此所有线程之间有一个共享实例。

Answer 2

您可能只想使用原子指令触摸 x。

#pragma omp atomic
x++;

这确保所有线程都看到相同的 x 值，而不需要互斥锁或其他同步技术。

Answer 3

我假设你想做的是检查 collatz 猜想是否对所有数字都成立。您发布的程序在串行和并行的许多层面上都是错误的。

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 是隐式私有的，每个线程都有一个副本。此外，OpenMP 将负责在线程之间分配工作 [1 ... 2^63]。当线程调用 check_collatz 时，将为它创建一个新的私有 mpz_class 对象。

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

#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 来自外部范围的变量被单元化。

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

您担心每个线程都有额外的对象。这是获得良好性能所必需的。您无法使用 locks/critical sections/atomics 有效地解决此问题。您必须保护每个 读取和写入 到您唯一相关的变量。将没有并行性。

注意：巨大的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<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));
        }
    }

使用 OpenMP 循环时的线程安全

Thread safety while looping with OpenMP

c++

multithreading

openmp

gmp