并行计算多媒体课件并行算法设计与分析课程总结与复习
《并行算法》课程总结及复习 Ch1 并行算法基础 1.1 并行计算机体系结构 并行计算机的分类 SISD,SIMD,MISD,MIMD; SIMD,PVP,SMP,MPP,COW,DSM 并行计算机的互连方式 静态:LA(LC),MC,TC,MT,HC,BC,SE 动态:Bus, Crossbar Switcher, MIN(Multistage Interconnection 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表示:Brent定理、WT最优 加速比性能定律 并行算法的同步和通讯 Ch2 并行算法的基本设计技术 基本设计技术 平衡树方法:求最大值、计算前缀和 倍增技术:表序问题、求森林的根 分治策略:FFT分治算法 划分原理: 匀称划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) 流水线技术:五点的DFT计算 Ch3 比较器网络上的排序和选择算法 3.1 Batcher归并和排序 0-1原理的证明 奇偶归并网络:计算流程和困难性(比较器个数和延迟级数) 双调归并网络:计算流程和困难性(比较器个数和延迟级数) Batcher排序网络:原理、种类和困难性 3.2 (m, n)-选择网络 分组选择网络 平衡分组选择网络及其改进 Ch4 排序和选择的同步算法 4.1 一维线性阵列上的并行排序算法 4.2 二维Mesh上的并行排序算法 ShearSort排序算法 Thompson&Kung双调排序算法及其计算示例 4.3 Stone双调排序算法 4.4 Akl并行k-选择算法:计算模型、算法实现细微环节和时间分析 4.5 Valiant并行归并算法:计算模型、算法实现细微环节和时间分析 4.7 Preparata并行枚举排序算法:计算模型和算法的困难度 Ch5 排序和选择的异步和分布式算法 5.1 MIMD-CREW模型上的异步枚举排序算法 5.2 MIMD-TC模型上的异步快排序算法 5.3分布式k-选择算法 Ch6 并行搜寻 6.1 单处理器上的搜寻 6.2 SIMD共享存储模型上有序表的搜寻:算法 6.3 SIMD共享存储模型上随机序列的搜寻:算法 6.4 树连接的SIMD模型上随机序列的搜寻:算法 6.5 网孔连接的SIMD模型上随机序列的搜寻:算法和计算示例 Ch8 数据传输及选路 8.1 引言 信包传输性能参数 维序选路(X-Y选路、E-立方选路) 选路模式及其传输时间公式 8.2 单一信包一到一传输 SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) 8.3 一到多播送 SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 8.4 多到多播送 SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 8.5 贪心算法(书8.2) 二维阵列上的贪心算法 蝶形网上的贪心算法 8.6 随机和确定的选路算法(书8.3) Ch12矩阵运算 12.1 矩阵的划分:带状划分和棋盘划分,有循环的带状划分和棋盘划分 矩阵转置:网孔和超立方连接的算法及其时间分析 12.3 矩阵向量乘法 带状划分的算法及其时间分析 棋盘划分的算法及其时间分析 12.4 矩阵乘法 简洁并行分块算法 Cannon算法及其计算示例 Fox算法及其计算示例 DNS算法及其计算示例 Systolic算法 Ch13 数值计算 13.1 稠密线性方程组求解 SIMD-CREW的上三角方程组回代算法 SIMD-CREW上的Gauss-Jordan算法 MIMD-CREW上的Gauss-Seidel算法 13.2 稀疏线性方程组的求解 三对角方程组的奇偶规约求解法 Gauss-Seidel迭代法的红黑着色并行算法 13.3 非线性方程的求根 Ch14 快速傅立叶变换FFT 14.1 快速傅里叶变换(FFT) 离散傅里叶变换(DFT) 串行FFT递归算法及其计算原理 串行FFT蝶式计算及其蝶式计算流图 14.2 DFT干脆并行算法 SIMD-MT上的并行DFT算法 14.3 并行FFT算法 SIMD-MC上的FFT算法 SIMD-BF上的FFT算法及其时间分析 Ch15 图论算法 15.1 图的并行搜寻 p-深度优先搜寻及其计算示例 p-宽深优先搜寻及其计算示例 p-宽度优先搜寻及其计算示例 15.2 图的传递闭包 基于布尔矩阵乘积的算法原理 计算示例 SIMD-CC上的传递闭包算法 15.3 图的连通重量 基于传递闭包的算法 基于顶点合并的算法 15.4 图的最短路径 基于矩阵乘积的算法原理 计算示例 15.5 图的最小生成树 SIMD-EREW模型上的Prim算法 算法的时间分析 Ch17组合搜寻 17.1 基于分治法的及树搜寻 及树并行搜寻过程 处理器数目及搜寻效率关系 17.2 基于分枝限界法的或树搜寻 串行分枝限界法 示例: 0-1背包问题,8-谜问题及其搜寻算法的并行化 TSP问题的分枝限界算法及其并行化 Ch18 随机算法 18.1 引言 基本学问:随机算法的定义、分类 时间困难性度量 设计方法 18.2 低度顶点部分独立集 串行算法 随机并行算法及其正确性证明 18.5 多项式恒等的验证 基本原理和方法 矩阵乘积的验证原理 7 / 7