Finite Difference Methods参考.ppt

Parallel Programmingin C with MPI and OpenMP Michael J. Quinn Chapter 13 Finite Difference Methods Outline Ordinary and partial differential equations Finite difference methods Vibrating string problem Steady state heat distribution problem Ordinary and Partial Differential Equations Ordinary differential equation: equation containing derivatives of a function of one variable Partial differential equation: equation containing derivatives of a function of two or more variables Examples of Phenomena Modeled by PDEs Air flow over an aircraft wing Blood circulation in human body Water circulation in an ocean Bridge deformations as its carries traffic Evolution of a thunderstorm Oscillations of a skyscraper hit by earthquake Strength of a toy Model of Sea Surface Temperaturein Atlantic Ocean Solving PDEs Finite element method Finite difference method (our focus) Converts PDE into matrix equation Result is usually a sparse matrix Matrix-based algorithms represent matrices explicitly Matrix-free algorithms represent matrix values implicitly (our focus) Linear Second-order PDEs Linear second-order PDEs are of the form where A - H are functions of x and y only Elliptic PDEs: B2 - AC 0 Parabolic PDEs: B2 - AC = 0 Hyperbolic PDEs: B2 - AC 0 Difference Quotients Formulas for 1st, 2d Derivatives Vibrating String Problem Solution Stored in 2-D Matrix Each row represents state of string at some point in time Each column shows how position of string at a particular point changes with time Discrete Space, Time Intervals Lead to 2-D Matrix Heart of Sequential C Program Parallel Program Design Associate primitive task with each element of matrix Examine communication pattern Agglomerate tasks in same column Static number of identical tasks Regular communication pattern Strategy: agglomerate columns, assign one block of columns to each task Result of Agglomeration and Mapping Communication Still Needed Initial values (in lowest row) are computed without communication Values in bl