并行计算-多媒体课件-并行算法设计与分析-课程总结与复习1

《并行算法》课程总结与复习并行算法基础Chi并行计算机体系结构

1.1并行计算机的分类；SISD,SIMD,MISD,MIMDSIMD,PVP,SMP,MPP,COW,DSM并行计算机的互连方式静态（）LA LC,MC,TC,MT,HC,BC,SE动态（）Bus,Crossbar Switcher,MIN MultistageInterconnection Networks并行计算模型

1.2模型PRAM SIMD-SM,又分（）CRCW CPRAM,PPRAM,APRAM,CREW,EREW模型SIMD-IN SIMD-DM异步模型APRAM MIMD-SM模型块内异步并行，块间显式同步BSP MIMD-DM,模型点到点通讯LogP MIMD-DM,并行算法的一般概念

1.3并行算法的定义并行算法的表示并行算法的困难度运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量并行算法的表示定理、最优WT BrentWT加速比性能定律并行算法的同步和通讯并行算法的基本设计技术Ch2基本设计技术平衡树方法求最大值、计算前缀和倍增技术表序问题、求森林的根分治策略分治算法FFT划分原理匀称划分（排序）、对数划分（并行归并排序）、方根划分（归并排序）、PSRS Valiant功能划分（（）m,n-选择）流水线技术五点的计算DFT比较器网络上的排序和选择算法Ch3归并和排序

3.1Batcher原理的证明0-1奇偶归并网络计算流程和困难性（比较器个数和延迟级数）双调归并网络计算流程和困难性（比较器个数和延迟级数）排序网络原理、种类和困难性Batcher（）.选择网络

3.2m,n分组选择网络平衡分组选择网络及其改进排序和选择的同步算法Ch4一维线性阵列上的并行排序算法

4.1二维上的并行排序算法

4.2Mesh排序算法ShearSort双调排序算法及其计算示例ThompsonKung双调排序算法

4.3Stone并行选择算法计算模型、算法实现细微环节和时间分析

4.4Aki k-并行归并算法计算模型、算法实现细微环节和时间分析

4.5Valiant并行枚举排序算法计算模型和算法的困难度

4.7Preparata排序和选择的异步和分布式算法Ch5模型上的异步枚举排序算法

5.1MIMD-CREW模型上的异步快排序算法

5.2MIMD-TC分布式.选择算法

5.3k并行搜寻Ch6单处理器上的搜寻

6.1共享存储模型上有序表的搜寻算法

6.2SIMD共享存储模型上随机序列的搜寻算法

6.3SIMD树连接的模型上随机序列的搜寻算法

6.4SIMD网孔连接的模型上随机序列的搜寻算法和计算示例

6.5SIMD数据传输与选路Ch8引言

8.1信包传输性能参数维序选路（选路、立方选路）X-Y E-选路模式及其传输时间公式单一信包一到一传输

8.2和传输模式的传输时间（一维环、带环绕的、超立方）SF CTMesh一到多播送

8.3和传输模式的传输时间（一维环、带环绕的、超立方）及传输方法SF CTMesh多到多播送

8.4和传输模式的传输时间（一维环、带环绕的、超立方）及传输方法SF CTMesh贪心算法（书）

8.

58.2二维阵列上的贪心算法蝶形网上的贪心算法随机和确定的选路算法（书）

8.

68.3矩阵运算Chl2矩阵的划分带状划分和棋盘划分，有循环的带状划分和棋盘划分

12.1矩阵转置网孔和超立方连接的算法及其时间分析矩阵向量乘法

12.3带状划分的算法及其时间分析棋盘划分的算法及其时间分析矩阵乘法

12.4简洁并行分块算法算法及其计算示例Cannon算法及其计算示例Fox算法及其计算示例DNS算法Systolic数值计算Chl3稠密线性方程组求解

13.1的上三角方程组回代算法SIMD-CREW上的算法SIMD-CREW Gauss-Jordan上的算法MIMD-CREW Gauss-Seidel稀疏线性方程组的求解

13.2三对角方程组的奇偶规约求解法迭代法的红黑着色并行算法Gauss-Seidel非线性方程的求根

13.3快速傅立叶变换Chl4FFT快速傅里叶变换

14.1FFT离散傅里叶变换DFT串行递归算法及其计算原理FFT串行蝶式计算及其蝶式计算流图FFT干脆并行算法

14.2DFT上的并行算法SIMD-MT DFT并行算法

14.3FFT上的算法SIMD-MC FFT上的算法及其时间分析SIMD-BF FFT图论算法Chl5图的并行搜寻

15.1深度优先搜寻及其计算示例P-宽深优先搜寻及其计算示例P-宽度优先搜寻及其计算示例P-图的传递闭包

15.2基于布尔矩阵乘积的算法原理计算示例上的传递闭包算法SIMD-CC图的连通重量

15.3基于传递闭包的算法基于顶点合并的算法图的最短路径

15.4基于矩阵乘积的算法原理计算示例图的最小生成树

15.5模型上的算法SIMD-EREW Prim算法的时间分析组合搜寻Chl7基于分治法的与树搜寻

17.1与树并行搜寻过程处理器数目与搜寻效率关系基于分枝限界法的或树搜寻

17.22串行分枝限界法示例:背包问题-谜问题及其搜寻算法的并行化0-1,8问题的分枝限界算法及其并行化TSP随机算法Chl8引言

18.1基本学问随机算法的定义、分类时间困难性度量设计方法低度顶点部分独立集

18.2串行算法随机并行算法及其正确性证明多项式恒等的验证

18.5基本原理和方法矩阵乘积的验证原理。