CS 267 Applications of Parallel Computers Hierarchical Methods for the N-Body problemBig IdeaOutlineParticle SimulationMotif/Dwarf: Common Computational Methods (Red Hot Blue Cool)ApplicationsReducing the number of particles in the force sumWhat is new: Using points at CM recursivelySlide 9Quad TreesOct TreesUsing Quad Trees and Oct TreesExample of an Adaptive Quad TreeAdaptive Quad Tree Algorithm (Oct Tree analogous)Cost of Adaptive Quad Tree ConstrutionSlide 16Barnes-Hut AlgorithmStep 2 of BH: compute CM and total mass of each nodeStep 3 of BH: compute force on each particleComputing force on a particle due to a nodeDetails of Step 3 of BHAnalysis of Step 3 of BHSlide 23Fast Multiple Method (FMM)Gravitational/Electrostatic Potential2D Multipole Expansion (Taylor expansion in 1/z) (1/2)2D Multipole Expansion (Taylor expansion in 1/z) (2/2)Error in Truncated 2D Multipole ExpansionOuter(n) and Outer ExpansionInner(n) and Inner ExpansionTop Level Description of FMMStep 2 of FMM: Outer_shift: converting Outer(n1) to Outer(n2)Outer_shift: continuedStep 2 of FMM: compute Outer(n) for each node n in QuadTreeSlide 35Step 3 of FMM: Compute Inner(n) for each n in QuadTreeStep 3 of FMM: Inner(n1) = Inner_shift(Inner(n2), n1)Step 3 of FMM: Inner(n4) = Convert(Outer(n3), n4)Step 3 of FMM: Computing Inner(n) from other expansionsStep 3 of FMM: Interaction SetStep 3 of FMM: Compute Inner(n) for each n in QuadTreeSlide 42Slide 43Parallelizing Hierachical N-Body codesProgramming Model - BSPLoad Balancing Scheme 1: Orthogonal Recursive Bisection (ORB)Load Balancing Scheme 2: CostzonesLinearly Ordering Quadtree nodes for Costzones (1/2)Linearly Ordering Quadtree nodes for Costzones (2/2)Determining Costzones in ParallelComputing Locally Essential Trees (LETs)Locally Essential Trees in Distributed MemoryPerformance Results - 1Performance Results - 2Old SlidesSlide 56Slide 572D Multipole Expansion (Taylor expansion in 1/z)Slide 59Slide 60Outer_shift: converting Outer(n1) to Outer(n2)Slide 62FMM: compute Outer(n) for each node n in QuadTreeSlide 64Summary of FMMSlide 6604/20/2009 CS267 Lecture 22CS 267 Applications of Parallel ComputersHierarchical Methods for the N-Body problemJames Demmelwww.cs.berkeley.edu/~demmel/cs267_Spr0904/20/2009 CS267 Lecture 22Big Idea°Suppose the answer at each point depends on data at all the other points•Electrostatic, gravitational force•Solution of elliptic PDEs•Graph partitioning°Seems to require at least O(n2) work, communication°If the dependence on “distant” data can be compressed•Because it gets smaller, smoother, simpler…°Then by compressing data of groups of nearby points, can cut cost (work, communication) at distant points•Apply idea recursively: cost drops to O(n log n) or even O(n)°Examples:•Barnes-Hut or Fast Multipole Method (FMM) for electrostatics/gravity/…•Multigrid for elliptic PDE•Multilevel graph partitioning (METIS, Chaco,…)04/20/2009 CS267 Lecture 22Outline°Motivation•Obvious algorithm for computing gravitational or electrostatic force 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 related algorithms04/20/2009 CS267 Lecture 22Particle Simulation°f(i) = external_force + nearest_neighbor_force + N-Body_force•External_force is usually embarrassingly parallel and costs O(N) for all particles-external current in Sharks and Fish•Nearest_neighbor_force requires interacting with a few neighbors, so still O(N)-van der Waals, bouncing balls•N-Body_force (gravity or electrostatics) requires all-to-all interactions-f(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 –v = vector from particle i to particle k , c = product of masses or charges–||v|| = length of v -Obvious algorithm costs O(n2), but we can do better...t = 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 whilek ≠ iMotif/Dwarf: Common Computational Methods(Red Hot Blue Cool)EmbedSPECDBGamesMLHPCHealth Image Speech MusicBrowser1 Finite State Mach.2 Combinational3 Graph Traversal4 Structured Grid5 Dense Matrix6 Sparse Matrix7 Spectral (FFT)8 Dynamic Prog9 N-Body10 MapReduce11 Backtrack/ B&B12 Graphical Models13 Unstructured GridWhat do commercial and CSE applications have in common?04/20/2009 CS267 Lecture 2204/20/2009 CS267 Lecture 22Applications°Astrophysics and Celestial Mechanics•Intel Delta = 1992 supercomputer, 512 Intel i860s•17 million particles, 600 time steps, 24 hours elapsed time–M. Warren and J. Salmon–Gordon Bell Prize at Supercomputing 92•Sustained 5.2 Gflops = 44K Flops/particle/time step•1% accuracy•Direct method (17 Flops/particle/time step) at 5.2 Gflops would have taken 18 years, 6570 times longer°Plasma Simulation°Molecular Dynamics°Electron-Beam Lithography Device Simulation°Fluid Dynamics (vortex method)°Good sequential algorithms too!04/20/2009 CS267 Lecture 22Reducing the number of particles in the force sum°All later 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•Oops! One “star” is really the Andromeda galaxy, which contains billions of real stars-Seems like a lot more work than we thought … °Don’t worry, ok to approximate all stars in Andromeda by a single point at its center of mass (CM) with same total mass (TM)•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 CMs04/20/2009 CS267 Lecture 22What 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
View Full Document
Unlocking...