如何在whilemp和while循環中並行化openmp？

Question

我想學習使用OpenMP並行編程和我感興趣的幾個while循環裏面並行以下do while循環：

do { 
     while(left < (length - 1) && data[left] <= pivot) left++; 
     while(right > 0 && data[right] >= pivot) right--; 

     /* swap elements */ 
     if(left < right){ 
      temp = data[left]; 
      data[left] = data[right]; 
      data[right] = temp; 
     } 

    } while(left < right); 

我沒有真正想通了如何並行while和do while循環，找不到任何資源，在那裏它專門描述瞭如何並行化while和do while循環。我發現了for循環的說明，但我無法對此做出任何假設，因爲while和do while循環。那麼，請你描述一下我可以如何平行化我在這裏提供的這個循環？

EDIT

我已經改變了do while循環至下面的代碼，在使用僅for迴路。

for(i = 1; i<length-1; i++) 
{ 
    if(data[left] > pivot) 
    { 
     i = length; 
    } 
    else 
    { 
     left = i; 
    } 

} 

for(j=length-1; j > 0; j--) 
{ 
    if(data[right] < pivot) 
    { 
     j = 0; 
    } 
    else 
    { 
     right = j; 
    } 
} 

/* swap elements */ 
if(left < right) 
{ 
    temp = data[left]; 
    data[left] = data[right]; 
    data[right] = temp; 
} 

int leftCopy = left; 
int rightCopy = right; 

for(int leftCopy = left; leftCopy<right;leftCopy++) 
{ 
    for(int new_i = left; new_i<length-1; new_i++) 
    { 
     if(data[left] > pivot) 
     { 
      new_i = length; 
     } 
     else 
     { 
      left = new_i; 
     } 
    } 

    for(int new_j=right; new_j > 0; new_j--) 
    { 
     if(data[right] < pivot) 
     { 
      new_j = 0; 
     } 
     else 
     { 
      right = new_j; 
     } 
    } 
    leftCopy = left; 
    /* swap elements */ 
    if(left < right) 
    { 
     temp = data[left]; 
     data[left] = data[right]; 
     data[right] = temp; 
    } 
} 

此代碼工作正常，併產生正確的結果，但是當我試圖通過改變前兩個for環路以下並行的上述代碼的部分：

#pragma omp parallel default(none) firstprivate(left) private(i,tid) shared(length, pivot, data) 
    { 
#pragma omp for 
     for(i = 1; i<length-1; i++) 
     { 
      if(data[left] > pivot) 
      { 
       i = length; 
      } 
      else 
      { 
       left = i; 
      } 
     } 
    } 


#pragma omp parallel default(none) firstprivate(right) private(j) shared(length, pivot, data) 
    { 
#pragma omp for 
     for(j=length-1; j > 0; j--) 
     { 
      if(data[right] < pivot) 
      { 
       j = 0; 
      } 
      else 
      { 
       right = j; 
      } 
     } 
    } 

的速度是比非並行代碼更糟糕。請幫助我確定我的問題。

謝謝

Answer 1

首先，排序算法很難與OpenMP並行循環並行化。這是因爲循環跳閘計數不是確定性的，而是取決於每次迭代讀取的輸入設置值。

我不認爲像data[left] <= pivot這樣的循環條件會運行良好，因爲OpenMP庫不知道如何在線程間分割迭代空間。如果你仍然對平行排序算法感興趣，我建議你先閱讀文獻，看看那些由於它們的可伸縮性而真正值得實施的算法。如果你只是想學習OpenMP，我建議你從更簡單的算法開始，比如bucket-sort，其中桶的數量是衆所周知的，並且不經常改變。

關於您嘗試並行化的示例，while循環並不直接受OpenMP支持，因爲循環次數（循環行程計數）不是確定性的（否則很容易將它們轉換爲for循環）。因此，不可能在線程之間分配迭代。另外，While循環使用最後一次迭代的結果來檢查一個條件是很常見的。這稱爲後寫後讀或真相關並且不能並行化。

如果您嘗試將omp parallel子句的數目減至最少，您的減速問題可能會得到緩解。另外，嘗試將它們移出所有循環。這些子句可能會創建並加入在代碼的並行部分中使用的其他線程，這些代價非常昂貴。

您仍然可以同步並行塊內的線程，以便結果類似。實際上，默認情況下，所有線程在omp for子句末尾彼此等待，這樣可以使事情變得更加簡單。

#pragma omp parallel default(none) firstprivate(right,left) private(i,j) shared(length, pivot, data) 
{ 
    #pragma omp for 
    for(i = 1; i<length-1; i++) 
    { 
     if(data[left] > pivot) 
     { 
      i = length; 
     } 
     else 
     { 
      left = i; 
     } 
    } 

    #pragma omp for 
    for(j=length-1; j > 0; j--) 
    { 
     if(data[right] < pivot) 
     { 
      j = 0; 
     } 
     else 
     { 
      right = j; 
     } 
    } 
} // end omp parallel