《并行計(jì)算》課程復(fù)習(xí)

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