目录
第一章 并行算法基础
1.1 并行算法的硬件基础
1.1.1 当代并行计算机体系结构
1.1.2 并行计算机互连网络
1.2 并行计算模型
1.2.1 SIMD同步并行计算模型
1.2.2 MIMD异步并行计算模型
1.2.3 其他并行计算模型
1.3 并行算法编程模型
1.3.1 数据并行模型
1.3.2 消息传递模型
1.3.3 共享变量模型
1.4 并行算法的一般概念
1.4.1 并行算法的定义和分类
1.4.2 并行算法的表达
1.4.3 并行算法的复杂性度量
1.4.4 并行算法的WT表示
1.4.5 并行算法的同步和通信
习题
参考文献
第二章 并行算法的基本设计技术
2.1 平衡树方法
2.1.1 求取最大值
2.1.2 计算前缀和
2.2 倍增技术
2.2.1 表序问题的计算
2.2.2 求森林的根
2.3 分治策略
2.3.1 SIMD模型上分治算法的描述
2.3.2 SIMD共享存储模型上的FFT算法
2.4 划分原理
2.4.1 归并原理
2.4.2 划分算法与归并算法
2.5 流水线技术
2.5.1 一维阵列上的流水线归并排序原理
2.5.2 一维阵列上的流水线归并排序算法
2.6 加速级联策略
2.6.1 常数时间求最大值算法
2.6.2 双对数时间算法
2.6.3 加速级联算法
2.7 破对称技术
2.7.1 基本着色算法
2.7.2 快速3-着色算法
2.7.3 最优3-着色算法
习题
参考文献
第三章 比较器网络上的排序和选择算法
3.1 Batcher归并和排序网络
3.1.1 比较操作和[0，1]原理
3.1.2 奇偶归并网络
3.1.3 双调归并网络
3.1.4 Bateher排序网络
3.2 （m，n）一选择网络
3.2.1 分组选择网络
3.2.2 平衡分组选择网络
3.3 AKS排序网络
3.3.1 扩展图和划分网络
3.3.2 部分排序算法
3.3.3 完全排序算法
习题
参考文献
第四章 排序和选择的同步算法
4.1 Stone双调排序算法
4.1.1 均匀洗牌函数及其性质
4.1.2 Stone的观察及其计算模型
4.1.3 Stone的并行排序算法
4.2 Thompson和Kung双调排序算法
4.2.1 处理器编号方式
4.2.2 Thompon和Kung的观察
4.2.3 Thompon和Kung的双调排序算法
4.3 Preparata和Vuilemin双调排序算法
4.3.1 算法原理
4.3.2 流水线技术
4.3.3 算法描述
4.4 Akl并行k-选择算法
4.4.1 算法原理及物理描述
4.4.2 并行k-选择算法
4.4.3 算法分析
4.5 Valiant并行归并算法
4.5.1 归并算法的基本原理
4.5.2 k=pq时Valiant归并
4.5.3 k=rpq时Valiant归并
4.6 Hirschberg并行桶排序算法
4.6.1 并行桶排序算法原理
4.6.2 并行桶排序算法描述
4.7 Preparata并行枚举排序算法
4.7.1 枚举排序及其实现方法
4.7.2 排序算法的设计和分析
4.8 Cole并行归并排序算法
4.8.1 使用覆盖和位序的归并方法
4.8.2 Cole最佳排序算法
4.8.3 算法的正确性证明及分析
习题
参考文献
第五章排序和选择的异步和分布式算法
5.1 MIMD-CREW模型上的异步枚举
排序算法
5.1.1 算法原理和描述
5.1.2 算法举例和分析
5.2 MIMD.TC模型上的
异步快排序算法
5.2.1 算法原理和描述
5.2.2 算法举例和分析
5.3 分布式k-选择算法
5.3.1 随机k-选择算法
5.3.2 确定k-选择算法
5.4 分布式求中值算法
5.4.1 分布式中值
5.4.2 分布式求中值算法
5.5 分布式定序算法
5.5.1 分布式计算模型
5.5.2 分布式定序算法
5.5.3 算法复杂度分析
5.6 分布式排序算法
5.6.1 模型和定义
5.6.2 静态排序算法
5.6.3 算法复杂度分析
习题
参考文献
第六章并行搜索
6.1 单处理机上的搜索
6.1.1 单处理机上的顺序搜索
6.1.2 单处理机上有序表的对半搜索
6.2 SIMD共享存储模型上有序表
的搜索
6.2.1 SIMD-EREW模型上的搜索
6.2.2 SIMD-CREW模型上的搜索
6.3 SIMD共享存储模型上随机序列的搜索
6.3.1 sIMD-SM模型上的随机序列搜索.算法描述
6.3.2 sIMDS-M模型上的随机序列搜索算法分析
6.4 树连接的SIMD模型上随机序列的搜索
6.4.1 提问
6.4.2 维护
6.5 网孔连接的SIMD模型上随机序列的搜索
6.5.1 提问
6.5.2 维护
6.6 MIMD共享存储模型上有序表
的搜索
6.6.1 AVL树及其顺序
插入算法
6.6.2 Ellis并行搜索和插入算法
习题
第七章排列和组合
第八章数据传输与选路
第九章并行串匹配
第十章表达式求值
第十一章上下文无关语富的并行识别与语法分析
第十二章矩阵运算
第十三章数值计算
第四章肿和卷积与滤波
· · · · · · (收起)