使用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

我假设你想要做的是检查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轻松标记某些规范的循环。对于这一点，但是，你不能使用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编译指示：

#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对象编写自己的定制工作共享。

您担心每个线程都有额外的对象。这是基本良好的性能。你无法用锁/关键部分/原子来有效地解决这个问题。你必须保护每一个读写到你唯一的相关变量。没有平行性。

注意：巨大的循环可能会有负载不平衡。所以有些线程可能会比其他线程早几个世纪才能完成。你可以通过动态调度或者更小的静态块来解决这个问题。

编辑：对于学术的缘故，这里是一个知道如何直接实现在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)); 
     } 
    } 

Answer 2

你很可能是正确的与x碰撞。您可以通过标记x私人：

#pragma omp parallel private(x) 

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

Answer 3

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

#pragma omp atomic 
x++; 

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