并行計(jì)算多媒體課件并行算法設(shè)計(jì)與分析課程總結(jié)與復(fù)習(xí)

1、并行算法課程總結(jié)與復(fù)習(xí)Ch1 并行算法基礎(chǔ)1.1 并行計(jì)算機(jī)體系結(jié)構(gòu)并行計(jì)算機(jī)的分類SISD,SIMD,MISD,MIMD；SIMD,PVP,SMP,MPP,COW,DSM并行計(jì)算機(jī)的互連方式靜態(tài)：LA(LC),MC,TC,MT,HC,BC,SE動(dòng)態(tài)：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks)1.2 并行計(jì)算模型 PRAM模型：SIMD-SM，又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREWSIMD-IN模型：SIMD-DM異步APRAM模型：MIMD-SMBSP模型：MIMD-DM，塊

2、內(nèi)異步并行，塊間顯式同步LogP模型：MIMD-DM，點(diǎn)到點(diǎn)通訊1.3 并行算法的一般概念并行算法的定義并行算法的表示并行算法的復(fù)雜度：運(yùn)行時(shí)間、處理器數(shù)目、成本及成本最優(yōu)、加速比、并行效率、工作量并行算法的WT表示：Brent定理、WT最優(yōu)加速比性能定律并行算法的同步和通訊Ch2 并行算法的基本設(shè)計(jì)技術(shù)基本設(shè)計(jì)技術(shù)平衡樹(shù)方法：求最大值、計(jì)算前綴和倍增技術(shù)：表序問(wèn)題、求森林的根分治策略：FFT分治算法劃分原理：均勻劃分(PSRS排序)、對(duì)數(shù)劃分(并行歸并排序)、方根劃分(Valiant歸并排序)、功能劃分( (m,n)-選擇 )流水線技術(shù)：五點(diǎn)的DFT計(jì)算Ch3 比較器網(wǎng)絡(luò)上的排序和選擇算法3

3、.1 Batcher歸并和排序0-1原理的證明奇偶?xì)w并網(wǎng)絡(luò)：計(jì)算流程和復(fù)雜性(比較器個(gè)數(shù)和延遲級(jí)數(shù))雙調(diào)歸并網(wǎng)絡(luò)：計(jì)算流程和復(fù)雜性(比較器個(gè)數(shù)和延遲級(jí)數(shù))Batcher排序網(wǎng)絡(luò)：原理、種類和復(fù)雜性3.2 (m, n)-選擇網(wǎng)絡(luò)分組選擇網(wǎng)絡(luò)平衡分組選擇網(wǎng)絡(luò)及其改進(jìn)Ch4 排序和選擇的同步算法4.1 一維線性陣列上的并行排序算法4.2 二維Mesh上的并行排序算法ShearSort排序算法Thompson&Kung雙調(diào)排序算法及其計(jì)算示例4.3 Stone雙調(diào)排序算法4.4 Akl并行k-選擇算法：計(jì)算模型、算法實(shí)現(xiàn)細(xì)節(jié)和時(shí)間分析4.5 Valiant并行歸并算法：計(jì)算模型、算法實(shí)現(xiàn)細(xì)節(jié)和

4、時(shí)間分析4.7 Preparata并行枚舉排序算法：計(jì)算模型和算法的復(fù)雜度Ch5 排序和選擇的異步和分布式算法5.1 MIMD-CREW模型上的異步枚舉排序算法5.2 MIMD-TC模型上的異步快排序算法5.3分布式k-選擇算法Ch6 并行搜索6.1 單處理器上的搜索6.2 SIMD共享存儲(chǔ)模型上有序表的搜索：算法6.3 SIMD共享存儲(chǔ)模型上隨機(jī)序列的搜索：算法6.4 樹(shù)連接的SIMD模型上隨機(jī)序列的搜索：算法6.5 網(wǎng)孔連接的SIMD模型上隨機(jī)序列的搜索：算法和計(jì)算示例Ch8 數(shù)據(jù)傳輸與選路8.1 引言信包傳輸性能參數(shù)維序選路(X-Y選路、E-立方選路)選路模式及其傳輸時(shí)間公式8.2 單一

5、信包一到一傳輸SF和CT傳輸模式的傳輸時(shí)間(一維環(huán)、帶環(huán)繞的Mesh、超立方)8.3 一到多播送SF和CT傳輸模式的傳輸時(shí)間(一維環(huán)、帶環(huán)繞的Mesh、超立方)及傳輸方法8.4 多到多播送SF和CT傳輸模式的傳輸時(shí)間(一維環(huán)、帶環(huán)繞的Mesh、超立方)及傳輸方法8.5 貪心算法(書(shū)8.2)二維陣列上的貪心算法蝶形網(wǎng)上的貪心算法8.6 隨機(jī)和確定的選路算法(書(shū)8.3)Ch12矩陣運(yùn)算 12.1 矩陣的劃分：帶狀劃分和棋盤(pán)劃分，有循環(huán)的帶狀劃分和棋盤(pán)劃分矩陣轉(zhuǎn)置：網(wǎng)孔和超立方連接的算法及其時(shí)間分析12.3 矩陣向量乘法帶狀劃分的算法及其時(shí)間分析棋盤(pán)劃分的算法及其時(shí)間分析12.4 矩陣乘法簡(jiǎn)單并行分

6、塊算法Cannon算法及其計(jì)算示例Fox算法及其計(jì)算示例DNS算法及其計(jì)算示例Systolic算法Ch13 數(shù)值計(jì)算13.1 稠密線性方程組求解SIMD-CREW的上三角方程組回代算法SIMD-CREW上的Gauss-Jordan算法MIMD-CREW上的Gauss-Seidel算法13.2 稀疏線性方程組的求解三對(duì)角方程組的奇偶規(guī)約求解法Gauss-Seidel迭代法的紅黑著色并行算法13.3 非線性方程的求根Ch14 快速傅立葉變換FFT14.1 快速傅里葉變換(FFT)離散傅里葉變換(DFT)串行FFT遞歸算法及其計(jì)算原理串行FFT蝶式計(jì)算及其蝶式計(jì)算流圖14.2 DFT直接并行算法SI

7、MD-MT上的并行DFT算法14.3 并行FFT算法SIMD-MC上的FFT算法SIMD-BF上的FFT算法及其時(shí)間分析Ch15 圖論算法15.1 圖的并行搜索p-深度優(yōu)先搜索及其計(jì)算示例p-寬深優(yōu)先搜索及其計(jì)算示例p-寬度優(yōu)先搜索及其計(jì)算示例15.2 圖的傳遞閉包基于布爾矩陣乘積的算法原理計(jì)算示例SIMD-CC上的傳遞閉包算法15.3 圖的連通分量基于傳遞閉包的算法基于頂點(diǎn)合并的算法15.4 圖的最短路徑基于矩陣乘積的算法原理計(jì)算示例15.5 圖的最小生成樹(shù)SIMD-EREW模型上的Prim算法算法的時(shí)間分析Ch17組合搜索 17.1 基于分治法的與樹(shù)搜索與樹(shù)并行搜索過(guò)程處理器數(shù)目與搜索效率關(guān)系17.2 基于分枝限界法的或樹(shù)搜索串行分枝限界法示例: 0-1背包問(wèn)題,8-謎問(wèn)題及其搜索算法的并行化TSP問(wèn)題的分