并行算法课程总结与复习20170526.docVIP

《并行算法》课程总结与复习 2017.05.26 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定理 加速比性能定律(略) 并行算法的同步和通讯(略) Ch2 设计技术 2.1 并行算法的三种基本设计方法及其代表实例 2.2 基本设计技术 平衡树方法：求最大值、计算前缀和 倍增技术：表序问题、求森林的根 分治策略：FFT分治算法 划分原理： 均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) 流水线技术：五点的DFT计算，Systolic算法 加速级联 破对称技术 Ch3 前缀计算（略） Ch4 排序和选择网络（略） 4.1 Batcher归并和排序 0-1原理的证明(略) 奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) 双调归并网络：计算流程和复杂性(比较器个数和延迟级数) Batcher排序网络：原理、种类和复杂性 4.2 (m, n)-选择网络 分组选择网络 平衡分组选择网络及其改进 Ch5 排序和选择算法（略） 5.1 一维线性阵列上的并行排序算法 5.2 二维Mesh上的并行排序算法 ShearSort排序算法 ThompsonKung双调排序算法及其计算示例 5.3 Stone双调排序算法(略) 5.4 Akl并行k-选择算法：计算模型、时间分析 5.5 Valiant并行归并算法：计算模型、时间分析 5.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 Ch7 并行有哪些信誉好的足球投注网站（略） 7.1 单处理器上的有哪些信誉好的足球投注网站(略) 7.2 SIMD共享存储模型上有序表的有哪些信誉好的足球投注网站：算法 7.3 SIMD共享存储模型上随机序列的有哪些信誉好的足球投注网站：算法 7.4 树连接的SIMD模型上随机序列的有哪些信誉好的足球投注网站：算法 7.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.2 矩阵转置：网孔和超立方连接的算法及其时间分析 12.3 矩阵向量乘法 带状划分的算法及其时间分析 棋盘划分的算法及其时间分析 Systolic算法 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 图