MIT Reacting Gas Dynamics Laboratory

Fast domain decomposition for parallel vortex simulations

A large-scale 3D vortex simulation involves the evaluation of pairwise particle interactions, whose computational cost scales as O(N^2), where N is the number of computational elements. The recent development of fast multipole approaches reduces this cost to O(N Log N), shedding light on large-scale simulations using 3D vortex methods. However, truly large-scale calculations can only be enabled by achieving parallel implementation of a fast multipole algorithm. The task here is to develop new methods to parallelize fast multipole algorithms efficiently.

We have developed a new algorithm, based on k-means clustering, for partitioning parallel hierarchial N-body interactions [1]. Since the number of particle-cluster interactions and the order at which they are performed are directly affected by partition geometry, it is essential to optimize partition geometry for best performance. Our k-means clustering algorithm minimizes the sum of clusters' second moments and creates well-localized domains, and thus reduces the computational cost by enabling the use of lower-order approximations and fewer cells.

We have also introduced techniques for dynamic load balancing, compatible to our k-means clustering algorithm, including adaptive scaling of cluster volumes and redistribution of cluster centroids. Our dynamic load balancing algorithm guarantees excellent load balancing even for an irregular, time-evolving particle distribution containing a range of length scales and the continual introduction of the vortex particles into the domain.

An example of geometric domain decomposition based on the k-means clustering technique

Publications