并行计算导论——张林波图书在版编目(CIP)数据并行计算导论/张林波等编著.一北京:清华大学出版社,2006(高等院校信息与计算科学专业系列教材)ISBN7-302-12760-3Ⅰ.并.IL张….IIL并行算法-高等学校一教材IV.TP301.6(8132?)中国版本图书馆CIP数据核字(2006)第026693号内容简介本书是并行计算,特别是分布式并行计算环境和消息传递并行编程的入门教材,目的是促进并行计算技术在我国的应用。书中介绍了并行计算的基础知识、Linx/UNIX的基本使用、基于Linx机群的并行计算平台的建立、并行算法的设计和MPI消息传递并行编程的基本概念与方法。书中还提供了一批典型科学计算问题的并行算法与程序设计实例,介绍了一些当前国际上流行的科学计算软件工具及平台。本书力求从简单入手,循序渐进,读者不需要有太多的预备知识,在逐步学习使用的过程中学会利用并行计算解决自己学习和工作中的问题。本书侧重介绍高性能计算的实用技术,可作为信息技术与计算专业的专业基础课教材,也可作为其他理工科非计算机专业的并行计算课程教材。此外,本书还可作为有关Linⅸ机群建造、MI消息传递并行算法设计与编程及常用高性能科学计算软件的参考书使用前言随着高性能并行计算机,尤其是Linx微机机群在我国应用部门、大学和科硏机构的普及,并行计算已经成为许多科研和工程技术人员亟待掌握的一项研究开发手段。但是,在我国,对并行计算的基本原理、并行算法设计、并行程序的设计与实现、并行性能优化以及一些成熟的科学计算软件工具箱、库等的普及教育和推广应用还明显不够,大大制约了并行计算技术在科学研究与工程设计中应有作用的发挥。本书是并行计算,特别是分布式并行计算环境及消息传递并行编程的入门教材。它侧重于介绍利用现有的微机条件建立并行计算的软硬件环境,以及并行算法设计、MPI消息传递并行编程的基本概念与方法。作者希望通过本书,一方面加强和规范普通高校的并行计算课程,另一方面在科学研究与工程应用领域普及并行计算技术,推进高性能计算技术的应用。全书分为三部分,共包括九章和两个附录第1部分包括第1章至第4章,主要介绍并行计算的基础知识。第1章讲述并行计算机的发展历史、并行计算机体系结构以及并行计算、并行算法设计的基本名词和概念。第2章介绍 Linux操作系统的安装、Linx操作系统的基本命令和工具,以及 Linux操作系统中的程序开发、调试。第3章讲述标准消息传递并行编程接口MPI,并介绍如何利用目前流行的免费MPI软件 MPICH和 Linux系统在局域网上建立实用的并行计算平台。考虑到本书的篇幅限制并鉴于国内已有一些专门关于MPI编程的书,本书中关于MPI编程的部分仅限于讲述MPI编程的基本概念和介绍一些MPI的重要函数,同时在附录B中提供MPI变量和函数的完整参考方便读者查询。第4章讲述程序性能评价与优化方面的有关知识。第2部分包括第5章至第9章。在这部分中,通过一些典型并并行计算导论行算法设计及并行程序实现的实例,介绍并行算法设计的基本思想与MPI并行程序实现的基本技巧。第5章介绍一个自适应数值积分算法的并行算法设计与MPI并行程序实现。第6章介绍矩阵计算的并行算法与程序。第7章介绍快速傅里叶变换(FFT)的并行算法及在消息传递并行环境中的实现方法。第8章以二维 Poisson方程5点差分格式的点 Jacobi迭代算法为例,介绍基于区域分解方法的并行算法设计与并行程序编制。第9章通过二维热传导方程的ADI格式介绍基于流水线方法的并行算法设计的基本思想及实现方法。第3部分由两个附录构成。附录A介绍一些重要的高性能计算、并行计算的工具和平台,包括BLAS, LAPACK, ScalapacK,FFTW和 PETSC。附录B是一个为方便读者速查而整理的较完整的MPI参考手册书的最后是MPI函数、变量索引和名词、概念索引。大部分章后面附有习题,一部分习题是为了巩固、加深对该章内容的理解,而另一部分习题则是对正文内容的扩充。本书可作为一本课堂使用或者自学使用的教材,在编写过程中考虑了适应尽可能广的读者群体,以便读者不需要很多的预备知识,就能够在逐步的使用过程中掌握利用并行计算技术解决自己学习和工作领域中的计算问题的知识和技术。本书的特点是:注重实效性,使得读者能够学到具体有用的知识和技术,而不必首先建立对整个知识系统结构的认识;强调实践性,读者应该一边学习一边操作,认真分析和重复书中提供的具体例子,将介绍的知识应用于各自的专业领域中;强调普适性,侧重于科学计算领域面临的一些共性问题的并行计算方法与技术,并注意介绍一些国际流行的库、软件和工具箱。希望读者能够结合自己的实际情况,练习简单微机机群环境建立的实际操作及 Linux系统的管理和使用,与自己的工作领域相结合编写具体模型问题的例子程序,举一反三,学以致用,通过本书的学习,迅速掌握并行计算机的使用与编程,并且能够利用已有条件采用微机机群技术自行建立实验性或实用的并行计算环境,用于解决实际问题。本书的目的是介绍运用高性能并行计算机深入解决科学计算问题所必需掌握的并行计算原理、并行算法设计、并行程序设计和性能优化等方面的基本知识和技术手段。鉴于此,本书写作过程中尽量避免枯燥的系统介绍,而是侧重于培养读者解决实际问题的能力,并注意介绍编著者在这方面的经验。限于作者的学识以及时间,书中错误与片面之处在所难免,恳请读者不吝指正。在本书的作者中,张林波(中国科学院数学与系统科学研究院)编写了第3章、第5章、第9章和附录B,以及第2章、第4章和附录A中的部分内容;迟学斌(中国科学院计算机网络信息中心)编写了第6章、第7章,以及附录A中的部分内容;莫则尧(北京应用物理与计算数学研究所)编写了第1章、第4章和第8章;李若(北京大学数学科学学院)编写了第2章本书中的程序实例可以从下面的网址下载:ftp: //ftp. cc. ac. cn/pub/home/zlb/bxjsbook/code/鸣谢:下述人员提供了附录A中的部分内容:程强(A.5)、陈江(A.3)、赵韬(A.2)、谷同祥(A.4),在此一并致谢。作者2006年7月17日于北京并行计算导论目录第1部分基础知识第1章预备知识1.1并行计算的主要研究目标和内容1.1.1什么是并行计算1.1.2并行计算的主要研究目标和内容113推动并行计算发展的主要动力1333469912并行计算机发展历史121应用需求的推动作用12270年代1012.380年代早期1012480年代中期1012.580年代后期111.2.690年代早期12.790年代中后期1312.82000年到当前171.3并行机体系结构20131结点211.3.2并行机互联网络拓扑结构231.3.3多级存储体系结构341.3.4访存模型.4113.5并行机分类441.4操作系统与并行编程环境501.4.1进程、进程间通信与线程50并行计算导论1.4.2并行编程环境551.5并行算法591.5.1并行算法的分类1.52并行算法的发展阶段习题第2章Linuⅹ操作系统与程序开发环境6321 Linux安装与使用入门6321.1 Linux系统的安装632.1.2基本使用与管理6722 Linux基本命令和概念77221一些基本命令772.2.2 Shell223文本文件处理1302.3程序开发环境.13923.1第一个程序(C程序)140232 Fortran程序的开发15023.3软件开发156第3章消息传递编程接口MPI1753. MPICH安装与程序编译、运行、调试.1763.1.1单机环境下 MPICH的安装1763.1.2机群环境下 MPICH的安装1823.2MPI编程189321MPI编程的基本概念.18932.2程序基本结构1913.2.3MPI的原始数据类型1933.2.4点对点通信函数与通信模式193