v****s
发帖数: 1112 | 1 【 以下文字转载自 CS 讨论区 】
发信人: vicfcs (ML+CV), 信区: CS
标 题: 多线程优化求助！
发信站: BBS 未名空间站 (Sat Sep 11 08:49:35 2010, 美东)
最近赶deadline，一个巨大无比的运算，已经吃掉我supercomputer account上的 5000
core hour了。。。。
不是很复杂，就是运算量太大了，如附图。
每个步骤（一共要算大概500，000次）：
table 1 and table 2已经load到内存了，他们的长度各自是M, N. M,N can be upto 1
million. 要计算那个result table的每个cell，每个cell只要取对应位置的table1[i
,:], table2[j,:], 然后计算出resulttable[i,j].
现在我做的优化是把所有data都load到内存，然后搞2个for loop去sequentially
compute，但是这样太不efficient了，估计下周都没法搞完。。。大牛给出出主意，怎
么设计multi thread来加速！谢谢 |
g*****g
发帖数: 34805 | 2 这个有啥复杂的？两个数据源表都是不变的，结果表的所有结果也是
互相独立的。对于每一项，起一个Job，扔进Threadpool算就是了，
看机器强弱设定一下线程数即可。
别说supercomputer，整一群台式机都搞定了。
5000
1
[i
【在 v****s 的大作中提到】
: 【 以下文字转载自 CS 讨论区 】
: 发信人: vicfcs (ML+CV), 信区: CS
: 标 题: 多线程优化求助！
: 发信站: BBS 未名空间站 (Sat Sep 11 08:49:35 2010, 美东)
: 最近赶deadline，一个巨大无比的运算，已经吃掉我supercomputer account上的 5000
: core hour了。。。。
: 不是很复杂，就是运算量太大了，如附图。
: 每个步骤（一共要算大概500，000次）：
: table 1 and table 2已经load到内存了，他们的长度各自是M, N. M,N can be upto 1
: million. 要计算那个result table的每个cell，每个cell只要取对应位置的table1[i
|
y***d
发帖数: 2330 | 3 这个运算似乎很奇怪，10^6 x 10^6，有谁会要这样的结果呢？
【在 g*****g 的大作中提到】
: 这个有啥复杂的？两个数据源表都是不变的，结果表的所有结果也是
: 互相独立的。对于每一项，起一个Job，扔进Threadpool算就是了，
: 看机器强弱设定一下线程数即可。
: 别说supercomputer，整一群台式机都搞定了。
:
: 5000
: 1
: [i
|
v****s
发帖数: 1112 | 4 10^6 x 10^6, it's actually just like cross correlation matrix, then we
compute the histogram out from it...
【在 y***d 的大作中提到】
: 这个运算似乎很奇怪，10^6 x 10^6，有谁会要这样的结果呢？
|
v****s
发帖数: 1112 | 5 是啊，如果用java，再用K个thread，怎么run 这些threads? 还有就是怎么判断某个
thread已经算好了，然后给安排下一个？请讲讲threadpool好么？谢谢虫哥！
【在 g*****g 的大作中提到】
: 这个有啥复杂的？两个数据源表都是不变的，结果表的所有结果也是
: 互相独立的。对于每一项，起一个Job，扔进Threadpool算就是了，
: 看机器强弱设定一下线程数即可。
: 别说supercomputer，整一群台式机都搞定了。
:
: 5000
: 1
: [i
|
y***d
发帖数: 2330 | 6 如果只是 histogram 的话，这个 result[i,j] 还是不要存储了，直接扔给 histogram
吧... 否则，如果是浮点数的话，8T，太大了...
把 j 分成 100 段，就可以分到 100 个进程来算了，最后把 histogram merge 了就成
【在 v****s 的大作中提到】
: 10^6 x 10^6, it's actually just like cross correlation matrix, then we
: compute the histogram out from it...
|
v****s
发帖数: 1112 | 7 yes, that resultmatrix is not stored, but eventually we need to run thru all
elements of it....
能展开说说这个thread应该怎么写么？能用java最好，cpp也行！
histogram
【在 y***d 的大作中提到】
: 如果只是 histogram 的话，这个 result[i,j] 还是不要存储了，直接扔给 histogram
: 吧... 否则，如果是浮点数的话，8T，太大了...
: 把 j 分成 100 段，就可以分到 100 个进程来算了，最后把 histogram merge 了就成
|
g*****g
发帖数: 34805 | 8 这个很简单，看看ThreadPoolExecutor的文档，初始化core size。
你每个Job是一个Runnable，往里扔就是了。至于ThreadPool是怎么
实现的，你不需要知道。
如果怕内存占用太多，在afterExecute()里加新Job即可。
【在 v****s 的大作中提到】
: 是啊，如果用java，再用K个thread，怎么run 这些threads? 还有就是怎么判断某个
: thread已经算好了，然后给安排下一个？请讲讲threadpool好么？谢谢虫哥！
|
v****s
发帖数: 1112 | 9 谢谢虫哥，你说的是不是这个？
http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/ThreadPoolExecutor.html
这个class会自动判断哪个thread已经运行完了然后分配新的data给它？
【在 g*****g 的大作中提到】
: 这个很简单，看看ThreadPoolExecutor的文档，初始化core size。
: 你每个Job是一个Runnable，往里扔就是了。至于ThreadPool是怎么
: 实现的，你不需要知道。
: 如果怕内存占用太多，在afterExecute()里加新Job即可。
|
g*****g
发帖数: 34805 | |
|
|
v****s
发帖数: 1112 | 11 谢谢虫哥！
【在 g*****g 的大作中提到】
: 得，我好人做到底。
: http://download.oracle.com/javase/tutorial/essential/concurrency/pools.html
: 先读读tutorial吧。threadpool这种东西也算基础了。
: java程序员不见得都会用到，但至少都应该知道。
|
v****s
发帖数: 1112 | 12 我看了一下threadpool，觉得很有用。 我想这样用：
ThreadPoolExecutor threadPool = new ThreadPoolExecutor(poolSize,
maxPoolSize, keepAliveTime, TimeUnit.SECONDS, queue);
for(i = 0; i
for(j = 0; j
while(threadPool.getActiveCount < poolSize){
threadPool.execute( computeRij(a[i], b[j] ) );
}
}
}
但是可能中间这个while会占用太多的cpu时间因为很多时候都在空循环。怎样才能把这
个threadpool用好呢？我感觉关键在于如何知道哪个thread在什么时候complete了。谢谢！！
【在 g*****g 的大作中提到】
: 得，我好人做到底。
: http://download.oracle.com/javase/tutorial/essential/concurrency/pools.html
: 先读读tutorial吧。threadpool这种东西也算基础了。
: java程序员不见得都会用到，但至少都应该知道。
|
g*****g
发帖数: 34805 | 13 That's not how you use it. If you want to run N threads,
submit N jobs into threadpool. And in afterExecute, submit
another one.
【在 v****s 的大作中提到】
: 我看了一下threadpool，觉得很有用。 我想这样用：
: ThreadPoolExecutor threadPool = new ThreadPoolExecutor(poolSize,
: maxPoolSize, keepAliveTime, TimeUnit.SECONDS, queue);
: for(i = 0; i: for(j = 0; j: while(threadPool.getActiveCount < poolSize){
: threadPool.execute( computeRij(a[i], b[j] ) );
: }
: }
: }
|
r****t
发帖数: 10904 | 14 这种问题用显卡算比较好。
5000
1
[i
【在 v****s 的大作中提到】
: 我看了一下threadpool，觉得很有用。 我想这样用：
: ThreadPoolExecutor threadPool = new ThreadPoolExecutor(poolSize,
: maxPoolSize, keepAliveTime, TimeUnit.SECONDS, queue);
: for(i = 0; i: for(j = 0; j: while(threadPool.getActiveCount < poolSize){
: threadPool.execute( computeRij(a[i], b[j] ) );
: }
: }
: }
|
v****s
发帖数: 1112 | 15 cuda写起来太麻烦了。。。
【在 r****t 的大作中提到】
: 这种问题用显卡算比较好。
:
: 5000
: 1
: [i
|
r****t
发帖数: 10904 | 16 我觉得还好啊，不用 shared mem 的话程序很简单的，处理这种问题很适合。
【在 v****s 的大作中提到】
: cuda写起来太麻烦了。。。
|
v****s
发帖数: 1112 | 17 虫哥能给个pseudo code么？我折腾了一宿，这个afterExecute就是弄不好。。。
【在 g*****g 的大作中提到】
: That's not how you use it. If you want to run N threads,
: submit N jobs into threadpool. And in afterExecute, submit
: another one.
|
g*****g
发帖数: 34805 | 18 public class MyThreadPool extends ThreadPoolExecutor {
private MyJobCreator creator;
public void afterExecute(Runnable r, Throwable t) {
//do some clean up, log processing for finished job
submit(creator.createNewJob());
}
}
And in MyJobCreator constructor
MyThreadPool pool = new MyThreadPool();
pool.setCreator(this);
Then you can create N job and submit to initialize, that's all.
【在 v****s 的大作中提到】
: 虫哥能给个pseudo code么？我折腾了一宿，这个afterExecute就是弄不好。。。
|
v****s
发帖数: 1112 | 19 thanks good bug..
我试了一下你贴的这个pseudocode,觉得我思路转不过弯来。。。这2个class怎么你中
有我我中有你？
如果我现在有另一个class 叫做 RunAllJobs, 里面包含一个main() entry, 然后怎么
弄？谢谢。。。。
【在 g*****g 的大作中提到】
: public class MyThreadPool extends ThreadPoolExecutor {
:
: private MyJobCreator creator;
: public void afterExecute(Runnable r, Throwable t) {
: //do some clean up, log processing for finished job
: submit(creator.createNewJob());
: }
: }
: And in MyJobCreator constructor
: MyThreadPool pool = new MyThreadPool();
|
v****s
发帖数: 1112 | 20 在我们组的java engineer帮助下搞定了。。。。。
把这2个class都弄成singleton，MyJobCreator 负责create下一个thread，给MyTPE的
afterExecute()运行就ok！
【在 v****s 的大作中提到】
: thanks good bug..
: 我试了一下你贴的这个pseudocode,觉得我思路转不过弯来。。。这2个class怎么你中
: 有我我中有你？
: 如果我现在有另一个class 叫做 RunAllJobs, 里面包含一个main() entry, 然后怎么
: 弄？谢谢。。。。
|
h***i
发帖数: 1970 | 21 这个是正道。
【在 r****t 的大作中提到】
: 这种问题用显卡算比较好。
:
: 5000
: 1
: [i
|
