使用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相同的值，而不需要互斥或其他同步技術。