在同一線程上運行的所有OpenMP任務

Question

我已經使用OpenMP中的任務編寫了遞歸併行函數。雖然它給了我正確的答案，並且運行良好，但我認爲這存在並行性問題。與串行解決方案相比，運行時無法在沒有任務解決的其他並行問題中進行擴展。當打印每一個線程，他們都上線運行的任務0我上編譯和Visual Studio速成運行2013年

int parallelOMP(int n) 
{ 

    int a, b, sum = 0; 
    int alpha = 0, beta = 0; 

    for (int k = 1; k < n; k++) 
    { 

     a = n - (k*(3 * k - 1)/2); 
     b = n - (k*(3 * k + 1)/2); 


     if (a < 0 && b < 0) 
      break; 


     if (a < 0) 
      alpha = 0; 

     else if (p[a] != -1) 
      alpha = p[a]; 

     if (b < 0) 
      beta = 0; 

     else if (p[b] != -1) 
      beta = p[b]; 


     if (a > 0 && b > 0 && p[a] == -1 && p[b] == -1) 
     { 
      #pragma omp parallel 
      { 
       #pragma omp single 
       { 
        #pragma omp task shared(p), untied 
        { 
         cout << omp_get_thread_num(); 
         p[a] = parallelOMP(a); 
        } 
        #pragma omp task shared(p), untied 
        { 
         cout << omp_get_thread_num(); 
         p[b] = parallelOMP(b); 
        } 
        #pragma omp taskwait 
       } 
      } 

      alpha = p[a]; 
      beta = p[b]; 
     } 

     else if (a > 0 && p[a] == -1) 
     { 
      #pragma omp parallel 
      { 
       #pragma omp single 
       { 
        #pragma omp task shared(p), untied 
        { 
         cout << omp_get_thread_num(); 
         p[a] = parallelOMP(a); 
        } 

        #pragma omp taskwait 
       } 
      } 

      alpha = p[a]; 
     } 

     else if (b > 0 && p[b] == -1) 
     { 
      #pragma omp parallel 
      { 
       #pragma omp single 
       { 
        #pragma omp task shared(p), untied 
        { 
         cout << omp_get_thread_num(); 
         p[b] = parallelOMP(b); 
        } 

        #pragma omp taskwait 
       } 
      } 

      beta = p[b]; 
     } 


     if (k % 2 == 0) 
      sum += -1 * (alpha + beta); 
     else 
      sum += alpha + beta; 


    } 

    if (sum > 0) 
     return sum%m; 
    else 
     return (m + (sum % m)) % m; 
} 

Answer 1

實際的問題：

您使用Visual Studio 2013年

Visual Studio從未支持超過2.0的OMP版本（請參閱here）。

OMP任務是OMP 3.0的一項功能（請參閱spec）。

Ergo，使用VS完全不需要OMP任務。

如果OMP任務是基本要求，請使用其他編譯器。如果OMP不是基本要求，則應考慮使用另一個並行任務處理庫。 Visual Studio包含MS Concurrency Runtime，以及構建於其上的Parallel Patterns Library。由於我使用VS工作，我最近從OMP轉移到PPL;它不是一個簡單的替代品，但它非常有能力。

---

我在解決第二次嘗試，再次保存歷史原因：

那麼，問題是幾乎可以肯定的是你定義你的omp task個omp parallel區域之外。

這裏是一個人爲的例子：

void work() 
{ 
    #pragma omp parallel 
    { 
     #pragma omp single nowait 
     for (int i = 0; i < 5; i++) 
     { 
      #pragma omp task untied 
      { 
       std::cout << 
        "starting task " << i << 
        " on thread " << omp_get_thread_num() << "\n"; 

       sleep(1); 
      } 
     } 
    } 
} 

如果省略parallel聲明，作業連續運行：

starting task 0 on thread 0 
starting task 1 on thread 0 
starting task 2 on thread 0 
starting task 3 on thread 0 
starting task 4 on thread 0 

但是，如果你把它留在：

starting task starting task 3 on thread 1 
starting task 0 on thread 3 
2 on thread 0 
starting task 1 on thread 2 
starting task 4 on thread 2 

成功，完全可靠地濫用共享輸出資源。 （作爲參考，如果你省略了single聲明，每個線程將運行循環，導致20個任務在我的4個CPU虛擬機上運行）。

---

原來的答覆如下出於完整性考慮，但不再相關的！

在任何情況下，您的omp task是一件簡單的事情。它可能運行並立即完成：因爲你永遠不會開始一個長期運行的發射了下一個任務之前的任務，一切都將可能是第一個分配的線程上運行

#pragma omp task shared(p), untied 
cout << omp_get_thread_num(); 

#pragma omp task shared(p), untied 
cout << omp_get_thread_num(); 

#pragma omp task shared(p), untied 
cout << omp_get_thread_num(); 

#pragma omp task shared(p), untied 
cout << omp_get_thread_num(); 

。

也許你打算做這樣的事情？

if (a > 0 && b > 0 && p[a] == -1 && p[b] == -1) 
{ 
    #pragma omp task shared(p), untied 
    { 
     cout << omp_get_thread_num(); 
     p[a] = parallelOMP(a); 
    } 

    #pragma omp task shared(p), untied 
    { 
     cout << omp_get_thread_num(); 
     p[b] = parallelOMP(b); 
    } 

    #pragma omp taskwait 

    alpha = p[a]; 
    beta = p[b]; 
} 

Answer 2

有時候，我希望在SO評論可能被豐富的格式化爲答案，但可惜事實並非如此。因此，這裏出現了一個假裝作爲答案的長評論。

看來在編寫遞歸OpenMP代碼時出現的一個非常常見的錯誤並不瞭解平行區域的工作方式。考慮下面的代碼（使用明確的任務，因此需要支持OpenMP 3.0或更高版本）：

void par_rec_func (int arg) 
{ 
    if (arg <= 0) return; 

    #pragma omp parallel num_threads(2) 
    { 
     #pragma omp task 
     par_rec_func(arg-1); 

     #pragma omp task 
     par_rec_func(arg-1); 
    } 
} 

// somewhere in the main function 
par_rec_func(10); 

這個代碼有問題。問題是，除了頂級調用par_rec_func()之外，在所有其他調用中，並行區域將在封閉外部並行區域的上下文中創建。這稱爲嵌套並行，默認情況下，已禁用，這意味着頂層下面的所有並行區域都將處於非活動狀態，即它們將連續執行。由於任務綁定到最裏面的並行區域，所以它們也會被串行執行。這個代碼會發生什麼，它會在par_rec_func()的頂層調用中產生一個額外的線程（總共兩個線程），然後每個線程將執行遞歸樹的整個分支（即整個樹的一半）。如果在具有64個內核的機器上運行該代碼，則其中62個將閒置。爲了使嵌套並行啓用，人們要麼設置環境變量OMP_NESTED到true或致電omp_set_nested()，並將它傳遞一個真正的標誌：

omp_set_nested(1); 

一旦嵌套並行操作已被啓用，一個面臨着一個新的問題。每遇到一個嵌套的並行區域，相遇的線程就會產生一個額外的線程（因爲num_threads(2)）或從運行時的線程池中獲取一個空閒線程。在遞歸的每一個更深層次上，這個程序將需要兩倍於上一級的線程數量。儘管可以通過OMP_THREAD_LIMIT（另一個OpenMP 3.0功能）設置線程總數的上限，並將開銷放在一邊，但在這種情況下，這不是真正想要的。

在這種情況下的正確的解決方案是在一個單一的並行區域的動態範圍，以使用孤立的任務：

void par_rec_func (int arg) 
{ 
    if (arg <= 0) return; 

    #pragma omp task 
    par_rec_func(arg-1); 

    #pragma omp task 
    par_rec_func(arg-1); 

    // Wait for the child tasks to complete if necessary 
    #pragma omp taskwait 
} 

// somewhere in the main function 
#pragma omp parallel 
{ 
    #pragma omp single 
    par_rec_func(10); 
} 

這種方法的優點是很多的。首先，只用一個指定的線程創建一個並行區域（例如，通過設置OMP_NUM_THREADS或通過任何其他方式）。當子任務以遞歸方式調用par_rec_func()時，只需將新任務添加到並行區域而不產生新線程。這在遞歸樹不平衡的情況下有很大的幫助，因爲許多質量OpenMP運行時間實現任務竊取，例如，線程i可以執行在線程j中執行的任務的子任務，其中i != j。

給定一個的OpenMP 2.0的編譯器等VC++，一個不能做很多除了通過使用嵌套並行，並明確地在一定水平禁用它近似於在上述想法：

void par_rec_func (int arg) 
{ 
    if (arg <= 0) return; 

    int level = omp_get_level(); 

    #pragma omp parallel sections num_threads(2) if(level < 4) 
    { 
     #pragma omp section 
     par_rec_func(arg-1); 

     #pragma omp section 
     par_rec_func(arg-1); 
    } 
} 

// somewhere in the main function 
int saved_nested = omp_get_nested(); 
omp_set_nested(1); 

par_rec_func(10); 

omp_set_nested(saved_nested); 

omp_get_level()用於確定的電平嵌套和if子句用於選擇性地停用第四層或更深層嵌套處的並行區域。這個解決方案是愚蠢的，並且在遞歸樹不平衡時不能很好地工作。