C++ OpenMP 多CPU同時處理可能的問題

[sorryChen (陳揚和)]

我有一個很大的array大概是 3G 個數(其實是Human Genome)
我想要用多個CPU同時bucket這些數到 64 million個 bucket
一個簡單的sudo code 大概是這樣
int array[3G];
int counters[64M];
for( int i = 0; i < 3G; i++) {
   counter[array[i] % 64M] ++;
}
如果用openMP平行時 其實只要在for loop 加一行annotation
但可能會發生剛好兩個CPU同時要算到一個counter會可能出錯
但因為有64M個counter 所以剛好算到同一個機會很低 而且其實如果差異不大
其實也還可以

請問有人有類似的經驗嗎 有人說假設有16個CPU就設16 * 64M個 CPU的counter
最後在加起來 這個要 4G memory..可能還ok

另外設semaphore..好像會慢很多 但可能是我設的不好
另外就是 假設有衝突 不知道會發生什麼是 就是有counter少加了而以嗎
如果只要算個大概就好 可以直接去并行嗎 還是會memory有錯
其實錯沒關係 但其實我比較希望多加兒不是少加 有什麼算法或programming上得技巧
可以解決這個問題嗎




--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 143.48.10.57
※ 編輯: sorryChen       來自: 143.48.10.57         (05/17 02:49)
→ dryman:counter不適合用openMP
推 dryman:也許你可以分組，分成兩個迴圈
→ dryman:一個是以64個為單位跑的迴圈，沒用openMP
→ dryman:在這裡面的迴圈則是同時處理64M的
→ dryman:這樣就不會打架了