本书全面讲述并行技术研究及并行程序设计所需要的基本知识，包括并行系统构建、并行程序设计、并行系统性能测试、机群监控系统设计及并行算法设计。
本书可作为从事并行技术研究、设计和开发的教师、研究人员和开发人员的重要参考书，也可以作为高等院校计算机及相关专业的高年级本科生及研究生并行技术课程的教材。
本书特点
●面向实际应用、贴近实战，使读者能够亲身感受并行计算技术的魅力，书中的许多内容来源于作者的科研和工作成果。
●为选择本书作为教材的教师提供电子课件，需要的教师可登录机工新阅读网站（www.cmpreading.com）下载。
无
历史发展历程证明，人类总是在寻求最佳的问题解决方法。随着科学技术的发展，各科学及应用部门对计算机的依赖性越来越大，对计算机的性能也提出越来越高的要求，大规模的数值运算早已不再是科研部门的专利，银行、游戏娱乐行业等都成为大规模计算的重要客户。在这样的需求背景下，人们基于对下面两方面的认识，促成了并行计算技术的产生与发展。
第一，芯片技术近几十年的发展逐渐达到物理极限，芯片的量子效应也开始出现，想大幅度提高单个芯片的计算能力面临很大的技术困难，而使用多台处理机以一定方式连接起来共同求解一个问题的并行计算机是解决大规模计算问题的一个有效途径。通过采用并行计算技术，可以使我们在现有芯片制造技术的情况下快速提升计算能力，满足日益发展的大规模计算需求。第二，同时性与并行性是客观物质世界普遍存在的属性，很多计算问题都可以划分为能够并行计算的多个子任务。
并行计算是针对一个具体问题，利用它内在的并行性，设计并行算法，将其分解为相互独立、但彼此又有一定联系的若干个子问题，再分别交给各个处理机，由所有处理机按照并行算法完成初始应用问题的求解。这是一种达到高性能计算的手段，能够将计算能力从单个处理器扩展到多个处理器。在这里我们要和高性能计算这一概念相区别。高性能计算是指运算速度快、性能高、处理能力强的一类计算机，它提供当前最先进的计算能力，以支撑人们理解和解决复杂的计算问题。并行计算技术是实现高性能计算的一种主要方式。
并行计算技术从产生到现在，经历了几十年的发展，其应用领域从科学及工程应用的计算模拟，到商业应用的数据挖掘及事务处理等，并对这些领域产生了巨大的影响。并行计算技术高效的处理能力极大地增强了人们进行科学研究的能力，加快了把科学技术转化为生产力的过程，推动着当代科学计算技术向纵深发展。并行计算技术现在已成为计算机科学领域的一个重要研究方向，为国防建设和国民经济发展做出了重大贡献。通过本书的学习，读者将能够亲身感受并行计算技术的魅力。
从20世纪90年代开始，我国的并行计算专家先后出版了许多与并行计算相关的书籍，这些书籍介绍了并行机体系结构模型和并行算法设计，但很少对并行计算平台（例如机群）的具体搭建、测试和监控过程以及并行计算在其他先进技术领域的具体应用进行系统而详细的介绍。为此我们编写了本书。本书适合具备一定计算机技术基础知识、想在并行计算领域有所成就的读者，特别适合从事并行系统设计和开发的工程技术人员阅读。读者通过学习本书，不仅能够了解并行计算技术的基础知识，而且可以在有限的硬件条件下实现并行程序及并行系统的设计和开发。
全书从内容上分为两部分：基础篇与应用篇。
基础篇包括第1～6章，主要对并行计算技术的发展、应用以及并行计算机模型进行概述。作者根据多年在科研工作中的实际经验，在基础篇的第3～6章系统介绍MPI 并行编程环境的使用与机群的搭建、测试和监控过程，旨在帮助读者完成简单的并行程序设计，掌握并行计算平台的搭建、测试与监控方法，为深入学习并行计算技术打下坚实的基础。本篇主要面向高年级本科学生，使其初步掌握基本的并行计算知识。
应用篇包括第7～10章，各章自成一体，读者可根据自己的兴趣和需要选读。在基础篇的基础上进行了拓展与深化，详细介绍并行计算技术在数据挖掘、遗传算法、迭代算法中的应用，并对并行技术的发展前沿进行了介绍，不仅使读者了解并行计算技术的应用方法，而且为读者深入学习和研究并行计算技术提供了有益的借鉴。本篇主要面向研究生及具备一定知识基础的并行系统开发人员，讲解并行计算的高级应用知识。
各章的主要内容介绍如下：
第1章 对并行计算的概念、发展及应用等方面进行概述。
第2章 介绍并行系统结构模型，特别是对Beowulf机群系统进行详细的介绍，使读者对并行计算机体系结构有一个初步的认识。
第3章 主要介绍机群并行计算环境的搭建过程，包括操作系统的配置及MPI的安装，以及采用VMware在单台PC机上建立并行实验环境的方法。
第4章 介绍MPI的基本功能和基本实现方法，从简单的例子入手，讲解MPI程序设计的基本过程和框架。本章内容对具有C语言串行程序设计经验的人员而言，很容易理解和接受。
第5章 从机器级、算法级、基准程序级三方面对Linux机群进行性能分析，详细分析加速比、效率、扩展性和浮点计算能力等机群性能指标。
第6章 简单介绍机群监控的原理，并详细分析Linux的/proc文件系统以及基于/proc文件系统的机群监控系统，向读者展示了机群监控系统的设计过程，为读者设计自己的监控系统提供借鉴。
第7章 介绍并行数据挖掘的基础理论，并在此基础上详细阐述关联规则挖掘与决策树挖掘方法中主要的串行与并行算法。
第8章 介绍遗传算法的基本概念和理论，作为一种重要的非数值并行算法，本章对遗传算法的并行化方法作了介绍，使读者能掌握基本的遗传算法和并行技术。
第9章 介绍迭代算法的一般性原理，对迭代算法中著名的雅可比迭代和高斯－赛德尔迭代进行详细阐述，并介绍了雅可比迭代、高斯－赛德尔迭代、J迭代与G-S迭代结合的串行与并行算法，最后给出以上算法在不同问题规模下的测试结果以及对结果的分析。
第10章 介绍并行计算技术中一些前沿技术，如量子计算机、隐含并行性和云计算等，可以为读者开拓视野。
致谢
本书在编写过程中得到了许多老师和学生的帮助，向令、黄松林、李惠君、李裕森、李庆波、伍国良、张成等同学参与了本书的编写以及书中研究项目的设计开发工作。本书的前期工作得到了中国科技大学高性能中心许胤龙教授、李春生老师，电子科技大学孙世新教授、李建平教授，成都信息工程学院陈高云副教授、安俊秀副教授、郭本俊讲师，国防科技大学霍志国博士、贾承丽博士，上海惠普Intel解决方案中心张涛工程师，中国电子科技集团第三十八研究所成像中心张长耀研究员、阮祥伟工程师、常庆利工程师、李英先工程师等同志的帮助。本书的编写参阅了大量的相关书籍和研究资料，在此一并向这些书籍和资料的作者表示感谢，并向他们前期所做的工作表示敬意。本书的写作还得到以下基金的资助：国家自然科学基金（60702075）、中国博士后科学基金一等（20070410385）、四川省教育厅自然科学重点项目（07ZA014）、成都信息工程学院自然科学与技术发展基金（CSRF200701）。
由于作者水平所限，书中难免有很多不足之处，希望读者批评指正。
王 鹏
成都信息工程学院并行计算实验室
电子科技大学计算机科学与工程学院
作 者 简 介
王鹏，男，生于1975年，副教授、博士后、硕士研究生导师，中国计算机学会高级会员，高性能计算专委会委员，成都信息工程学院并行计算实验室主任。2004年于中国科学院获计算机软件与理论博士学位。2006年起在电子科技大学计算机科学与工程学院小波国际研究中心从事博士后研究工作，现作为项目负责人承担国家自然科学基金、中国博士后科学基金一等资助和四川省教育厅自然科学重点项目。主要研究方向为并行计算，量子计算，数据挖掘及移动搜索引擎。已发表论文50余篇，其中多篇被EI及SCI收录。
本书全面讲述并行技术研究及并行程序设计所需要的基本知识，包括并行系统构建、并行程序设计、并行系统性能测试、机群监控系统设计及并行算法设计。 本书可作为从事并行技术研究、设计和开发的教师、研究人员和开发人员的重要参考书，也可以作为高等院校计算机及相关专业的高年级本科生及研究生并行技术课程的教材。 本书特点 ●面向实际应用、贴近实战，使读者能够亲身感受并行计算技术的魅力，书中的许多内容来源于作者的科研和工作成果。 ●为选择本书作为教材的教师提供电子课件，需要的教师可登录华章网站（www.hzbook.com）下载。
前言
基 础 篇
第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 计算p值的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
应 用 篇
第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
