CS 267 Applications of Parallel Computers Lecture 12: Sources of Parallelism and Locality (Part 3) Tricks with TreesRecap of last lectureOutlineSlide 4Poisson’s equation in 1DPoisson’s equation in 2DAlgorithms for 2D Poisson Equation with N unknownsRelation of Poisson’s equation to Gravity, ElectrostaticsComments on practical meshesComposite mesh for a mechanical structureConverting the mesh to a matrixEffects of Ordering Rows and Columns on Gaussian EliminationIrregular mesh: NASA Airfoil in 2D (direct solution)Irregular mesh: Tapered Tube (multigrid)Adaptive Mesh Refinement (AMR)Challenges of irregular meshes (and a few solutions)CS267 L12 Sources of Parallelism(3).1Demmel Sp 1999CS 267 Applications of Parallel ComputersLecture 12: Sources of Parallelism and Locality(Part 3)Tricks with TreesJames Demmelhttp://www.cs.berkeley.edu/~demmel/cs267_Spr99CS267 L12 Sources of Parallelism(3).2Demmel Sp 1999Recap of last lecture°ODEs•Sparse Matrix-vector multiplication•Graph partitioning to balance load and minimize communication°PDEs•Heat Equation and Poisson Equation•Solving a certain special linear system T•Many algorithms, ranging from-Dense Gaussian elimination, slow but very general, to-Multigrid, fast but only works on matrices like TCS267 L12 Sources of Parallelism(3).3Demmel Sp 1999Outline°Continuation of PDEs•What do realistic meshes look like?°Tricks with TreesCS267 L12 Sources of Parallelism(3).4Demmel Sp 1999Partial Differential EquationsPDEsCS267 L12 Sources of Parallelism(3).5Demmel Sp 1999Poisson’s equation in 1D°Solve Tx=b where2 -1 -1 2 -1 -1 2 -1 -1 2 -1 -1 2T =2-1 -1Graph and “stencil”CS267 L12 Sources of Parallelism(3).6Demmel Sp 1999Poisson’s equation in 2D°Solve Tx=b where°3D is analogous4 -1 -1-1 4 -1 -1 -1 4 -1 -1 4 -1 -1 -1 -1 4 -1 -1 -1 -1 4 -1 -1 4 -1 -1 -1 4 -1 -1 -1 4T =4-1-1-1-1Graph and “stencil”CS267 L12 Sources of Parallelism(3).7Demmel Sp 1999Algorithms for 2D Poisson Equation with N unknownsAlgorithm Serial PRAM Memory #Procs°Dense LU N3N N2N2°Band LU N2N N3/2N°Jacobi N2 N N N°Explicit Inv. N log N N N°Conj.Grad. N 3/2N 1/2 *log N N N°RB SOR N 3/2N 1/2N N°Sparse LU N 3/2N 1/2N*log N N°FFT N*log N log N N N°Multigrid N log2 N N N°Lower bound N log N NPRAM is an idealized parallel model with zero cost communication (see next slide for explanation)2 22CS267 L12 Sources of Parallelism(3).8Demmel Sp 1999Relation of Poisson’s equation to Gravity, Electrostatics°Force on particle at (x,y,z) due to particle at 0 is -(x,y,z)/r^3, where r = sqrt(x +y +z )°Force is also gradient of potential V = -1/r = -(d/dx V, d/dy V, d/dz V) = -grad V°V satisfies Poisson’s equation (try it!)2 2 2CS267 L12 Sources of Parallelism(3).9Demmel Sp 1999Comments on practical meshes°Regular 1D, 2D, 3D meshes•Important as building blocks for more complicated meshes°Practical meshes are often irregular•Composite meshes, consisting of multiple “bent” regular meshes joined at edges•Unstructured meshes, with arbitrary mesh points and connectivities•Adaptive meshes, which change resolution during solution process to put computational effort where neededCS267 L12 Sources of Parallelism(3).10Demmel Sp 1999Composite mesh for a mechanical structureCS267 L12 Sources of Parallelism(3).11Demmel Sp 1999Converting the mesh to a matrixCS267 L12 Sources of Parallelism(3).12Demmel Sp 1999Effects of Ordering Rows and Columns on Gaussian EliminationCS267 L12 Sources of Parallelism(3).13Demmel Sp 1999Irregular mesh: NASA Airfoil in 2D (direct solution)CS267 L12 Sources of Parallelism(3).14Demmel Sp 1999Irregular mesh: Tapered Tube (multigrid)CS267 L12 Sources of Parallelism(3).15Demmel Sp 1999Adaptive Mesh Refinement (AMR)°Adaptive mesh around an explosion°John Bell and Phil Colella at LBL (see class web page for URL)°Goal of Titanium is to make these algorithms easier to implementin parallelCS267 L12 Sources of Parallelism(3).16Demmel Sp 1999Challenges of irregular meshes (and a few solutions)°How to generate them in the first place•Triangle, a 2D mesh partitioner by Jonathan Shewchuk°How to partition them•ParMetis, a parallel graph partitioner°How to design iterative solvers•PETSc, a Portable Extensible Toolkit for Scientific Computing•Prometheus, a multigrid solver for finite element problems on irregular meshes•Titanium, a language to implement Adaptive Mesh Refinement°How to design direct solvers•SuperLU, parallel sparse Gaussian elimination°These are challenges to do sequentially, the more so in
View Full Document
Unlocking...