2023年并行计算多媒体课件并行算法设计与分析课程全面汇总归纳与复习.pdf

《2023年并行计算多媒体课件并行算法设计与分析课程全面汇总归纳与复习.pdf》由会员分享，可在线阅读，更多相关《2023年并行计算多媒体课件并行算法设计与分析课程全面汇总归纳与复习.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)-学习必备 欢迎下载 选择)流水线技术：五点的 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.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 模型上随机序列的搜索：算法

5、6.5 网孔连接的 SIMD 模型上随机序列的搜索：算法和计算示例 般概念并行算法的定义并行算法的表示并行算法的复杂度运行时间处理法求最大值计算前缀和倍增技术表序问题求森林的根分治策略分治算法排序原理的证明奇偶归并网络计算流程和复杂性比较器个数和延迟级数学习必备 欢迎下载 Ch8 数据传输与选路 8.1 引言 信包传输性能参数 维序选路(X-Y 选路、E-立方选路)选路模式及其传输时间公式 8.2 单一信包一到一传输 SF 和 CT 传输模式的传输时间(一维环、带环绕的 Mesh、超立方)8.3 一到多播送 SF 和 CT 传输模式的传输时间(一维环、带环绕的 Mesh、超立方)及传输方法 8

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

7、3.1 稠密线性方程组求解 SIMD-CREW 的上三角方程组回代算法 般概念并行算法的定义并行算法的表示并行算法的复杂度运行时间处理法求最大值计算前缀和倍增技术表序问题求森林的根分治策略分治算法排序原理的证明奇偶归并网络计算流程和复杂性比较器个数和延迟级数学习必备 欢迎下载 SIMD-CREW 上的 Gauss-Jordan算法 MIMD-CREW 上的 Gauss-Seidel算法 13.2 稀疏线性方程组的求解 三对角方程组的奇偶规约求解法 Gauss-Seidel迭代法的红黑着色并行算法 13.3 非线性方程的求根 Ch14 快速傅立叶变换 FFT 14.1 快速傅里叶变换(FFT)离

8、散傅里叶变换(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 图的最短路径

9、 基于矩阵乘积的算法原理 般概念并行算法的定义并行算法的表示并行算法的复杂度运行时间处理法求最大值计算前缀和倍增技术表序问题求森林的根分治策略分治算法排序原理的证明奇偶归并网络计算流程和复杂性比较器个数和延迟级数学习必备 欢迎下载 计算示例 15.5 图的最小生成树 SIMD-EREW 模型上的 Prim 算法 算法的时间分析 Ch17 组合搜索 17.1 基于分治法的与树搜索 与树并行搜索过程 处理器数目与搜索效率关系 17.2 基于分枝限界法的或树搜索 串行分枝限界法 示例:0-1背包问题,8-谜问题及其搜索算法的并行化 TSP 问题的分枝限界算法及其并行化 Ch18 随机算法 18.1 引言 基本知识：随机算法的定义、分类 时间复杂性度量 设计方法 18.2 低度顶点部分独立集 串行算法 随机并行算法及其正确性证明 18.5 多项式恒等的验证 基本原理和方法 矩阵乘积的验证原理 般概念并行算法的定义并行算法的表示并行算法的复杂度运行时间处理法求最大值计算前缀和倍增技术表序问题求森林的根分治策略分治算法排序原理的证明奇偶归并网络计算流程和复杂性比较器个数和延迟级数