GPU-based Direct Simulation Monte Carlo

It's been a while since my last post. Lots of things have changed. Now I'm a PhD student at UW-Milwaukee and a research assistant at the Complex Systems Simulation Lab. In this post I will describe my first project which is a GPU (CUDA) implementation of DSMC method for particle simulations.

DSMC is a computational method for fluid mechanics simulation. Simply put, it can be used for simulation of interaction between gas molecules and a solid body. For example, the case, when a space ship enters the atmosphere can be simulated. The method is relatively simple, but it requires simulation of huge number of molecules for an accurate result, so it is a good candidate for parallelization.

Implementation details

Since it is a Monte Carlo-based method, it requires a random number generator. The Mersenne Twister is one of the best RNGs at the moment, however it has a large state which doesn't make it very suitable for GPU, however this RNG was used in the simulation. I modified the NVIDIA's sample, so each thread in the simulation can run its own twister. Also XOR128 was implemented as well and is used for very large simulations.

For inter-particle collisions I used Bird's collision method, which is currently the most accurate one. Since it is a particle-based simulation, I adopted particles' hashing method from NVIDIA's particles sample (using radixsort).

During the simulation particles can collide with an obstacle (polygonal object). For more efficient processing this object is subdivided using a regular grid. For AABB to triangle testing I used very fast and accurate method by Moller. There is also very nice ray to triangle testing method by the same author, I used this method as well. The simulation can easily run in a real time with systems up to 16 mln particles and with a complex polygonal object in it.

As a result, I achieved a speedup of 65x over a CPU implementation and got some nice screenshots:

In these screenshots a small window in a top right corner shows per-cell concentration. Red is high, blue is low, green is in between. The blue cells in the simulation show the current grid slice that is presented in the concentration window.

I also submitted a paper to SIMULATION journal about this method. It got accepted, so I'll post it here when the journal is released. I will also describe particular aspects of this implementation in more details in my further posts, since it will take lots of space.

This was my first project, but I have some more to describe, so stay tuned :)