《并行計算》課程復習

并行計算》課程總結(jié)與復習2017/5/15第一篇并行計算硬件平臺：并行計算機Ch1并行計算與并行計算機結(jié)構(gòu)模型1.1計算與計算機科學1.2單處理機與指令級并行1.3多核處理器與線程級并行何謂多核處理器及意義微處理器中的并行方式ILP,TLP,多任務OS,SMT,CMP,虛擬化技術(shù)Intel超線程技術(shù)1.4并行計算機體系結(jié)構(gòu)并行計算機結(jié)構(gòu)模型SISD,SIMD,MISD,MIMD；SIMD,PVP,SMP,MPP,COW(Cluster),DSM并行計算機訪存模型UMA,NUMA,COMA,CC-NUMA,NORMA不同存儲結(jié)構(gòu)的并行機系統(tǒng)(P20圖1.11)1.5更多的并行計算概念PFLOPS,TFLOPS,GFLOPSTOP500中的Rmax和Rpeak指標Ch2并行計算機系統(tǒng)互連與基本通信操作2.1并行計算機互連網(wǎng)絡(luò)并行計算機的互連方式靜態(tài)互連：LA(LC),MC,TC,HC;(P42表2.1各種網(wǎng)絡(luò)特性表)動態(tài)互連：Bus,CrossbarSwitcher,MIN(MultistageInterconnectionNetworks)特別地，標準網(wǎng)絡(luò)互連：FDDI,快速以太網(wǎng),Myrinet,InfiniBand2.2-2.5通信代價公式SF和CT基本公式SF和CT在一維環(huán)、帶環(huán)繞的Mesh、超立方上的通信代價公式Ch3典型并行計算機系統(tǒng)介紹(略)3.1共享存儲多處理機系統(tǒng)3.2分布存儲多計算機系統(tǒng)3.3分布共享存儲計算機系統(tǒng)3.4機群系統(tǒng)Ch4并行計算性能評測4.1基本性能指標4.2加速比性能定律Amdahl,Gustafson,Sun&Ni定律4.3可擴放性評測標準（略）可擴放性的含義三個評測標準：等效率度量，等速度度量，平均延遲度量4.4基準測試程序（略）SPEC,LinPACK第二篇并行計算理論基礎(chǔ)：并行算法設(shè)計Ch5并行算法與并行計算模型5.1并行算法的基礎(chǔ)知識并行算法的定義并行算法的表達并行算法的復雜度：運行時間、處理器數(shù)目、成本及成本最優(yōu)、加速比、并行效率、工作量及工作量最優(yōu)并行算法的WT表示：Brent定理5.2并行計算模型PRAM模型：SIMD-SM，又分CRCW（CPRAM,PPRAM,APRAM）,CREW,EREWSIMD-IN模型：SIMD-DM異步APRAM模型：MIMD-SMBSP模型：MIMD-DM，塊內(nèi)異步并行，塊間顯式同步LogP模型：MIMD-DM，點到點通訊Ch6并行算法基本設(shè)計策略并行算法的三種設(shè)計策略：串改并，全新設(shè)計，借用法及其示例：快排序、前綴和/k著色、所有點對最短路徑Ch7并行算法常用設(shè)計技術(shù)劃分設(shè)計技術(shù)：均勻劃分（PSRS排序）、對數(shù)劃分（并行歸并排序）、方根戈扮（Valiant歸并排序）、功能劃分（（m,n）-選擇）分治設(shè)計技術(shù)：雙調(diào)歸并網(wǎng)絡(luò)平衡樹設(shè)計技術(shù)：求最大值、計算前綴和倍增設(shè)計技術(shù)：表序問題、求森林的根流水線技術(shù)：五點的DFT計算、4流水線編程實例Ch8并行算法一般設(shè)計過程PCAM的含義PCAM設(shè)計方法的四個階段和每個階段的任務與目標（略）域分解和功能分解（略）第三篇并行計算理論基礎(chǔ)：并行數(shù)值算法Ch9稠密矩陣運算9.1矩陣的劃分帶狀劃分和棋盤劃分，有循環(huán)的帶狀劃分和棋盤劃分9.2矩陣轉(zhuǎn)置網(wǎng)孔和超立方連接的算法及其時間分析（棋盤劃分）9.3矩陣向量乘法帶狀劃分的算法及其時間分析棋盤劃分的算法及其時間分析Systolic算法（略）9.4矩陣乘法簡單并行分塊算法Cannon算法及其計算示例Fox算法及其計算示例DNS算法及其計算示例（略）Systolic算法（略）Ch1。線性方程組的求解回代求解上三角形方程組的并行算法及其數(shù)據(jù)劃分方法三對角方程組的奇偶規(guī)約求解法Gauss-Seide迭代法的并行化異步并行化算法小規(guī)模并行化算法（針對五點格式產(chǎn)生的線性方程組）紅黑著色并行算法（針對五點格式產(chǎn)生的線性方程組）Ch11快速傅立葉變換FFT離散傅里葉變換（DFT）定義及其0（m2）算法串行FFT蝶式分治算法的計算原理、偽代碼及其遞歸計算流圖串行FFT分治遞歸算法的計算原理SIMD-MC上的FFT算法（略）SIMD-BF上的FFT算法及其時間分析Ch12數(shù)值計算的基本支撐技術(shù)（略）網(wǎng)格生成圖的劃分稀疏線性系統(tǒng)求解器算法和軟件科學計算可視化第四篇并行計算軟件支撐：并行編程Ch13并行程序設(shè)計基礎(chǔ)基本概念和術(shù)語Ch14共享存儲系統(tǒng)并行編程OpenMP編程Ch15分布存儲系統(tǒng)并行編程MPI編程Ch16并行程序設(shè)計環(huán)境與工具（略）Intel的ParallelStudio補充篇GPU體系結(jié)構(gòu)及編程術(shù)語：GPU,GPGPUNVIDIAG80的體系結(jié)構(gòu)SM的組成存儲器：層次結(jié)構(gòu)和特點，全局存儲器的coalescedmemor