Finite-Difference-Method課件

1、Parallel Programmingin C with MPI and OpenMPMichael J. QuinnChapter 13Finite Difference MethodsOutlineOrdinary and partial differential equationsFinite difference methodsVibrating string problemSteady state heat distribution problemOrdinary and Partial Differential EquationsOrdinary differential equ

2、ation: equation containing derivatives of a function of one variablePartial differential equation: equation containing derivatives of a function of two or more variablesExamples of Phenomena Modeled by PDEsAir flow over an aircraft wingBlood circulation in human bodyWater circulation in an oceanBrid

3、ge deformations as its carries trafficEvolution of a thunderstormOscillations of a skyscraper hit by earthquakeStrength of a toyModel of Sea Surface Temperaturein Atlantic OceanCourtesy MICOM groupat the Rosenstiel Schoolof Marine and AtmosphericScience, University of MiamiSolving PDEsFinite element

4、 methodFinite difference method (our focus)Converts PDE into matrix equationResult is usually a sparse matrixMatrix-based algorithms represent matrices explicitlyMatrix-free algorithms represent matrix values implicitly (our focus)Linear Second-order PDEsLinear second-order PDEs are of the formwhere

5、 A - H are functions of x and y onlyElliptic PDEs: B2 - AC 0Difference QuotientsFormulas for 1st, 2d DerivativesVibrating String ProblemVibrating string modeled by a hyperbolic PDESolution Stored in 2-D MatrixEach row represents state of string at some point in timeEach column shows how position of

6、string at a particular point changes with timeDiscrete Space, Time Intervals Lead to 2-D MatrixHeart of Sequential C Programuj+1i = 2.0*(1.0-L)*uji + L*(uji+1 + uji-1) - uj-1i;Parallel Program DesignAssociate primitive task with each element of matrixExamine communication patternAgglomerate tasks in

7、 same columnStatic number of identical tasksRegular communication patternStrategy: agglomerate columns, assign one block of columns to each taskResult of Agglomeration and MappingCommunication Still NeededInitial values (in lowest row) are computed without communicationValues in black cells cannot b

8、e computed without access to values held by other tasksGhost PointsGhost points: memory locations used to store redundant copies of data held by neighboring processesAllocating ghost points as extra columns simplifies parallel algorithm by allowing same loop to update all cellsMatrices Augmentedwith

9、 Ghost PointsLilac cells are the ghost points.Communication in an IterationThis iteration the process is responsible forcomputing the values of the yellow cells.Computation in an IterationThis iteration the process is responsible forcomputing the values of the yellow cells.The striped cells are the

10、ones accessed asthe yellow cell values are computed.Complexity AnalysisComputation time per element is constant, so sequential time complexity per iteration is (n)Elements divided evenly among processes, so parallel computational complexity per iteration is (n / p)During each iteration a process wit

11、h an interior block sends two messages and receives two messages, so communication complexity per iteration is (1)Isoefficiency AnalysisSequential time complexity: (n)Parallel overhead: (p)Isoefficiency relation:n CpTo maintain the same level of efficiency, n must increase at the same rate as pIf M(

12、n) = n2, algorithm has poor scalabilityIf matrix of 3 rows rather than m rows is used, M(n) = n and system is perfectly scalableReplicating ComputationsIf only one value transmitted, communication time dominated by message latencyWe can reduce number of communications by replicating computationsIf w

13、e send two values instead of one, we can advance simulation two time steps before another communicationReplicating ComputationsWithout replication:With replication:Communication Time vs. Number of Ghost PointsSteady State Heat Distribution ProblemSteamSteamSteamIce bathSolving the ProblemUnderlying

14、PDE is the Poisson equationThis is an example of an elliptical PDEWill create a 2-D gridEach grid point represents value of state state solution at particular (x, y) location in plateHeart of Sequential C Programwij = (ui-1j + ui+1j + uij-1 + uij+1) / 4.0;Parallel Algorithm 1Associate primitive task

15、 with each matrix elementAgglomerate tasks in contiguous rows (rowwise block striped decomposition)Add rows of ghost points above and below rectangular region controlled by processExample Decomposition16 16 griddivided among 4 processorsComplexity AnalysisSequential time complexity:(n2) each iterati

16、onParallel computational complexity: (n2 / p) each iterationParallel communication complexity: (n) each iteration (two sends and two receives of n elements)Isoefficiency AnalysisSequential time complexity: (n2) Parallel overhead: (pn) Isoefficiency relation:n2 Cnp n CpThis implementation has poor sc

17、alabilityParallel Algorithm 2Associate primitive task with each matrix elementAgglomerate tasks into blocks that are as square as possible (checkerboard block decomposition)Add rows of ghost points to all four sides of rectangular region controlled by processExample Decomposition16 16 griddivided am

18、ong16 processorsImplementation DetailsUsing ghost points around 2-D blocks requires extra copying stepsGhost points for left and right sides are not in contiguous memory locationsAn auxiliary buffer must be used when receiving these ghost point valuesSimilarly, buffer must be used when sending colum

19、n of values to a neighboring processComplexity AnalysisSequential time complexity:(n2) each iterationParallel computational complexity: (n2 / p) each iterationParallel communication complexity: (n /p ) each iteration (four sends and four receives of n /p elements each)Isoefficiency AnalysisSequentia

20、l time complexity: (n2) Parallel overhead: (n p ) Isoefficiency relation:n2 Cn p n C pThis system is perfectly scalableSummary (1/4)PDEs used to model behavior of a wide variety of physical systemsRealistic problems yield PDEs too difficult to solve analytically, so scientists solve them numericallyTwo most common numerical techniques for solving PDEsfinite element methodfinite difference