CS 267 Applications of Parallel Computers Solving Linear Systems arising from PDEs - IOutlineRecap of “Sources of Parallelism” LectureContinuation of RecapSolving PDEsPoisson’s equation arises in many modelsRelation of Poisson’s equation to Gravity, ElectrostaticsPoisson’s equation in 1D: 2u/x2 = f(x)2D Poisson’s equation: 2u/x2 + 2u/y2 = f(x,y)Algorithms for 2D Poisson Equation with N unknownsShort explanations of algorithms on previous slideComments on practical meshesComposite mesh from a mechanical structureConverting the mesh to a matrixIrregular mesh: NASA Airfoil in 2D (direct solution)Irregular mesh: Tapered Tube (multigrid)Adaptive Mesh Refinement (AMR)Jacobi’s Method on Regular 2D MeshConvergence of Nearest Neighbor MethodsSlide 21Parallelizing Jacobi’s MethodLocality Optimization in JacobiRedundant Ghost Nodes in JacobiSuccessive Overrelaxation (SOR)Gauss-SeidelSlide 27Conjugate Gradient (CG) for solving A*x = bSummary of Jacobi, SOR and CGSolving the Poisson equation with the FFTSerial FFTUsing the 1D FFT for filteringUsing the 2D FFT for image compressionRelated TransformsSerial Algorithm for the FFTDivide and Conquer FFTDivide-and-Conquer FFTAn Iterative AlgorithmParallel 1D FFTBlock Layout of 1D FFTCyclic Layout of 1D FFTParallel ComplexityFFT With “Transpose”Why is the Communication Step Called a Transpose?Complexity of the FFT with TransposeComment on the 1D Parallel FFTHigher Dimension FFTsFFTW – Fastest Fourier Transform in the WestCS267 Poisson - 1.1Demmel Fall 2002CS 267 Applications of Parallel ComputersSolving Linear Systems arising from PDEs - IJames Demmelwww.cs.berkeley.edu/~demmel/CS267_2002_Poisson_1CS267 Poisson - 1.2Demmel Fall 2002Outline°Review Poisson equation°Overview of Methods for Poisson Equation°Jacobi’s method°Red-Black SOR method°Conjugate Gradients°FFT°Multigrid (next lecture)Reduce to sparse-matrix-vector multiplyNeed them to understand MultigridCS267 Poisson - 1.3Demmel Fall 2002Recap of “Sources of Parallelism” Lecture°Discrete event systems:•Examples: “Game of Life,” logic level circuit simulation. °Particle systems:•Examples: billiard balls, semiconductor device simulation, galaxies.°Lumped variables depending on continuous parameters:•ODEs, e.g., circuit simulation (Spice), structural mechanics, chemical kinetics.°Continuous variables depending on continuous parameters:•PDEs, e.g., heat, elasticity, electrostatics.°A given phenomenon can be modeled at multiple levels.°Many simulations combine more than one of these techniques.CS267 Poisson - 1.4Demmel Fall 2002Continuation of RecapExamples of PDE systems include°Hyperbolic problems (waves):•Quantum mechanics: Wave-function(position,time)°Elliptic (steady state) problems:•Electrostatic or Gravitational Potential: Potential(position)°Parabolic (time-dependent) problems:•Heat flow: Temperature(position, time)•Diffusion: Concentration(position, time)Many problems combine features of above°Fluid flow: Velocity,Pressure,Density(position,time)°Elasticity: Stress,Strain(position,time)CS267 Poisson - 1.6Demmel Fall 2002Solving PDEsSolution strategies:°Hyperbolic problems (waves):•Use explicit time-stepping •Solution at each point depends on neighbors at previous time°Elliptic (steady state) problems:•Everything depends on everything else•This means locality is harder to find than in hyperbolic problems°Parabolic (time-dependent) problems:•Involves an elliptic solve at each time-step°Focus on elliptic problems•Canonical example is the Poisson equation2u/x2 + 2u/y2 + 2u/z2 = f(x,y,z)CS267 Poisson - 1.7Demmel Fall 2002Poisson’s equation arises in many models°Heat flow: Temperature(position, time)°Diffusion: Concentration(position, time)°Electrostatic or Gravitational Potential: Potential(position)°Fluid flow: Velocity,Pressure,Density(position,time)°Quantum mechanics: Wave-function(position,time)°Elasticity: Stress,Strain(position,time)3D: 2u/x2 + 2u/y2 + 2u/z2 = f(x,y,z)2D: 2u/x2 + 2u/y2 = f(x,y)1D: 2u/x2 = f(x)CS267 Poisson - 1.8Demmel Fall 2002Relation 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(x,y,z) = -1/r = -(d/dx V, d/dy V, d/dz V) = -grad V°V(x,y,z) satisfies Poisson’s equation (try it!)2 2 2CS267 Poisson - 1.9Demmel Fall 2002Poisson’s equation in 1D: 2u/x2 = f(x)2 -1 -1 2 -1 -1 2 -1 -1 2 -1 -1 2T =2-1 -1Graph and “stencil”Discretize 2u/x2 = f(x) on regular mesh ui = u(i*h) to get [ u i+1 – 2*u i + u i-1 ] / h2 = f(x)Write as solving Tu = -h2 * f for u whereCS267 Poisson - 1.10Demmel Fall 20022D Poisson’s equation: 2u/x2 + 2u/y2 = f(x,y)°Similar to the 1D case, but the matrix T is now•Grid points numbered left to right, top row to bottom row°3D is analogous°Similar “adjacency matrix” for arbitrary graph4 -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 Poisson - 1.11Demmel Fall 2002Algorithms 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 communication2 22CS267 Poisson - 1.12Demmel Fall 2002Short explanations of algorithms on previous slide°Sorted in two orders (roughly):•from slowest to fastest on sequential machines•from most general (works on any matrix) to most specialized (works on matrices “like” Poisson)°Dense LU: Gaussian elimination; works on any N-by-N matrix°Band LU: exploit fact that T is nonzero only on sqrt(N) diagonals nearest main diagonal, so faster°Jacobi: essentially does matrix-vector multiply by T in inner loop
View Full Document
Unlocking...