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

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

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

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

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

4、排序算法 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

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

6、输时间一维环、带围绕的Mesh、超立方 及传输方法8.4 多到多播送SF 和 CT 传输模式的传输时间一维环、带围绕的Mesh、超立方 及传输方法8.5 贪心算法 书 8.2 二维阵列上的贪心算法 蝶形网上的贪心算法 8.6 随机和确定的选路算法 书 8.3 Ch12 矩阵运算 12.1 矩阵的划分：带状划分和棋盘划分,有循环的带状划分和棋盘划分 矩阵转置：网孔和超立方连接的算法及其时间分析 12.3 矩阵向量乘法 带状划分的算法及其时间分析 棋盘划分的算法及其时间分析 12.4 矩阵乘法 简洁并行分块算法 Cannon 算法及其运算示例 Fox 算法及其运算示例 DNS 算法及其运算示例 S

7、ystolic 算法 Ch13 数值运算 13.1 稠密线性方程组求解名师归纳总结 SIMD-CREW的上三角方程组回代算法第 3 页,共 5 页- - - - - - -精选学习资料 - - - - - - - - - SIMD-CREW上的 Gauss-Jordan 算法学习必备欢迎下载MIMD-CREW上的 Gauss-Seidel 算法13.2 稀疏线性方程组的求解 三对角方程组的奇偶规约求解法Gauss-Seidel 迭代法的红黑着色并行算法 13.3 非线性方程的求根Ch14 快速傅立叶变换 FFT 14.1 快速傅里叶变换 FFT 离散傅里叶变换 DFT 串行 FFT 递归算法及

8、其运算原理 串行 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 图的最短路径 基于矩阵乘积的算法原理名师归纳总结 - - - - -

9、 - -第 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 页