CS 267: Applications of Parallel Computers Tree-Structured Codes for N-Body SimulationsMotivationOutlineParticle SimulationSlide 5Reducing the Number of Particles in the SumWhat is new: Using points at CM RecursivelyQuad TreesOct TreesUsing Quad Trees and Oct TreesExample of an Adaptive Quad TreeAdaptive Quad Tree AlgorithmCost of Adaptive QuadTree ConstructionBarnes-Hut AlgorithmStep 2: Compute CM and TM of Each NodeStep 3: Compute Force on Each ParticleComputing Force on a Particle Due to a NodeDetails of Step 3 of BHAnalysis of Step 3 of BHFast Multiple Method (FMM)Slide 21Gravitational/Electrostatic Potential2D Multipole (Taylor Expansion in 1/z)Summary of FMMParallelizing Hierachical N-Body CodesSlide 26Load Balancing 1: ORBLoad Balancing 2: CostzonesLinearly Ordering Nodes for CostzonesLinearly Ordering Nodes for CostzonesDetermining Costzones in ParallelComputing Locally Essential Trees (LETs)Locally Essential Trees in Distributed MemoryApplications of Fast N-Body AlgorithmsPerformance Results - 1Performance Results - 2Alternate Approach: Hardware01/14/19 CS267, Yelick 1CS 267: Applications of Parallel ComputersTree-Structured Codes for N-Body SimulationsKathy Yelickhttp://www.cs.berkeley.edu/~yelick/cs26701/14/19 CS267, Yelick 2Motivation•Particle methods are used for a variety of applications•Astrophysics•The particles are stars or galaxies•The force is gravity•Particle physics•The particles are ions, electrons, etc.•The force is due to Coulomb’s Law•Molecular dynamics•The particles are atoms or •The forces is electrostatic•Vortex methods in fluid dynamics•Particles are blobs of fluid01/14/19 CS267, Yelick 3Outline•Motivation•Obvious algorithm on N bodies takes O(N2) work•How to reduce the number of particles in the force sum•We must settle for an approximate answer (say 2 decimal digits, or perhaps 16 …)•Basic Data Structures: Quad Trees and Oct Trees•The Barnes-Hut Algorithm (BH)•An O(N log N) approximate algorithm for the N-Body problem•The Fast Multipole Method (FMM)•An O(N) approximate algorithm for the N-Body problem•Parallelizing BH, FMM and other algorithms•Example applications•Alternative approach: lots of hardware01/14/19 CS267, Yelick 4Particle Simulation•Let f(i) be the force on particle i•f(i) = external_force + nearest_neighbor_force + NBody_forcet = 0while t < t_final for i = 1 to n … n = number of particles compute f(i) = force on particle i for i = 1 to n move particle i under force f(i) for time dt … using F=ma compute interesting properties of particles (energy, etc.) t = t + dtend while01/14/19 CS267, Yelick 5Particle Simulationf(i) = external_force + nearest_neighbor_force + NBody_force•External_force (e.g., current) is usually embarrassingly parallel, O(N) •Nearest_neighbor_force is with a few neighbors, so still O(N)•N-Body_force (gravity or electrostatics) requires all-to-all interactions•f(i) = k!=i f(i,k) … f(i,k) = force on i from k •f(i,k) = c*v/||v||3 in 3 dimensions or •f(i,k) = c*v/||v||2 in 2 dimensions •c = product of masses or charges and appropriate constants•v = vector from particle i to particle k, ||v|| = length of v •Obvious algorithm costs O(N2), but we can do better...01/14/19 CS267, Yelick 6Reducing the Number of Particles in the Sum•Previous divide and conquer algorithms use same intuition•Consider computing force on earth due to all celestial bodies•Look at night sky, # terms in force sum >= number of visible stars•One “star” is really the Andromeda galaxy, which is billions of stars•A lot of work if we compute this per star … •OK to approximate all stars in Andromeda by a single point at its center of mass (CM) with same total mass•D = size of box containing Andromeda , r = distance of CM to Earth•Require that D/r be “small enough”•Idea not new: Newton approximated earth and falling apple by CMsEarthr = distance to center of massx = location of center of massAndromedaDDrx01/14/19 CS267, Yelick 7What is new: Using points at CM Recursively•From Andromeda’s point of view, Milky Way is also a point mass•Within Andromeda, picture repeats itself•As long as D1/r1 is small enough, stars inside smaller box can be replaced by their CM to compute the force on Vulcan•Boxes nest in boxes recursivelyEarthAndromedaDDrxVulcanD1D1Replacing clusters by their Centers of Mass Recursivelyr101/14/19 CS267, Yelick 8Quad Trees•Data structure to subdivide the plane•Nodes can contain coordinates of center of box, side length•Eventually also coordinates of CM, total mass, etc.•In a complete quad tree, each nonleaf node has 4 children01/14/19 CS267, Yelick 9Oct Trees•Similar Data Structure to subdivide 3D space•Analogous to 2D Quad tree--each cube is divided into 8 sub-cubesTwo Levels of an OctTree01/14/19 CS267, Yelick 10Using Quad Trees and Oct Trees•All our algorithms begin by constructing a tree to hold all the particles•Interesting cases have non-uniform particle distribution•In a complete tree (full at lowest level), most nodes would be empty, a waste of space and time•Adaptive Quad (Oct) Tree only subdivides space where particles are located •More compact and efficient computationally, but harder to program01/14/19 CS267, Yelick 11Example of an Adaptive Quad TreeChild nodes enumerated counterclockwise from SW cornerEmpty ones excludedAdaptive quad tree where no space contains more than 1 particle01/14/19 CS267, Yelick 12Adaptive Quad Tree Algorithmclass QuadTree build (particles) QuadTree t = new QuadTree(); for each j in particles t.insert(j) … loop over all N particles t.insert(j) … insert particle j in QuadTree end build insert(j) … Try to insert particle j at node n in QuadTree if this node is empty … empty add j as the (only) particle in this node if this is an internal node (has 4 children) … internal determine which child c contains particle j c.insert(j) else (this quadtree contains 1 particle) … leaf add n’s 4 children to the QuadTree let c be the child of the particle k already here c.insert(k) let c be the child of n containing j c.insert(j) end insert01/14/19 CS267, Yelick 13Cost of Adaptive QuadTree ConstructionCost <= N * maximum cost of QuadTreeInsert = O(N * maximum depth of QuadTree)1. Uniform distribution => depth of QuadTree = O(log N), so Cost = O( N log N)2. Arbitrary
View Full Document
Unlocking...