作者LouisXIV (一個人寂寞 兩個人麻煩)
看板Programming
標題Re: C++ OpenMP 多CPU同時處理可能的問題
時間Thu May 20 14:08:18 2010
Let's go back the idea of bucket sort!!!!
This sorting algorithm needs to know "how many" for each number.
When using single CPU, race condition will not happen.
Now, you introduce the multiple CPU to do that.
I suggest that: using addtional memory to avoid the race condition problem.
If you have 16 workers(CPU), you can let them to count the different parts of
data. After they finished, you can use the same method to sum the coutners.
PS. You must know that your data size is very large, so you should consider
the memory cache issue, or the memery swap(?) will be the major problem to
make the performance bad.
Regards,
Louis
※ 引述《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: 140.114.78.109
※ 編輯: LouisXIV 來自: 140.114.78.109 (05/20 14:10)