Method of creating a load balanced spatial partitioning of a structured, diffusing system of particles
US7860695B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 15, 2008 |
| Grant date | Dec 28, 2010 |
| Priority date | — |
| Expiry date | Jul 15, 2028 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG16C10/00
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and system are disclosed 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, a weight is assigned 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. A spatial partitioning of the simulation volume is then carried out using a k-d tree or optimal recursive bisection (ORB) to divide the volume into sections that have approximately equal total weights.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.