Reduced message count for interaction decomposition of N-body simulations

Abstract

Disclosed are a method of and system for creating a load balanced spatial partitioning of a structured, diffusing system of particles with pairwise interactions that is scalable to a very large number of nodes and has favorable communications characteristics including well defined bounds on the number of hops and the number of nodes to which a particle's position must be sent. To deal with structural imbalance, we can assign a weight corresponding to the computational cost for a particular pair interaction of particles or locally clustered groups of particles to simulation space at the midpoint of the distance between the particles or centers of the clusters. We then carry out a spatial partitioning of the simulation volume using a k-d tree or optimal recursive bisection (ORB) to divide the volume into sections that have approximately equal total weights. To deal with local degradation of the load balance caused by changes in the distribution of particles from that used to determine the original spatial decomposition one can assign the actual computation of the pair interaction between two particles to any node that has the positions of both particles.

1 . A method of creating a load balanced spatial partitioning of a structured, diffusing system of particles, comprising the steps of:
 providing a computer system having a plurality of processing nodes;   assigning computational weights to the particles;   separating said system of particles, based on the computational weights assigned to the particles, into a number of voxels;   mapping each voxel to one of the processing nodes of the computer system; and   for each voxel, using said one of the processing nodes, to which said each voxel is mapped, to perform a series of calculations for the particles in said each voxel.   
   
   
       2 . A method according to  claim 1 , wherein:
 the step of assigning computational weights includes the step of assigning each of the computational weights to a position in said system; and   the separating step includes the step of separating said system of particles into said number of voxels based on the positions assigned to the computational weights.   
   
   
       3 . A method according to  claim 2 , wherein the voxels have an approximately equal total of computational weights. 
   
   
       4 . A method according to  claim 2 , wherein:
 each computational weight is associated with a pair of the particles; and   the step of assigning each of the computational weights to a position includes the step of assigning each computational weight to a position between the pair of particles with which said each computational weight is associated.   
   
   
       5 . A method according to  claim 1 , wherein:
 the computer system has a given number of said processing nodes;   said given number of voxels equals said given number; and   the mapping step includes the step of mapping each of the voxels to a respective one of the processing nodes of the computer system.   
   
   
       6 . A method according to  claim 1 , comprising the further step of, over time, assigning said calculations for some of the particles from one of the processing nodes to another of the processing nodes to alleviate reduced load balance caused by changes in the distribution of particles in said system. 
   
   
       7 . A method according to  claim 1 , wherein:
 the using step includes the step of using said one of the processing nodes to perform said series of calculations at a first time for the particles in said each voxel; and   comprising the further steps of, for each of at least some of the particles in the system:   broadcasting the position of the particle to a set of said processing nodes; and   using said one of said set of processing nodes to perform said calculations, at a second time.   
   
   
       8 . A system for creating a load balanced spatial partitioning of a structured, diffusing system of particles, comprising the steps of:
 a computer system having a plurality of processing nodes;   means for assigning computational weights to the particles;   means for separating said system of particles, based on the computational weights assigned to the particles, into a number of voxels; and   means for mapping each voxel to one of the processing nodes of the computer system; wherein said one of the processing nodes performs a series of calculations for the particles in said each voxel.   
   
   
       9 . A system according to  claim 8 , wherein:
 the means for assigning computational weights includes means for assigning each of the computational weights to a position in said system; and   the means for separating includes means for separating said system of particles into said number of voxels based on the positions assigned to the computational weights.   
   
   
       10 . A system according to  claim 9 , wherein the voxels have an approximately equal total of computational weights. 
   
   
       11 . A system according to  claim 9 , wherein:
 each computational weight is associated with a pair of the particles; and   the assigning means includes means for assigning each computational weight to a position between the pair of particles with which said each computational weight is associated.   
   
   
       12 . A system according to  claim 8 , wherein:
 the computer system has a given number of said processing nodes;   said given number of voxels equals said given number; and   the means for mapping includes means for mapping each of the voxels to a respective one of the processing nodes of the computer system.   
   
   
       13 . A system according to  claim 8 , wherein:
 said one of the processing nodes performs said series of calculations at a first time for the particles in said each voxel; and further comprising:   means for broadcasting the positions of at least some of the particles to a set of said processing nodes; and wherein one of said set of processing nodes performs said series of calculations at a second time.   
   
   
       14 . A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for creating a load balanced spatial partitioning of a structured, diffusing system of particles, and for use with a computer system having a plurality of processing nodes, said method steps comprising:
 assigning computational weights to the particles;   separating said system of particles, based on the computational weights assigned to the particles, into a number of voxels;   mapping each voxel to one of the processing nodes of the computer system; and   for each voxel, using said one of the processing nodes, to which said each voxel is mapped, to perform a series of calculations for the particles in said each voxel.   
   
   
       15 . A program storage device according to  claim 14 , wherein:
 the step of assigning computational weights includes the step of assigning each of the computational weights to a position in said system; and   the separating step includes the step of separating said system of particles into said number of voxels based on the positions assigned to the computational weights.   
   
   
       16 . A program storage device according to  claim 15 , wherein the voxels have an approximately equal total of computational weights. 
   
   
       17 . A program storage device according to  claim 15 , wherein:
 each computational weight is associated with a pair of the particles; and   the step of assigning each of the computational weights to a position includes the step of assigning each computational weight to a position between the pair of particles with which said each computational weight is associated.   
   
   
       18 . A program storage device according to  claim 14 , wherein:
 the computer system has a given number of said processing nodes;   said given number of voxels equals said given number; and   the mapping step includes the step of mapping each of the voxels to a respective one of the processing nodes of the computer system.   
   
   
       19 . A program storage device according to  claim 14 , wherein:
 the using step includes the step of using said one of the processing nodes to perform said series of calculations at a first time for the particles in said each voxel; and   said method steps comprise the further steps of, for each of at least some of the particles in the system:   broadcasting the position of the particle to a set of said processing nodes; and   using said one of said set of processing nodes to perform said calculations, at a second time.