OpenMP - 二叉樹

Question

我試圖運行一個簡單的程序並行運行。我想將它基於二叉樹。根據我想要將工作分配給所有處理器的處理器數量，以便程序並行運行。使用遞歸，我正在檢查是否還有1個或2個處理器，如果有，我使用OpenMP sections來運行它。但是，它使用的內核越多，算法越慢，我不明白爲什麼。我試圖儘可能自我解釋地編寫代碼。

void fun1(int tab[], int pocz, int kon, int threadsLeft) 
{ 
    if (threadsLeft == 2) 
    { 
     #pragma omp parallel num_threads(2) 
     { 
      #pragma omp sections nowait 
      { 
       #pragma omp section 
       { 
        for (int i = pocz; i < kon/2; i++) 
        { 
         tab[i] = 1; 
        } 

       } 
       #pragma omp section 
       { 
        for(int i = kon/2 + 1; i < kon; i++) 
        { 
         tab[i] = 0; 
        } 
       } 
      } 
     } 
    } 
    else if (threadsLeft == 1) 
    { 
     #pragma omp parallel num_threads(1) 
     { 
      #pragma omp sections nowait 
      { 
       #pragma omp section 
       { 
        for (int i = pocz; i < kon; i++) 
        { 
         tab[i] = 2; 
        } 
       } 
      } 
     } 
    } 
    else 
    { 
     fun1(tab, pocz, kon/2, threadsLeft/2); 
     fun1(tab, kon - kon/2, kon, threadsLeft - threadsLeft/2); 
    } 
} 

int main() 
{ 
    int allThreads = omp_get_num_threads(); 
    int N = 200000000; 
    int* tab = new int[N]; 
    for (int i = 0; i < N; i++) 
    { 
     tab[i] = 0; 
    } 
    fun1(tab, 0, N, allThreads); 
} 

Answer 1

正如我所看到的那樣，您有兩個問題。

第一個問題是，在主函數中，在並行區域之外，omp_get_num_threads()應該總是返回1.因此，在並行區域內調用它以訪問當前並行區域的多少個線程。

第二個問題是你有一個遞歸問題，這個問題適合於任務並行。 OpenMP sections最好與常數先驗已知數量的部分一起使用。 OpenMP tasks旨在處理遞歸問題，其中任務的數量不一定是已知的。例如，請查看basic tutorial。請注意，您的編譯器必須支持OpenMP 3.0才能正常工作。

把這些都在一起，你的新#pragma omp tasks代碼應該看起來像如下：

void fun1(int tab[], int pocz, int kon, int threadsLeft) 
{ 
    if (threadsLeft <= 1) { 
     for (int i = pocz; i < kon; i++) 
      tab[i] = 2; // should make this constant something else to be more helpful 
    } 
    else 
    { 
     #pragma omp task 
     fun1(tab, pocz, kon/2, threadsLeft/2); 
     #pragma omp task 
     fun1(tab, kon - kon/2, kon, threadsLeft - threadsLeft/2); 
     #pragma omp taskwait 
    } 
} 

int main() 
{ 

    int N = 200000000; 
    int* tab = new int[N]; 
    for (int i = 0; i < N; i++) 
     tab[i] = 0; 

    #pragma omp parallel 
    // Only the first thread will spawn other threads 
    #pragma omp single nowait 
    { 
     int allThreads = omp_get_num_threads(); 
     fun1(tab, 0, N, allThreads); 
    } 

} 

公平的警告：我還沒有測試此代碼自己，所以把它當作一粒鹽。