10

我正在为根据牛顿定律在空间中移动的一组 N 个粒子构建一个（并发）模拟器。我的想法是将每个粒子建模为一个任务，它与其他粒子（任务）相互作用以获得它们的位置和质量，从而计算它所受的净力。每个粒子任务都是

while(true){
   force = thisParticle.calculateNetForce(allTheParticles);
   thisParticle.waitForAllTheParticlesToCalculateNetForce(); // synchronization
   thisParticle.updatePosition(force);
   thisParticle.waitForAllTheParticlesToUpdateTheirState(); // synchronization
}

我可以有很多粒子（100 个或更多），所以我无法创建这么多 Java 线程（映射到物理线程）。我的想法是使用Runtime.getRuntime().availableProcessors()+1可以执行许多任务的线程。

但是，我不能使用 FixedThreadExecutor 因为粒子任务没有结束。我想使用一个 FixedThreadExecutor ，它还必须能够在内部执行某种调度。你知道一些为此目的吗？

或者，您能否建议我从并发的角度（例如，不同的任务分解）对这样的系统进行建模的更好方法？

Ps：我仅限于“经典”并发机制，不包括actor或类似架构。

4

7 回答 7

5

性能的最大杀手可能是您执行的线程安全检查，以确保所有粒子都以线程安全的方式进行交互。我建议你每个核心使用一个线程，并尽量减少线程之间的交互。这可以通过将您的空间划分为线程来完成，例如一半 X、一半 Y、一半 Z 将空间划分为 8。您可以同时独立地查看每个空间中的所有交互，并且您只需要担心当一个粒子从一个穿过时空间/线程到另一个。

于 2013-08-05T13:21:40.030 回答
3

我假设您将所有粒子存储在二维数组的数组中？这将是Fork-Join 框架的绝佳候选者。

您可以将数组部分的计算拆分为更小的部分。你一直分裂直到达到一定的大小。最后你计算并返回。然后将返回的值与树的另一侧连接并计算。

于 2013-08-05T13:20:31.160 回答
2

我将创建一个具有适当数量线程的 ExecutorService，而不是每个粒子一个线程。我会将粒子保存在列表（或其他类型的集合）中。我将为每个粒子的计算和更新步骤创建要执行的单独工作（作为可运行或可调用）。当你向执行者提交一份工作时，你会得到一个 Future。将这些期货放在一个集合中。在你提交了所有你想并行运行的工作之后，你遍历你的 future 列表并调用get()每一个来实现你的同步步骤。

您最终可能会创建一个小 POJO 来关联粒子及其计算的力（或将计算的力存储在粒子实例中）。

于 2013-08-05T13:53:34.677 回答
1

For each particle, you call calculateNetForce(allTheParticles), which I suppose makes your computations proportional to O(N^2) (the square of the number of all particles). This is the main performance killer, and you better find an algorithm with complexity of O(N), and only then try to parallelize. Off the top of my head, I can propose to first calculate the sum mass and the center of gravity for all particles. Then, for each particle, calculate mass and the center of the rest of particles. This can be done with taking the total mass and center, and adding a "hole" with negative mass instead of the current particle. Then calculate the force between the particle and the rest of them. The calculations for each particle are independent and can be parallelized with any of ways proposed by other commenters.

于 2013-08-23T16:30:14.210 回答
1

为什么不分步进行计算？

while(true){


for(Particle p : allParticles){
   force = p.calculateNetForce(allParticles);   
   p.setNextPosition(force); //Remembers, but doesn't change the current position
}

for(Particle p : allParticles){
    p.nextState(); //Change the position
}

}

首先计算每个粒子的力，但不要改变它的当前状态。在你为每个粒子计算完之后，然后根据你之前的计算更新它的内部状态。这样，即使是单个线程也足够了，当然您可以将计算拆分到多个线程中，但您需要额外的同步

JAVA 8 更新

使用 Java 8，您可以利用多核系统，而不必处理线程、同步等。

 while(true){
       allParticles.parallelStream().forEach(p -> {
           double force = p.calculateNetForce(allParticles);
           p.setNextPosition(force)
       });

       allParticles.parallelStream().forEach(p ->   p.nextState());      
 }
于 2013-08-05T14:17:48.697 回答
0

由于验证碰撞通常需要 n^2 次计算，因此划分空间是一个好主意。虽然，这本质上是一个 O(n^2) 问题。

这个问题对矩阵逼近很不利（但请查看并行计算以了解处理它的最佳方法）您可以使用此处指出的一些技术： 模拟许多粒子碰撞的有效方法？

请注意，使用Actor 模型应该是一个坏主意，因为线程在一定数量之后会出现问题。

现在有 Java OpenCL 库（例如：Aparapi），Java 9 应该在 Sumatra 项目中自带 openCL。因此，您可以使用 Fork 和 Join lib，而 JVM 将在后台使用 OpenCL。

于 2014-02-12T16:03:58.697 回答
0

粒子本身应该是可运行和可调用的，这将允许您避免创建大量额外的对象并同步不同的步骤。这是一个 SSCCEE：

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Particle implements Callable<Void> {

  private enum ParticleState {
    POSITION_UPDATED, FORCE_CALCULATED
  }

  private int id;
  private int calculatedForce;
  private ParticleState particleState = ParticleState.POSITION_UPDATED;
  private List<Particle> allTheParticles;

  public Particle(int id, List<Particle> allTheParticles) {
    this.id = id;
    this.allTheParticles = allTheParticles;
  }

  private void calculateNetForce() {
    System.out.println("calculation in " + id);
    String someIntenseOperation = "";
    for (int i = 0; i < 10000; i++) {
      someIntenseOperation += allTheParticles.size();
    }
    calculatedForce = 0;
    particleState = ParticleState.FORCE_CALCULATED;
  }

  private void updatePosition() {
    System.out.println("updating position of " + id);
    particleState = ParticleState.POSITION_UPDATED;
  }

  @Override
  public Void call() throws Exception {
    switch (particleState) {
      case FORCE_CALCULATED:
        updatePosition();
        break;
      case POSITION_UPDATED:
        calculateNetForce();
        break;
    }
    return null;
  }

  public static void main(String[] args) throws InterruptedException {
    final ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors() + 1);
    final List<Particle> allTheParticles = new ArrayList<>();
    for (int i = 0; i < 20; i++) {
      allTheParticles.add(new Particle(i, allTheParticles));
    }
    while (true) {
      executor.invokeAll(allTheParticles);
      executor.invokeAll(allTheParticles);
    }
  }
}
于 2013-08-05T14:43:50.790 回答