作者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)