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

并行算法课程总结及复习 Ch1 并行算法基础 1.1 并行计算机体系结构 并行计算机的分类 SISD,SIMD,MISD,MIMD； SIMD,PVP,SMP,MPP,COW,DSM 并行计算机的互连方式 静态LALC,MC,TC,MT,HC,BC,SE 动态Bus, Crossbar Switcher, MINMultistage Interconnection Networks 1.2 并行计算模型 PRAM模型SIMD-SM， 又分CRCWCPRAM,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排序算法 ThompsonKung双调排序算法及其计算示例 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