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

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 networks1.2 并行运算模型pram 模型： simd-sm ,又分 crcwcpram、ppram、apram、crew、erew simd-in模型： simd-dm异步 apra

2、m模型： mimd-smbsp 模型： mimd-dm,块内异步并行,块间显式同步logp 模型： mimd-dm,点到点通讯1.3 并行算法的一般概念并行算法的定义并行算法的表示并行算法的复杂度：运行时间.处理器数目.成本及成本最优.加速比.并行效率.工作量并行算法的wt 表示： brent 定理. wt 最优加速比性能定律并行算法的同步和通讯ch2并行算法的基本设计技术基本设计技术平稳树方法：求最大值.运算前缀和倍增技术：表序问题.求森林的根 分治策略： fft 分治算法划分原理：匀称划分 psrs 排序 .对数划分 并行归并排序.方根划分 valiant 归并排序 .功能划分 m、n-精

3、品学习资料精选学习资料 - - - 欢迎下载学习必备欢迎下载挑选流水线技术：五点的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模型上随机序列的搜寻：算法6.5 网孔连接的simd 模型上随机

5、序列的搜寻：算法和运算示例精品学习资料精选学习资料 - - - 欢迎下载学习必备欢迎下载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.3ch12

6、 矩阵运算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 稀疏

7、线性方程组的求解三对角方程组的奇偶规约求解法gauss-seidel 迭代法的红黑着色并行算法13.3 非线性方程的求根ch14快速傅立叶变换fft14.1 快速傅里叶变换fft离散傅里叶变换 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 图的最短路径基于矩阵乘积的算法原理精品学习资料精选学习资料 - - - 欢迎下载学习必备欢迎下载运算示例15.5 图的最小生成树simd-erew模型上的 prim 算法算法的时间分析ch17 组合搜寻17.1 基于分治法的与树搜寻与树并行搜寻过程处理器数目与搜寻效率关系17.2 基于分枝限界法的或树搜寻串行分枝限界法示例 : 0-1 背包问题 、8-谜问题及其搜寻算法的并行化ts