Java concurrency: executing many "infinite" tasks with few threads

Question

I'm building a (concurrent) simulator for a set of N particles that are moving in a space according to the Newton's laws. My idea is model each particle as a task, which interacts with other particles (tasks) in order to get their positions and masses in order to calculate the net force it is subject to. Each particle-task is something as

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

I can have a lot of particles (100 or more), so I can't create such a number of Java threads (which are mapped to physical threads). My idea is to use Runtime.getRuntime().availableProcessors()+1 threads onto which the many tasks can be executed.

However, I can't use a FixedThreadExecutor because the particle-tasks does not end. I would like to use a FixedThreadExecutor which must be also able to perform a sort of scheduling internally. Do you know something for this purpose?

Or, could you suggest me better approaches for modelling such a system by a point of view of concurrency (e.g. a different task decomposition) ?

P.s.: I am limited to "classical" concurrency mechanisms, not including actors or similar architectures.

Answer 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.

Answer 2

Rather than a thread per particle, I would create an ExecutorService with an appropriate number of threads. I would keep the particles in a list (or some other type of collection). I would create separate pieces of work to be executed (either as Runnable or Callable) for each particle's calculate and update steps. When you submit a piece of work to the executor, you get back a Future. Put these futures in a collection. After you have submitted all the pieces of work that you want to run in parallel, you iterate over your list of futures and call get() on each one to implement your synchronization steps.

You might end up creating a little POJO to associate a particle and it's calculated force (or stash the calculated force in the particle instance).

Answer 3

I would assume you are storing all your particles in maybe an array of 2-dimensiional array? This would be a great candidate for the Fork-Join Framework.

You would split the calculation of portions of the array into smaller portions. You keep splitting until at a certain size. Finally you calculate and return. The returned value will then be joined and calculated with other the other side of the tree.

Answer 4

The biggest killer for performance is likely to be the thread safety checks you perform to ensure all the particles are interacting in a thread safe manner. I suggest you use one thread per core and try to minimise the interaction between threads. This can be done by dividing your space into threads e.g. half X, half Y, half Z divides the space into 8. You cal look at all the interactions in each space concurrently and independently and you only need to worry when a particle passed from one space/thread to another.

Answer 5

Why don't you do the calculations in discrete steps ?

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
}

}

First calculate the force for each particle, but don't change its current state. After you've calculated it for every particle, then update its internal state according to your previous calculations. In this way even a single thread will be enough, and of course you can split up the calculations across multiple threads but you'll need additional synchronization

JAVA 8 UPDATE

Using Java 8 you can take advantage of multi-core systems, while not having to take care of threads, synchronization etc.

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

       allParticles.parallelStream().forEach(p ->   p.nextState());      
 }

Answer 6

The particle should be itself Runnable and Callable, this will allow you to avoid creating a lot of extra objects and synchronize different steps. Here is a 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);
    }
  }
}

Answer 7

Since, verifying collisions normally take n^2 calculations, dividing the space is a good idea. although, it will be essentially a O(n^2) problem.

This problem claims badly for a matrix approaching (but take a look in Parallel computing to know the best ideas to deal with it) You could use some techniques pointed here: An efficient way to simulate many particle collisions?

Please, note that should be a bad idea to use Actor model because threads will be problematic after certain number.

There's now Java OpenCL lib (ex: Aparapi) and Java 9 should bring openCL natively with Sumatra project. So, you could use Fork and Join lib and JVM will use OpenCL under the hood.