基础篇 1
第1章 引言 1
1.1 并行计算的概念 1
1.2 并行计算的发展历程 2
1.3 并行计算的应用 2
1.4 并行计算面临的技术挑战 4
1.5 人类对高速计算的探索 5
第2章 并行计算机体系结构 6
2.1 并行计算机体系结构模型 6
2.2 Beowulf机群 7
2.3 并行机群网络互联拓扑结构实例 11
第3章 PC机群的搭建 13
3.1 安装和配置基本Linux系统 13
3.2 安装NFS文件系统 13
3.3 配置用户环境文件 14
3.4 配置ssh公钥认证 14
3.5 安装和配置MPICH 15
3.6 并行环境配置中的疑难解析 18
3.7 SHELL技巧在并行环境中的运用 18
3.8 采用VMware在单台PC机上建立并行环境 22
第4章 并行程序开发——MPI编程 27
4.1 MPI简介 27
4.1.1 MPI的定义和特点 27
4.1.2 MPI的发展过程 28
4.1.3 MPI的语言绑定 28
4.1.4 目前主要的MPI实现 28
4.1.5 Linux的程序编辑器vi 29
4.2 MPI并行编程知识 30
4.2.1 MPI程序的基本结构 30
4.2.2 MPI常用函数 33
4.2.3 MPI的错误码 36
4.2.4 MPI程序的一些惯例 37
4.3 MPI消息 37
4.3.1 MPI消息的概念 37
4.3.2 一个简单的MPI消息传递例子 39
4.4 MPI程序示例 40
4.4.1 获取数据传输时间 40
4.4.2 计算π值的MPI程序 41
4.4.3 MPI的错误退出方式 42
4.4.4 数据的循环传送 42
4.4.5 非阻塞通信程序 43
4.4.6 矩阵相乘的并行算法 45
4.5 MPI中的组通信 47
4.5.1 组通信概述 47
4.5.2 广播 48
4.5.3 收集 49
4.5.4 散发 50
4.6 MPI综合编程实例——快速排序算法的并行化 51
4.6.1 串行程序的并行化方法 52
4.6.2 快速排序算法原理 53
4.6.3 快速排序法的并行化及MPI程序 54
第5章 并行机群的性能测试 60
5.1 机器级性能评测 60
5.1.1 CPU 60
5.1.2 存储器 60
5.1.3 通信开销 61
5.1.4 机群的规模可扩展性 61
5.2 算法级性能评测 62
5.2.1 机群加速比 62
5.2.2 机群效率 63
5.3 基准程序级性能评测 63
5.3.1 基准测试程序的分类 63
5.3.2 Linpack基准测试程序 64
5.3.3 其他基准测试程序 73
第6章 机群监控 75
6.1 机群监控介绍 75
6.1.1 本地化机群监控 75
6.1.2 网络化监控 75
6.1.3 Linux系统中常用的监控方式 76
6.2 ／proc文件系统介绍 77
6.2.1 虚拟文件系统 78
6.2.2 ／proc文件系统 79
6.2.3 ／proc目录及文件内容 82
6.3 基于／proc的机群监控系统实例 85
6.3.1 系统总体结构 86
6.3.2 部分模块实现例程 87
应用篇 91
第7章 并行数据挖掘 91
7.1 并行数据挖掘概述 91
7.1.1 数据挖掘的定义及分类 91
7.1.2 数据挖掘的步骤 92
7.1.3 数据挖掘算法的并行化策略 92
7.1.4 并行挖掘算法中需解决的问题 93
7.2 关联规则概述 93
7.2.1 关联规则的基本概念 93
7.2.2 关联规则挖掘过程 94
7.3 串行关联规则算法 94
7.3.1 Apriori算法 94
7.3.2 AprioriTid算法 97
7.4 并行关联规则算法 99
7.4.1 CD算法 100
7.4.2 DD算法 102
7.4.3 FDM算法 103
7.5 决策树概述 107
7.5.1 决策树的构建 107
7.5.2 决策树的剪枝 108
7.5.3 决策树的测试 108
7.6 串行决策树算法 109
7.6.1 ID3算法 109
7.6.2 ID3算法的改进 111
7.7 并行决策树算法 112
7.7.1 SLIQ算法及其并行化处理 113
7.7.2 SPRINT算法及其并行化处理 114
第8章 并行遗传算法 120
8.1 遗传算法简介 120
8.2 遗传算法的数学理论 123
8.2.1 模式定理 123
8.2.2 收敛定理 125
8.3 基本遗传算法 125
8.3.1 基本遗传算法描述 125
8.3.2 基本遗传算法的实现技术 126
8.4 并行遗传算法 129
8.4.1 遗传算法的并行化 129
8.4.2 并行遗传算法的分类 129
8.5 函数极值问题的并行遗传算法 133
8.5.1 函数极值问题描述 133
8.5.2 传统求极值方法介绍 133
8.5.3 串行遗传算法计算函数极值 134
8.5.4 并行遗传算法计算函数极值 135
第9章 并行迭代算法 141
9.1 迭代算法的数学原理 141
9.1.1 迭代算法的一般性原理 141
9.1.2 雅可比迭代法 141
9.1.3 高斯-赛德尔迭代法 142
9.2 迭代算法的串行实现 143
9.2.1 雅可比迭代的串行算法 143
9.2.2 高斯-赛德尔迭代的串行算法 143
9.3 并行迭代算法及实现 144
9.3.1 初始化节点数据 144
9.3.2 雅可比迭代并行算法 145
9.3.3 高斯-赛德尔迭代并行算法 146
9.3.4 J迭代与G-S迭代的结合算法 147
9.4 并行迭代算法性能分析 148
第10章 并行计算前沿 150
10.1 量子并行计算 150
10.1.1 量子计算机的出现 150
10.1.2 量子计算机的指数并行能力 150
10.2 隐含并行计算 151
10.2.1 遗传算法的隐含并行性 151
10.2.2 隐含并行性的物理解释 152
10.2.3 量子算法与遗传算法的比较 154
10.3 云计算 155
10.3.1 云计算的基本原理 155
10.3.2 云计算的实现 156
10.3.3 云计算的应用 157
附录 PROC重要目录及文件细解 158
参考文献 169