




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 音乐说课课件资源获取
- 油田开发项目经济效益和社会效益分析报告
- xx片区城乡供水一体化项目数字化方案(参考模板)
- 乡村治理结构优化实施方案
- 2025年油气钻采服务项目建议书
- 挖掘优势-树立科学就业观
- 2025年房地产市场区域分化与产业升级关系及投资策略分析报告
- 工业互联网平台数据清洗算法在工业物联网中的应用场景对比报告
- 探讨游戏化教学法在幼儿教育中的应用研究
- 医疗器械注册审批制度改革背景下2025年行业竞争格局与市场趋势分析
- 2025年食品检验员考试试卷及答案
- 四川省德阳市2025年七年级下学期语文期末试卷及答案
- 黎族文化课件
- 中华人民共和国民营经济促进法
- 色彩的魅力:艺术、科学与设计的交融
- 2025广州市荔湾区辅警考试试卷真题
- 一季度安委会汇报材料
- 贵州省遵义市2024年八年级《数学》上学期期末试题与参考答案
- 产品质量问题追溯制度
- TACE围手术期的护理
- GB/T 320-2025工业用合成盐酸
评论
0/150
提交评论