Patent ID: 8065090

Claim:
A method for creating a load balanced spatial partitioning of a structured, diffusing system of particles with pairwise interactions, the method comprising: a processor device configured to perform an n-body simulation by performing steps of: defining a three-dimensional simulation space comprising a plurality of particles and a plurality of processor nodes by mapping said simulation space to node space using a k-d tree on said three-dimensional simulation space, wherein defining said three-dimensional simulation space comprises: identifying a cutoff area by cutting off pair interaction beyond a defined radius; ensuring that there exists at least one processor node for every pair of particles within the cutoff area that can calculate the pairwise interaction by identifying a minimal set of communicating nodes for a particular particle as all those nodes which contain any of the spherical volume of space centered about the particle; and dividing the simulation space into a same number of voxels as processor nodes; determining a weight corresponding to a computation cost for a particular pair interaction of particles to the simulation space at a midpoint between the interacting particles within the defined radius; assigning the determined weight to the midpoint in the simulation space between locations of the two interacting particles; broadcasting the position of each particle to points in simulation space within a distance of one-half of the cut-off radius; performing a spatial partitioning of a volume of the simulation space such that all partitions have substantially a same weight; and assigning computation of the fragment pair interaction to the processing node owning the voxel that contains the midpoint of a line connecting the interacting pair of particles.