1

我正在为 N-Body 问题实现 Barnes-Hut 算法的多线程解决方案。

主类执行以下操作

public void runSimulation() {
        for(int i = 0; i < numWorkers; i++) {
            new Thread(new Worker(i, this, gnumBodies, numSteps)).start();
        }
        try {
            startBarrier.await();
            stopBarrier.await();
        } catch (Exception e) {e.printStackTrace();}
}

bh.stop- 和 bh.startBarrier 是 CyclicBarriers 将 start- 和 stopTime 设置为 System.nanoTime(); 到达时（障碍动作）。

工人运行方法：

public void run() {
    try {
        bh.startBarrier.await();

        for(int j = 0; j < numSteps; j++) {
            for(int i = wid; i < gnumBodies; i += bh.numWorkers) {
                bh.addForce(i);
                bh.moveBody(i);
            }
            bh.barrier.await();
        }
        bh.stopBarrier.await();
    } catch (Exception e) {e.printStackTrace();}
}

addForce(i) 遍历一棵树并进行一些计算。它不会影响任何共享变量，因此不使用同步。O(NlogN)。

moveBody(i) 对一个元素进行计算并且不使用同步。上）。

当达到 bh.barrier 时，就会建立一个包含所有实体的树（屏障动作）。

现在来解决问题。运行时间随着使用的线程数线性增加。gnumBodies = 240，numSteps = 85000 和四个核心的运行时：

  • 1 个线程 = 0.763
  • 2 个线程 = 0.952
  • 3 个线程 = 1.261
  • 4 个线程 = 1.563

为什么运行时不会随着使用的线程数而减少？

编辑：添加硬件信息

4

5 回答 5

1

你在什么硬件上运行它？运行多个线程有其开销，因此将任务拆分为小的子任务可能不值得。

另外，尝试使用 ExecutorService 而不是线程。这样您就可以使用线程池，而不是为每个任务创建一个实际的线程。拥有更多硬件可以处理的线程是没有用的。

在我看来，每个线程都会做同样的工作。会是这样吗？创建工作人员时，除了 for i 之外，您每次都使用相同的参数。

于 2016-03-17T21:33:46.337 回答
0

您的员工numWorker独立完成相同的工作时间。唯一的共享对象是您的 CyclicBarrier。await()等待所有奇偶校验在此屏障上调用 await。随着工人数量的增加，它花费更多的时间在await()

于 2016-03-17T21:42:15.257 回答
0

除非您还有多个 CPU 内核，否则多线程不会提高执行速度。

线程进行数学计算并且可以全速运行

如果你只有一个 CPU 核心，那么在一个线程或多个线程中运行计算都是一样的。在多线程中运行并没有带来性能上的好处，但会带来线程切换的开销，因此实际上总性能会差一些。

如果您有多个可用的 CPU 内核，则线程可以在物理上并行运行，最多可达到内核数。这意味着 4-8 个线程可能在当今的桌面硬件上运行良好。

等待 IO 并被挂起的线程

如果您不进行数学计算，但执行一些涉及慢 I/O 的事情（例如网络、文件或数据库），则线程是有意义的。当一个线程等待 IO 时，另一个线程可以使用相同的 CPU 内核，而不是占用程序的运行。这就是 Web 服务器和数据库解决方案使用比 CPU 内核更多的线程工作的原因。

避免不必要的同步

然而，您的测量显示同步错误。我猜你应该从线程代码中删除所有 xxbarrier.await() 。我不确定 xxBarriers 与 System nanotime 的目标是什么，但任何不必要的同步很容易导致性能下降。您不是在计算，而是在等待 xxxBarriers。

于 2016-03-17T21:37:41.280 回答
0

当我以更少的步骤运行具有更多主体的应用程序时，应用程序按预期扩展。所以问题可能是屏障的开销！

于 2016-04-01T06:29:27.423 回答
0

如果您有多个内核或超线程可用，那么运行多个线程将受益于底层硬件。

如果只存在一个内核，那么如果您的应用程序涉及至少一项非 CPU 密集型工作（例如与人的交互），那么多线程可以带来“感知”的好处。与现代 CPU 相比，人类的速度非常慢。因此，如果您的应用程序需要从人类那里获取多个输入并对其进行处理，那么将输入和计算分开在两个线程中是有意义的。当人类提供输入时，部分计算可以在另一个线程中完成。从而及时全面改善。

如果您的应用程序必须进行计算并且硬件中不存在多线程支持，那么最好使用单线程。您的“计算”已经在管道中背靠背排列，CPU 已经以（几乎）最大速度运行。多线程将需要上下文切换时间，这将增加进行计算所需的时间。

于 2016-03-17T21:52:27.017 回答