我的完整代碼中有一段代碼：
const unsigned int GL=8000000;
const int cuba=8;
const int cubn=cuba cuba;
const int cub3=cubn*cubn*cubn;
int Length[cub3];
int Begin[cub3];
int Counter[cub3];
int MIndex[GL];
struct Particle{
int ix,jy,kz;
int ip;
};
Particle particles[GL];
int GetIndex(const Particle & p){return (p.ix cuba cubn*(p.jy cuba cubn*(p.kz cuba)));}
...
#pragma omp parallel for
for(int i=0; i<cub3; i) Length[i]=Counter[i]=0;
#pragma omp parallel for
for(int i=0; i<N; i)
{
int ic=GetIndex(particles[i]);
#pragma omp atomic update
Length[ic] ;
}
Begin[0]=0;
#pragma omp single
for(int i=1; i<cub3; i) Begin[i]=Begin[i-1] Length[i-1];
#pragma omp parallel for
for(int i=0; i<N; i)
{
if(particles[i].ip==3)
{
int ic=GetIndex(particles[i]);
if(ic>cub3 || ic<0) printf("ic=%d out of range!\n",ic);
int cnt=0;
#pragma omp atomic capture
cnt=Counter[ic] ;
MIndex[Begin[ic] cnt]=i;
}
}
如果要洗掉
#pragma omp parallel for
代碼正常作業，輸出結果始終相同。但是有了這個編譯指示，代碼中有一些未定義的行為/競爭條件，因為每次它都會給出不同的輸出結果。如何解決這個問題？
更新：任務如下。有很多帶有一些隨機坐標的粒子。需要將粒子在陣列中的索引輸出到陣列MIndex ，這些索引在坐標系的每個單元格（笛卡爾立方體，例如1×1×1 cm）中。因此，在MIndex的開頭應該有坐標系第一個單元格中粒子的陣列粒子中的索引，然后是 - 在第二個單元中，然后是 - 在第三個，依此類推。區域MIndex中給定單元內的索引順序并不重要，可以是任意的。如果可能的話，需要使這個并行，可能是使用原子操作。
有一條直接的方法：并行遍歷所有坐標單元，并在每個單元中檢查所有粒子的坐標。但是對于大量的細胞和粒子，這似乎很慢。有更快的方法嗎？是否有可能只在粒子陣列中并行移動一次并使用原子操作填充MIndex陣列，就像上面代碼中寫的那樣？
uj5u.com熱心網友回復：
如果您想要一種可以有效作業的演算法（不需要在共享計數器上使用原子 RMW，這將是一場災難，請參見下文），您可能無法讓編譯器為您自動并行化標量代碼。但是您也許可以使用 OpenMP 作為啟動執行緒和獲取執行緒 ID 的一種方式。
保留初始直方圖中的每個執行緒計數陣列，在第二遍中使用
（更新：這可能行不通：我之前沒有注意到if(particles[i].ip==3)源Count[ic]中Length[ic]的指出，也許您首先在計算 Length 時想要進行檢查，那么就可以了。）
手動多執行緒處理第一個直方圖（進入Length[]），每個執行緒處理已知范圍的i值。保持這些每個執行緒的長度，即使你對它們求和并加上前綴求和來構建 Begin[]。
Length[thread][ic]該立方體中的粒子數也是如此，超出了該執行緒處理的值i范圍。（并且將在第二個回圈中再次回圈：關鍵是我們以相同的方式在執行緒之間劃分粒子兩次。理想情況下，相同的執行緒在相同的范圍內作業，因此 L1d 快取中的東西可能仍然很熱。）
將其預處理到每個執行緒Begin[][]陣列中，因此每個執行緒都知道 MIndex 中的何處放置來自每個存盤桶的資料。
// pseudo-code, fairly close to actual C
for(ic < cub3) {
// perhaps do this "vertical" sum into a temporary array
// or prefix-sum within Length before combining across threads?
int pos = sum(Length[0..nthreads-1][ic-1]) Begin[0][ic-1];
Begin[0][ic] = pos;
for (int t = 1 ; t<nthreads ; t ) {
pos = Length[t][ic]; // prefix-sum across threads for this cube bucket
Begin[t][ic] = pos;
}
}
這有一個非常糟糕的快取訪問模式，尤其是cuba=8在彼此相距 4096 位元組的Length[t][0]情況下。Length[t 1][0]（因此 4k 別名是一個可能的問題，快取沖突未命中也是如此）。
也許每個執行緒都可以將其自己的長度切片加到 Begin 切片中，1. 用于快取訪問模式（以及位置，因為它剛剛撰寫了這些長度），以及 2. 為該作業獲得一些并行性。
然后在最后一個回圈中MIndex，每個執行緒都可以int pos = --Length[t][ic]從 Length 中匯出一個唯一的 ID。（就像您對 所做的那樣Count[]，但沒有將另一個每個執行緒陣列引入零。）
Length 的每個元素都將回傳零，因為同一個執行緒正在查看它剛剛計算的相同點。使用正確計算的Begin[t][ic]位置，MIndex[...] = i商店不會發生沖突。 錯誤共享仍然是可能的，但它是一個足夠大的陣列，點往往會分散在周圍。
不要過度使用執行緒數，尤其cuba是大于 8 時。長度/開始預處理作業的數量與執行緒數成比例，因此最好只為不相關的執行緒或任務留出一些 CPU完成一些吞吐量。OTOH，cuba=8這意味著每個執行緒陣列只有 4096 位元組（太小而無法并行化歸零，順便說一句），實際上并沒有那么多。
（您的編輯之前的上一個答案更清楚地說明了發生了什么。）
這基本上是直方圖嗎？如果每個執行緒都有自己的計數陣列，您可以在最后將它們相加（您可能需要手動執行此操作，而不是讓 OpenMP 為您執行此操作）。但似乎您還需要這個計數在每個體素中是唯一的，才能正確更新 MIndex？如果可能的話，這可能是一個阻礙，比如需要調整每個 MIndex 條目。
更新后，您正在對 Length[] 進行直方圖，以便可以加快該部分的速度。
Atomic RMWs 對你的代碼來說是必要的，性能災難
共享計數器的原子增量會更慢，并且在 x86 上可能會嚴重破壞記憶體級并行性。在 x86 上，每個原子 RMW 也是一個完整的記憶體屏障，在它發生之前耗盡存盤緩沖區，并阻止以后的加載開始直到它發生之后。
與使用非原子訪問可能對多個 和未完成的元素Counter有快取未命中的單個執行緒相反。（由于無序執行，下一次迭代的 load / inc / store for可以在存在未完成的快取未命中和/或存盤時進行加載。）BeginMIndexCounter[ic] Begin[ic]Mindex[]
允許寬松原子增量的 ISA 可能能夠有效地做到這一點，例如 AArch64。（同樣，OpenMP 可能無法為您做到這一點。）
即使在 x86 上，如果有足夠的（邏輯）內核，您仍然可能會獲得一些加速，特別是如果Counter訪問足夠分散，它們的內核不會經常爭奪相同的快取行。但是，您仍然會在內核之間反彈很多快取行，而不是在 L1d 或 L2 中保持熱狀態。（虛假分享是個問題，
也許軟體預取可以提供幫助，例如prefetchw（寫入預取）計數器進行 5 或 10i次迭代。
但是，即使有memory_order_seq_cst增量，哪個點按哪個順序進行也不是確定性的。無論哪個執行緒首先遞增，都是與Counter[ic]that 相關聯的執行緒。cnti
替代訪問模式
也許讓每個執行緒掃描所有點，但只處理其中的一個子集，子集不相交。 因此Counter[]，任何給定執行緒接觸的元素集僅由該執行緒接觸，因此增量可以是非原子的。
按范圍過濾p.kz可能最有意義，因為這是索引中最大的乘數，因此每個執行緒“擁有”一個連續的Counter[].
但是，如果你的分數不是均勻分布的，你就需要知道如何將事情分解成大致均分的作業。而且你不能只是更精細地劃分它（如 OMP 調度動態），因為每個執行緒都將掃描所有點：這將增加過濾作業量。
也許幾個固定的磁區是一個很好的折衷方案，可以在不引入大量額外作業的情況下獲得一些并行性。
回復：您的編輯
您已經遍歷了整個點陣列Length[ic] ;嗎？用 再次做同樣的直方圖作業似乎是多余的Counter[ic] ;，但如何避免它并不明顯。
計數陣列很小，但如果您完成后不需要兩者，您可能只需減少 Length 以將唯一索引分配給體素中的每個點。至少第一個直方圖可以受益于每個執行緒的不同計數陣列的并行化，并在最后垂直添加。由于計數陣列對于 L1d 快取來說足夠小，因此應該與執行緒完美擴展。
順便說一句，for() Length[i]=Counter[i]=0;太小了，不值得并行化。對于cuba=8，它8*8*16 * sizeof(int)= 4096 位元組，只有一頁，所以它只是兩個小的 memset。
（當然，如果每個執行緒都有自己獨立的 Length 陣列，則每個執行緒都需要將其歸零）。如果一長串點都在同一個存盤桶中，這甚至可以考慮使用每個執行緒可能 2 個計數陣列展開以隱藏存盤/重新加載串行依賴項，這已經足夠小了。最后組合計數陣列是一項作業，#pragma omp simd或者只是正常的自動矢量化，gcc -O3 -march=native因為它是整數作業。
對于最后一個回圈，您可以將點陣列分成兩半（將一半分配給每個執行緒），并讓一個執行緒通過從 倒數獲得唯一 ID --Length[i]，另一個從 0 開始計數Counter[i] 。使用不同的執行緒查看不同的點，這可以為您提供 2 倍的加速。（MIndex 存盤的模爭用。）
要做的不僅僅是向上和向下計數，您需要僅從整個 Length 陣列中獲得的資訊......但您確實暫時擁有這些資訊。請參閱頂部的部分
uj5u.com熱心網友回復：
使更新Counter[ic] 原子化是正確的，但是下一行還有一個額外的問題：MIndex[Begin[ic] cnt]=i;不同的迭代可以在這里寫入相同的位置，除非你有數學證明從MIndex. 所以你也必須使那條線原子化。然后你的回圈中幾乎沒有并行作業，所以如果可能會很糟糕，你的速度就會加快。
然而，編輯第二行不是原子操作的正確形式，所以你必須 make it critical。這將使性能變得更糟。
此外，@Laci 是正確的，因為這是一個覆寫陳述句，并行調度的順序會影響結果。所以要么接受這個事實，要么接受這不能并行化。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/491162.html
上一篇：當一個任務正在寫入變數而其他任務讀取該變數時，我們是否需要信號量？
下一篇：多執行緒中基于函式輸入的鎖定