




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
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. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 班主任關(guān)于學(xué)習(xí)習(xí)慣的指導(dǎo)計劃
- 生物學(xué)觀察與記錄技巧計劃
- 藥學(xué)部臨床溝通能力提升計劃
- 2025年地面瞄準(zhǔn)設(shè)備、定位定向設(shè)備項目合作計劃書
- 中國開源軟件行業(yè)發(fā)展環(huán)境、市場運行格局及投資前景研究報告(2025版)
- 2025年微循環(huán)測試系統(tǒng)項目合作計劃書
- 2025年動葉可調(diào)軸流電站用風(fēng)機合作協(xié)議書
- 2025年磁共振成像裝置合作協(xié)議書
- 2025年油氣鉆采服務(wù)合作協(xié)議書
- 珠寶行業(yè)商品質(zhì)量免責(zé)合同
- 農(nóng)產(chǎn)品質(zhì)量安全及其檢測技術(shù)課件
- 外科學(xué)緒論課件
- 2020年中國人身保險產(chǎn)品研究報告
- 安全生產(chǎn)目標(biāo)責(zé)任制考核表
- 常見織帶花鏈的排法和穿棕方法
- 《化工工程制圖》完整教案
- 2023年廣東省中考試卷(語數(shù)英物化史生等共11套)帶答案解析
- DFX工藝設(shè)計方法介紹
- 洪恩識字識字卡(001-100)可直接打印剪裁
- 違反八項規(guī)定問題典型案例、法規(guī)依據(jù)和關(guān)注點
- J-STD-033D處理包裝運輸和使用濕度回流和過程敏感設(shè)備
評論
0/150
提交評論