如何使用OpenMP並行化數組移位？

我tryed的幾件事情，但沒有得到下面的示例中的任何準確的結果（其旋轉Carteira對象的數組中的元素，對於置換算法）：

void rotaciona(int i) 
{ 
    Carteira aux = this->carteira[i]; 
    for(int c = i; c < this->size - 1; c++) 
    { 
     this->carteira[c] = this->carteira[c+1]; 
    } 
    this->carteira[this->size-1] = aux; 
}

謝謝非常！

來源

2011-05-17 Leonardo Pessoa

我有類似的問題，任何人都可以幫忙嗎？！ – 2011-05-17 12:20:42

這是loop-carried dependencies一個循環的示例，並且因此不能被容易地作爲並行寫入，因爲任務（循環的每次迭代）不是獨立的。打破依賴可以從一個微不足道的修改到完全不可能的（例如迭代循環）。

在這裏，情況是介於兩者之間。並行執行此操作的問題在於，您需要在您的鄰居改變該值之前找出最右邊的值。構造的OMP不會向您公開哪些循環迭代值是「您的」，因此我不認爲您可以使用OpenMP作爲工作共享構造來分解循環。但是，你可以自己做;但是它需要更多的代碼，並且它不會很好地減少到系列案例。

但是，如何做到這一點的例子如下所示。你必須自己打破環路，然後獲得最正確的價值。 OpenMP屏障確保沒有人開始修改值，直到所有線程緩存了其最新的最右邊值。

#include <stdio.h> 
#include <stdlib.h> 
#include <omp.h> 

int main(int argc, char **argv) { 
    int i; 
    char *array; 
    const int n=27; 

    array = malloc(n * sizeof(char)); 
    for (i=0; i<n-1; i++) 
     array[i] = 'A'+i; 

    array[n-1] = '\0'; 

    printf("Array pre-shift = <%s>\n",array); 

    #pragma omp parallel default(none) shared(array) private(i) 
    { 
     int nthreads = omp_get_num_threads(); 
     int tid = omp_get_thread_num(); 

     int blocksize = (n-2)/nthreads; 
     int start = tid*blocksize; 
     int end = start + blocksize - 1; 
     if (tid == nthreads-1) end = n-2; 

     /* we are responsible for values start...end */ 

     char rightval = array[end+1]; 
     #pragma omp barrier 

     for (i=start; i<end; i++) 
      array[i] = array[i+1]; 

     array[end] = rightval; 
    } 
    printf("Array post-shift = <%s>\n",array); 

    return 0; 
}

來源

2011-05-17 21:09:41

+1本質上我的答案，但措辭更好_and_與代碼示例。乾杯！ – sehe 2011-05-17 23:34:13

雖然你的樣品不顯示任何顯式OpenMP編譯的，我不認爲它可以輕鬆地工作：

你正在做就地操作與重疊區域。如果將塊分割爲塊，則邊界處將出現競爭條件（因爲el [n]從el [n + 1]複製而來，而el [n + 1]可能已經在另一個線程中更新過）。我建議你做手動分塊（可以完成），但是我懷疑openmp parallel並沒有足夠的靈活性（還沒有嘗試過），所以你可能只有一個平行區域來完成大塊的工作和修正內容的邊界元素並行塊的線程屏障/結束後

其他的想法：

如果你的價值觀是POD，你可以使用的memmove，而不是
如果可以的話，只需切換到列表

。

std::list<Carteira> items(3000); 

// rotation is now simply: 
items.push_back(items.front()); 
items.erase(items.begin());

來源

2011-05-17 12:24:37 sehe

+1對於memmove尤其如此 - 如果它有效，它可能比任何對內存的並行訪問都快。 – 2011-05-18 02:40:23

如何使用OpenMP並行化數組移位？

回答

相關問題