《并行算法》课程总结与复习Ch1并行算法基础1.1并行计算机体系结构并行计算机的分类SISD,SIMD,MISD,MIMD；SIMD,PVP,SMP,MPP,COW,DSM并行计算机的互连方式静态：LA(LC),MC,TC,MT,HC,BC,SE动态：Bus,CrossbarSwitcher,MIN(MultistageInterconnectionNetworks)1.2并行计算模型PRAM模型：SIMD-SM，又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREWSIMD-IN模型：SIMD-DM异步APRAM模型：MIMD-SMBSP模型：MIMD-DM，块内异步并行，块间显式同步LogP模型：MIMD-DM，点到点通讯1.3并行算法的一般概念并行算法的定义并行算法的表示并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量并行算法的WT表示：Brent定理、WT最优加速比性能定律并行算法的同步和通讯Ch2并行算法的基本设计技术基本设计技术平衡树方法：求最大值、计算前缀和倍增技术：表序问题、求森林的根分治策略：FFT分治算法划分原理：均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分((m,n)-选择)流水线技术：五点的DFT计算Ch3比较器网络上的排序和选择算法3.1Batcher归并和排序0-1原理的证明奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数)双调归并网络：计算流程和复杂性(比较器个数和延迟级数)Batcher排序网络：原理、种类和复杂性3.2(m,n)-选择网络分组选择网络平衡分组选择网络及其改进Ch4排序和选择的同步算法4.1一维线性阵列上的并行排序算法4.2二维Mesh上的并行排序算法ShearSort排序算法Thompson&Kung双调排序算法及其计算示例4.3Stone双调排序算法4.4Akl并行k-选择算法：计算模型、算法实现细节和时间分析4.5Valiant并行归并算法：计算模型、算法实现细节和时间分析4.7Preparata并行枚举排序算法：计算模型和算法的复杂度Ch5排序和选择的异步和分布式算法5.1MIMD-CREW模型上的异步枚举排序算法5.2MIMD-TC模型上的异步快排序算法5.3分布式k-选择算法Ch6并行搜索6.1单处理器上的搜索6.2SIMD共享存储模型上有序表的搜索：算法6.3SIMD共享存储模型上随机序列的搜索：算法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快速傅立叶变换FFT14.1快速傅里叶变换(FFT)离散傅里叶变换(DFT)串行FFT递归算法及其计算原理串行FFT蝶式计算及其蝶式计算流图14.2DFT直接并行算法SIMD-MT上的并行DFT算法14.3并行FFT算法SIMD-MC上的FFT算法SIMD-BF上的FFT算法及其时间分析Ch15图论算法15.1图的并行搜索p-深度优先搜索及其计算示例p-宽深优先搜索及其计算示例p-宽度优先搜索及其计算示例15.2图的传递闭包基于布尔矩阵乘积的算法原理