Load balancing by spatial partitioning of interaction centers

Abstract

A method for creating a load balanced spatial partitioning of a structured, diffusing system of particles with pairwise interactions, comprises steps of: assigning a weight corresponding to a computational cost for a pair interaction of particles to a simulation space distance between the particles; performing a spatial partitioning of the simulation space; and assigning computation of pair interaction to any node that has the positions of both particles. The method can also be implemented as machine executable instructions executed by a programmable information processing system or as hard coded logic in a specialized computing apparatus such as an application-specific integrated circuit (ASIC).

1 . A method for assigning a pairwise fragment interaction computation to a processing network comprising a plurality of processor nodes, the method comprising: 
 defining a simulation space comprising a plurality of fragments and the plurality of processor nodes;    determining a weight corresponding to the computational cost for a given pairwise fragment interaction computation;    assigning the weight to the simulation space at a point between the two interacting fragments;    performing a spatial partitioning of the volume of the simulation space such that all partitions have substantially the same weight;    determining which nodes have the positions of both of the interacting fragments; and    assigning the pairwise fragment interaction computation to any node that has the positions of both fragment.    
   
   
       2 . The method of  claim 1 , wherein the step of performing a spatial partitioning comprises using a k-d tree on the simulation space.  
   
   
       3 . The method of  claim 1 , wherein the step of performing a spatial partitioning comprises using an optimal recursive bisection of the simulation space.  
   
   
       4 . The method of  claim 3 , wherein the step of assigning a weight comprises assigning a weight to the midpoint between the pair of fragments.  
   
   
       5 . The method of  claim 1 , wherein each of the fragments comprises a single particle.  
   
   
       6 . The method of  claim 1 , wherein each of the fragments comprises a cluster of particles.  
   
   
       7 . The method of  claim 1  further comprising cutting off each pair interaction beyond a defined radius.  
   
   
       8 . The method of  claim 7  further comprising broadcasting the position of a particle to a group of nodes containing a portion of a sphere having a radius R b  that is greater than R c /2, where R c  is the defined radius to ensure the existence of at least one node containing the positions of both particles required to compute any interaction.  
   
   
       9 . The method of  claim 8  wherein when more than one node contains the positions required to compute a particle interaction, the computation is assigned to any of those nodes, providing an opportunity for eliminating imbalances caused by short term local fluctuations in interaction workload.  
   
   
       10 . An information processing system comprising: 
 a processor configured for:    defining a simulation space comprising a plurality of fragments and a plurality of processor nodes;    determining a weight corresponding to the computational cost for a given pair interaction of fragments;    assigning the weight to the simulation space at a point between the two interacting fragments;    performing a spatial partitioning of the volume of the simulation space such that all partitions have substantially the same weight; and    assigning a computation of the fragment pair interaction to any node that has the positions of both groups of fragments.    
   
   
       11 . The system of  claim 10  wherein the processor is further configured for performing a spatial partitioning using a k-d tree on the simulation space.  
   
   
       12 . The system of  claim 10  wherein the processor is further configured for performing a spatial partitioning using an optimal recursive bisection of the simulation space.  
   
   
       13 . The system of  claim 10  wherein the processor is further configured for assigning a weight to the centers of the groups of fragments.  
   
   
       14 . The system of  claim 10  wherein each of the fragments comprises a single particle.  
   
   
       15 . The system of  claim 10  wherein each of the fragments comprises a cluster of particles.  
   
   
       16 . The system of  claim 10  wherein the processor is further configured for cutting off each pair interaction beyond a defined radius.  
   
   
       17 . The system of  claim 10  wherein the processor is further configured for broadcasting the position of a particle to a group of nodes containing a portion of a sphere having a radius Rb that is greater than Rc/2, where Rc is the defined radius to ensure the existence of at least one node containing the positions of both particles required to compute any interaction.  
   
   
       18 . The system of  claim 10  wherein the processor is further configured for when more than one node contains the positions required to compute a particle interaction, the computation is assigned to any of those nodes, providing an opportunity for eliminating imbalances caused by short term local fluctuations in interaction workload.  
   
   
       19 . A computer readable medium comprising program instructions for: 
 defining a simulation space comprising a plurality of groups of particles and the plurality of processor nodes;    determining a weight corresponding to the computational cost for a given pair interaction of groups of particles;    assigning the weight to the simulation space at a point between the two interacting groups of particles;    performing a spatial partitioning of the volume of the simulation space such that all partitions have substantially the same weight; and    assigning a computation of the pair interaction to any node that has the positions of both groups of particles.    
   
   
       20 . A method for creating a load balanced spatial partitioning of a structured, diffusing system of particles with pairwise interactions, comprising steps of: 
 assigning a weight corresponding to a computational cost for a pair interaction of particles to a simulation space distance between the particles;    performing a spatial partitioning of the simulation space; and    assigning computation of pair interaction to any node that has the positions of both particles.