我在jre 1.7中使用Java叉/join框架编写了一个多线程程序。该程序的目的是在四叉树的所有节点中找到满足指定条件的某些点(四叉树中的每个叶节点都可以用不受限制的点数来填充,例如,可以是0或1000)。与16核处理器上的串行程序相比,我测试了多线程程序的加速比,而加速比仅为1.3-1.5。以下是伪代码:
public class QuadtreeFindMultiThread extends RecursiveTask<IntArrayList> {
private Quadtree T;
private ObjectArrayList<Node> leaf_nodes;
private ObjectArrayList<Entry> candidatePoints;
private static int POINT_THRESHOLD = 50;
private static int NODE_THRESHOLD = 1;
public QuadtreeFindMultiThread(Quadtree T) {
this.T = T
this.leaf_nodes = T.get_nonempty_leaf_nodes();
this.candidatePoints = new IntArrayList();
}
private QuadtreeFindMultiThread(Quadtree T, IntArrayList leaf_nodes) {
this.T = T;
this.leaf_nodes = leaf_nodes; // reference copy
this.candidatePoints = new IntArrayList();
}
private IntArrayList QuadtreeFind() {
//...
//...
return candidatePoints;
}
private int getPointNum(){
int count = 0;
for(Node node:this.leaf_nodes){
count += node.getAllPoints().size();
}
return count;
}
@Override
public IntArrayList compute() {
if (this.getPointNum() <= POINT_THRESHOLD || this.leaf_nodes.size() <= NODE_THRESHOLD) {// trivial problem, solve by single thread
this.candidatePoints = QuadtreeFind();
} else {// START: divide and conquer
// Divide Step: partition this.leaf_nodes by direction: NW, NE, SW, SE
Partition leaf_nodes to four quadrants: leaf_nodes_NW,
leaf_nodes_NE,
leaf_nodes_SW,
leaf_nodes_SE
// Conquer Step
QuadtreeFindMultiThread thread_NW = new QuadtreeFindMultiThread(
this.T, leaf_nodes_NW);
QuadtreeFindMultiThread thread_NE = new QuadtreeFindMultiThread(
this.T, leaf_nodes_NE);
QuadtreeFindMultiThread thread_SW = new QuadtreeFindMultiThread(
this.T, leaf_nodes_SW);
QuadtreeJoinMultiThread thread_SE = new QuadtreeFindMultiThread(
this.T, leaf_nodes_SE);
// fork three new sub threads
thread_NE.fork();
thread_SW.fork();
thread_SE.fork();
this.candidatePoints.addAll(thread_NW.compute()); // main thread
this.candidatePoints.addAll(thread_NE.join());
this.candidatePoints.addAll(thread_SW.join());
this.candidatePoints.addAll(thread_SE.join());
}// END: divide and conquer
return this.candidatePoints;
}
}我刚开始使用Java多线程编程,为什么这个程序在16核处理器机器上的加速速度这么差?我还在我的笔记本电脑上测试了这个带有2个内核和2个虚拟核的多线程程序,加速速度也接近于1.3-1.5。在我的笔记本电脑上,多线程程序的性能有时甚至比16核处理器的性能还要好。
它似乎是默认的调度策略的叉子/连接帧叉子是LIFO,我如何才能更改为FIFO?
顺便说一句,我发现处理一些有很多点的叶节点需要花费很长的处理时间。我是否可以修改叉/连接调度程序,使其首先处理具有大量点的节点?因此,它应该获得更好的性能。谢谢!
发布于 2014-01-19 22:09:42
这个框架没有太多的文档。当然,我们很容易误解这个目的。该框架用于平衡树的递归分解(DAG.)它不能很好地容忍误用,因为它最初是作为研究论文中的一个实验设计的。
框架想要向左、向右分开。Left.fork()、right.compute()、left.join()。这样,它就沿着平衡的树的叶子走下去。分叉的任务回到它的状态,希望被其他线程偷走。当一切按计划进行时,每个线程都会为其他线程分叉足够的任务,并保持忙碌。
您要做的是将三个任务放回deque中,然后处理一个四边形。这并不能很好地分散工作。您最终可以得到的是有许多任务挂起的多个线程,而不是有几个挂起任务的许多线程。此框架无法正确地进行负载平衡。
还有连接()的问题。Join()需要一个上下文开关来释放线程用于其他工作。这个框架不能进行上下文切换,因此它为每个join()创建一个“延续线程”,然后为连接线程发出wait()。有了许多联接,您可能会有大量的创建/销毁开销。Java8版本取消了“延续线程”,但最终会频繁地停止运行(特别是您所使用的方式)。
尝试重新设计来处理DAG,看看会发生什么。它有16个线程,应该可以正常工作。
发布于 2014-01-19 17:24:05
任何并行问题的诀窍是平衡两个不同的问题:
一方面,我们希望通过尽可能小的任务来获得最佳的负载平衡,这样我们就不必在每个人都在等待的时候,在单个CPU上完成其巨大的最后一个任务。另一方面,调度细粒度任务会增加开销,因此我们希望使任务尽可能大,以尽可能少地增加调度开销。
诀窍是要在这两个极端之间找到一个很好的平衡,这就是为什么叉/连接程序通常有一个阈值,可以从这个阈值中单独三次执行任务。因此,正如Peter在他的评论中所指出的,您需要调整两个阈值,以获得最佳的性能。
最优阈值取决于许多因素--主要取决于问题的大小,但不同的计算机架构、内存等也会对其产生强烈的影响。解决这个问题的最好方法是将阈值作为输入参数,并在不同程度上运行基准测试。
https://stackoverflow.com/questions/21219042
复制相似问题