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

《2022年并行计算多媒体课件并行算法设计与分析课程总结与复习 .pdf》由会员分享，可在线阅读，更多相关《2022年并行计算多媒体课件并行算法设计与分析课程总结与复习 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习必备欢迎下载并行算法课程总结与复习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 模型：

2、MIMD-SM BSP 模型： MIMD-DM，块内异步并行，块间显式同步LogP 模型： MIMD-DM ，点到点通讯1.3 并行算法的一般概念并行算法的定义并行算法的表示并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量并行算法的WT 表示： Brent 定理、 WT 最优加速比性能定律并行算法的同步和通讯Ch2 并行算法的基本设计技术基本设计技术平衡树方法：求最大值、计算前缀和倍增技术：表序问题、求森林的根分治策略： FFT 分治算法划分原理：均匀划分 (PSRS 排序 )、对数划分 (并行归并排序)、方根划分 (Valiant 归并排序 )、功能划分 (

3、(m,n)-精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 5 页学习必备欢迎下载选择) 流水线技术：五点的DFT 计算Ch3 比较器网络上的排序和选择算法3.1 Batcher 归并和排序0-1 原理的证明奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) 双调归并网络：计算流程和复杂性(比较器个数和延迟级数) Batcher 排序网络：原理、种类和复杂性3.2 (m, n)- 选择网络分组选择网络平衡分组选择网络及其改进Ch4 排序和选择的同步算法4.1 一维线性阵列上的并行排序算法4.2 二维 Mesh 上的并行排序算法She

4、arSort 排序算法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 共享存储模型上随机序列的

5、搜索：算法6.4 树连接的SIMD 模型上随机序列的搜索：算法6.5 网孔连接的SIMD 模型上随机序列的搜索：算法和计算示例精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 5 页学习必备欢迎下载Ch8 数据传输与选路8.1 引言信包传输性能参数维序选路 (X-Y 选路、 E-立方选路 ) 选路模式及其传输时间公式8.2 单一信包一到一传输SF 和 CT 传输模式的传输时间(一维环、带环绕的Mesh、超立方 ) 8.3 一到多播送SF 和 CT 传输模式的传输时间(一维环、带环绕的Mesh、超立方 )及传输方法8.4 多到多播送SF 和

6、 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的上三角

7、方程组回代算法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 5 页学习必备欢迎下载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上的并行D

8、FT 算法14.3 并行 FFT 算法SIMD-MC上的 FFT 算法SIMD-BF 上的 FFT 算法及其时间分析Ch15 图论算法15.1 图的并行搜索p-深度优先搜索及其计算示例p-宽深优先搜索及其计算示例p-宽度优先搜索及其计算示例15.2 图的传递闭包基于布尔矩阵乘积的算法原理计算示例SIMD-CC 上的传递闭包算法15.3 图的连通分量基于传递闭包的算法基于顶点合并的算法15.4 图的最短路径基于矩阵乘积的算法原理精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 5 页学习必备欢迎下载计算示例15.5 图的最小生成树SIMD-EREW模型上的 Prim 算法算法的时间分析Ch17 组合搜索17.1 基于分治法的与树搜索与树并行搜索过程处理器数目与搜索效率关系17.2 基于分枝限界法的或树搜索串行分枝限界法示例 : 0-1 背包问题 ,8-谜问题及其搜索算法的并行化TSP 问题的分枝限界算法及其并行化Ch18 随机算法18.1 引言基本知识：随机算法的定义、分类时间复杂性度量设计方法18.2 低度顶点部分独立集串行算法随机并行算法及其正确性证明18.5 多项式恒等的验证基本原理和方法矩阵乘积的验证原理精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 5 页