How could you parallelise a 2D boids simulation

Question

How could you program a 2D boids simulation in such a way that it could use processing power from different sources (clusters, gpu).

In the above example, the non-coloured particles move around until they cluster (yellow) and stop moving.

The problem is that all the entities could potentially interact with each other although an entity in the top left is unlikely to interact with one in the bottom right. If the domain was split into different segments, it may speed the whole thing up, But if an entity wanted to cross into another segment there may be problems.

At the moment this simulation works with 5000 entities with a good frame rate, I would like to try this with millions if possible.

Would it be possible to use quad trees to further optimise this? Any other suggestions?

Answer 1

The master's thesis Parallel Simulation of Particle Fluids by Mattias Linde might offer some insight into data partitioning and algorithms for large-scale simulation.

His paper is geared towards Smoothed-Particle Hydrodynamics, which for the naive solution tends to use Spatial Hashing with a bucket size around the size of the kernel footprint of the particles in the simulation.

As the interaction distance is hard-clamped in typical SPH kernels, such partitioning optimizations are almost essential in scaling up the system.

Answer 2

The term I learned a long time ago was a game's speed of information.

If the speed of your boids is 1 and they only care about their neighbours, then the speed of information is 3, that is, a boid that is two squares away from you could be within the range you care about within one frame:

1 square movement per boid in the interaction (1+1) plus the distance that you can notice things (1) equals 3.

Given this, we learn that we can chunk off a map into pieces, sized as small as we like, but with this speed of information overlap into any neighbouring chunks.

I'll assume you're allowing your boids to move only one square, but they can see three

If you want to run a massive parallel sim, you chunk off into 10x10 grids, but overlap by 5 squares on each edge. Whenever one of your ends up being within the information distance from the local chunk's edge, you should update the neighbour, and once they traverse the boundary, they don't belong to you. If a neighbour says that a boid they are controlling has moved into your chunk, you have to take over it's AI.

This means that communication is localised to the neighbouring chunk managers, and the traffic is reduced to a minimum. The more jobs you run, the more CPUs you can use to power the simulation, but the more jobs you run, the more overlap their is, and therefore the more information passing between jobs/chunks as the simulation progresses. This is where you have to get heavy handed and tune the chunk size based on the AI complexity and what hardware you have available.

Answer 3

By reading your quesiton it seems you can take benefit of quad trees, create a quad tree and run simulation for each segment on a diffrent processing unit. This will cause checking only happen to objects near to each other. but you'll need to sync you threads every cycle. Which means to transfer some of those boids from one processing group to another. in general every cycle will consist of 3 steps :

1. Move all boids by one unit. (which can easily be processed using multiple threads)
2. Assigning each boid to a group*. This means using an algorithm of O(n) you have to select which boids are most likely to make a collision. This can also be handled using multiple threads.
3. In the end you have to check if two boids in a same group made collision.

*To create groups you can use the pattern below:

note that some boids may be a part of more than one group, but this pattern gives you a more accurate results. you may also create as many groups as you want using this pattern it's just a number you have to find for how many boids and the screen which screen size, what's is the best number of groups you need to create.

--edit--

there is another idea about segmentation which is described in the paper @LarsViklund sugested, this way there is far fewer double checkings and there is no need to increase/decrease number of threads between steps:

note that some areas are still a part of two groups. and width of area both group cover is exactly 2*maximum speed. In your case if boids move one pixel per simulation step you only need to share 2 pixel width area between each 2 group. and there is a small area which is a part of 4 groups. but in general this method is easier to implement and by far faster if implemented correctly. and by the way there is no reverse move this way, if some object can move it can move no more checking is required.

Answer 4

I tackled this problem recently using some of these answers as a starting point. The most helpful thing to keep in mind is that boids are a sort of simple n-body simulation: each boid is a particle that exerts a force on its neighbors.

I found the Linde paper difficult to read; I suggest instead looking at S.J. Plimpton's "Fast Parallel Algorithms for Short-Range Molecular Dynamics", which Linde referenced. Plimpton's paper is far more readable and detailed with better figures:

In a nutshell, atom-decomposition methods assign a subset of atoms permanently to each processor, force-decomposition methods assign a subset of pairwise force computations to each proc, and spatial-decomposition methods assign a sub-region of the simulation box to each proc.

I recommend you try AD. It's the easiest to understand and implement. FD is very similar. Here is nVidia's n-body simulation with CUDA using FD, which should give you a rough idea of how tiling and reduction can help drastically surpass serial performance.

SD implementations are generally optimizing techniques, and require some degree of choreography to implement. They're almost always faster and scale better.

This is because AD/FD requires building a "neighbor list" for each boid. If every boid needs to know the position of its neighbors, the communication between them is O(n²). You can use Verlet neighbor lists to reduce the size of the area each boid checks, which allows you to rebuild the list every few timesteps instead of every step, but it's still O(n²). In SD, each cell keeps a neighbor list, whereas in AD/FD every boid has a neighbor list. So instead of every boid communicating with each other, every cell communicates with each other. That reduction in communication is where the speed increase comes from.

Unfortunately the boids problem sabotages SD slightly. Having each processor keep track of a cell is most advantageous when the boids are somewhat evenly distributed across the entire region. But you want boids to cluster together! If your flock is behaving properly, the vast majority of your processors will be ticking away, exchanging empty lists with each other, and a small group of cells will end up performing the same calculations AD or FD would.

To deal with this, you can either mathematically tune the size of cells (which is constant) to minimize the number of empty cells at any given time, or use the Barnes-Hut algorithm for quad-trees. The BH algorithm is incredibly powerful. Paradoxically, it's extremely difficult to implement on parallel architectures. This is because a BH tree is irregular, so parallel threads will traverse it at wildly varying speeds, resulting in thread divergence. Salmon and Dubinski have presented orthogonal recursive bisection algorithms to distribute quadtrees evenly among processors, which must be restated iteratively for most parallel architectures.

As you can see, we're clearly in the realm of optimization and black magic at this point. Again, try reading Plimpton's paper and see if it makes any sense.

Answer 5

I'm assuming yours is a toroidal system, you can partition to the space so each unit has its sub area.

At each step the particles are moved, the particles that goes out the sub area are sent to the relevant processor; a communication step will syncronize the processors and a last poststep is taken to elaborate the foreign particles position (if any).

Here there are three problems here:

• 1) the shape of the sub area:

One can opt to rectangles but the show a small Area/perimeter ratio compared to cirlces. The bigger the border the more particles will leave. While the cicles exhibits the best A/p ratio, can not be used for tessellation, so you should indagate for some (possibily semi regular) tessellation with a good average A/p ratio. Obviously computing the tassel index by cell coordinate should be simple so consider this before to try a very exotic tasselation.

• 2) the communicationprotocol:

Depending upon what kind of communication infrastructure you have, you can think how to scatter the border-crossing informations among the processors. Broadcasting vs peer-to-peer reconstruction vs peer-to-peer communication are all options.

• 3) the sub-Area Allocation:

You should keep your elaboration balanced since there is a syncronizzation at each step. You can choose to statically or dynamically allocate areas to processors. This is not a big issue if your space is unifomly covered by active particles but i belive that it can be untrue in this case as collisions deactivate the particles.Changing the allocation requires an heavier communication step; some shortcut can be taken if all the processors shares the cross-border informations but you have to do some consideration about it

Answer 6

Try my simulation for clues https://github.com/wahabjawed/Boids-Simulation

I developed this on XNA