译 者 序 目前,计算科学已经继两门传统科学(理论科学和实验科学)之后成为第三门科学。并行处理是计算科学的重要内容,是实现高性能计算的重要途径,是并行算法设计、并行程序设计语言和并行计算机体系结构三者相结合的产物,是一门计算机科学与其他工程学科相结合的处于发展过程中的交叉学科,其研究重点在于挖掘各个计算层次的并行性。高性能并行机的处理器有数以千百计,处理器个数的增多给并行处理带来很多技术难题。考虑并行机的CPU速度、网络结构与性能、多级存储结构等特点,研究适合在高性能并行机上执行的新并行算法、新技术,充分提高解题的精度和速度,增大问题求解规模,对于大量的挑战性问题的数值模拟具有十分重要而紧迫的应用需求。相对而言,并行处理是一门年轻的学科,它已经成为一门相对独立和值得探讨的基础学科。随着国内外各种并行机体系结构的不断发展,并行计算机应用领域的不断扩大和深入,并行处理引起了各行各业科学家的关注,并投入大量精力进行研究。 本书系统地介绍了并行处理的基本原理,把并行算法设计、并行程序设计语言和并行计算机体系结构三者结合进行论述,交叉讨论了并行计算的各个方面,更强调了它们之间的相互关系,研究了各个部分对整体性能的影响。前7章深入地讨论了并行算法设计、向量算法和体系结构、多处理机、数据流结构、针对各种机器的并行程序设计语言、同步和通信机制、互连网络、数据相关性和编译器的优化技术。其余的4章主要对本书第一部分的内容进行了更深入的探讨,主要内容包括同步实现数据共享及其实现方法对性能的影响、并行处理机体系结构和程序性能、并行程序的时间复杂性以及并行I/O。 本书内容丰富全面,结构安排十分精当。重点讨论了并行处理核心原理的各个方面,并将涉及并行处理的表层信息抽象成理论,在论述理论分析结果的同时,给出了丰富的示例、程序和图表。通过对本书的学习,学生们将能够胜任并行应用程序的设计和实现,评价并行程序和体系结构的性能,更重要的是能够独立地在本领域内继续发展和进步。 全书由陈曙辉组织翻译,由于译者水平有限,书中难免存在一些不足和错误之处,敬请广大读者批评指正。 前 言 致学生 老师在讲授计算方法时,通常采用串行的观点。算法按照计算步骤进行组织,程序按照逐条指令的方式进行编写,而计算机则按照一系列的微操作指令执行。尽管串行模式也能够解决问题,但是以并行的方式让计算机同时执行多个操作可以极大地获得性能上的提高。提高计算速度的基本方法有两种:一是提高硬件潜在的时钟频率;二是让多个操作并行执行。其中利用并行操作来提高计算速度是更有前景,因为当任务变得庞大时,将会有更多的操作可以并行执行。要实现这种潜在的并行性,必须让以下三方面同时起作用:一是计算方法必须涉及许多相互独立的操作;二是编程语言必须可以定义并行操作,或者自动地找出可以并行执行的操作;三是运行并行程序的计算机的体系结构必须能够同时执行多个操作。 并行处理是算法设计、程序设计语言和计算机体系结构三者相结合的产物,其目的是为了计算机系统能够更快地完成对应用问题的计算。并行处理基本原理的出现正是源于对上述计算主题的理解以及它们之间的相互结合所带来的高性能。为了较好地理解并行处理,必须具备一些计算机设计和体系结构、编程语言和机器代码的基础知识,而且还必须具备算法结构的基础知识。本书的一些章节集中讨论了体系结构、编程语言和算法,但它们之间并没有明显的区分。这3部分共同构成并行处理这门学科的概念基础。我们希望读者具备算法和编程的基本知识,为了说明并行处理的真正目的(为了获得更高的性能),必须知道计算机是在机器语言级执行程序的,同时要求读者理解构成计算机体系结构的各个硬件部件的组织方式。此外,在该领域中的一些基本经验也是阅读本书的必备前提。 致教师 本书的目的就是要全面而综合地介绍并行处理的基本原理。要想学习知识既有深度又有广度,同时掌握成功设计和开发并行应用程序所需的专门技术,计算机体系结构、算法和语言知识的整合是关键。本书的组织与编写在这些主题领域之间建立起紧密的联系。在讨论了算法设计之后,本书还进一步讨论了每一种算法设计对于并行体系结构性能的影响。 技术的不断革新,新的体系结构、新式程序设计语言和新系统的不断涌现要求我们对并行处理有一个基本的了解。本书注重对于基本概念的阐述,而不是对于大量最新发展趋势的说明。本书的结构安排十分合理,每一个章节都是前一章节的自然延续。本书在论述每一主题时,都会尽早提出研究主题,从而促使读者进一步地学习,并对研究主题有一个全局的把握,明确学习什么和怎样学习。如果不是把最新的体系结构、编程语言和系统作为讲授基本概念的一个工具,而仅仅是为了学习这些时髦的东西,那么学习过程将很困难,而且您会发现它们很快就会过时。如果读者没有达到忘我的境界,并且对研究主题仍感困惑的话,那么要想学到精髓是很困难的。在任何情况下,在深入到核心内容之前,剥开一些表层的附加信息和特性是很有必要的。例如,一种编程语言有必要提供众多的结构体吗?是不是只有一些是必需的,而另外一些仅仅是为了方便使用而额外提供的呢?实现它们是为了满足特定体系结构的性能要求,还是为了提供可移植性?这些结构体的实现具有相关性吗?它们的性能会随着计算机体系结构的不同而相差很大呢?仅仅通过了解机器和语言,要想完全理解这些权衡和概念的内涵是不可能的。一旦理解了这些基本概念,就可以把它们应用到任何体系结构、系统和语言中。 并行处理是一个相对年轻的学科,我们相信,该学科已经能够从一些独立的系统中分离出来,而成为一个相对独立和值得探讨的基础学科。我们主要通过体系结构的特点、系统的特性、语言的结构体、算法的设计和实现来展示一些基本原理,而对于这些,我们尽可能地以一种与特定体系结构、系统和编程语言无关的方式进行讲解。在有些情况下,我们涉及到一些机器、语言或者系统的原型,因为这样便于我们引入基本的概念。但是,作为主要的实例,我们有意避免把每一个主题都扩展到一些具体的机器或语言上,这样做使我们可以把主要的精力放在基本原理上。 尽管本书不是并行程序设计的教科书,但是对于书中引入的每一类主要的并行概念都是通过一种具体的编程语言来表述的,书中选择Fortran作为基本语言。很多研究并行处理的文献都是基于Fortran的,大量并行处理科学的计算程序和程序员都使用Fortran。另外,Fortran是一种接近机器级而又很简单的高级语言,相对于具有复杂特性的、用户界面友好的高级语言而言,在各种不同体系结构的计算机上,Fortran更便于观察和解释语句的执行效果,Fortran程序员对编程模式和程序的设计、实现以及执行能有更好的控制。Fortran是静态语言。因此,相对于动态语言或者提供动态属性的语言而言,Fortran程序员不必太多关注它们的高级特性和并行性能的影响。语言的简单性更有利于我们重点关注并行概念和并行结构体,Fortran支持多维数组的计算,这对于向量处理具有特别重要的意义。在整本书中,我们都使用同一种基本语言,这有利于表达的一致性,读者不必在语言之间来回切换,这更有利于集中精力关注并行问题。 本书根据并行处理领域多年教学和科研经验组织和设计的,主要读者对象是计算机科学或者计算机工程与应用专业高年级学生和研究生。通过本书的学习,读者将能够胜任并行应用程序的设计和实现,评估并行程序和体系结构的性能,更重要的是,通过独立学习新的并行环境,能够培养学生独立开发的技能。教师主要的任务之一就是培养学生在感兴趣的领域继续发展和取得进步的能力。本书还将给教师提供一些综合性的材料,这些综合性的材料能够培养学生更具创造力并获得更大的成功。 本书主要内容 前7章的内容可以作为并行处理第一学期的课程,这7章比较深入地介绍了并行算法设计、向量、多处理机、数据流结构、针对各种机器的并行程序设计语言、同步和通信机制、互连网络、数据相关性和编译器的优化技术。其余的4章主要是对本书第一部分的内容进行了更深入的探讨。主要讨论了各种同步和通信方式的实现、其实现方法对性能的影响、机器体系结构和程序性能的解释、程序的行为对性能的影响以及并行I/O。这一部分可以作为第二学期的课程,学生可以学习到如何分析机器体系结构、并行程序和并行系统、并且能够深入地理解各部分对整体性能有何影响。从第8章至第11章所讨论的主题中,我们可以得到许多高级研究项目的思想。 下面的图显示了各章之间的相互关系,以及它们所涵盖的专业领域的重点。 各章主要内容 第1章简要回顾了并行性在计算机体系结构中的发展历程。该章介绍了向量处理、多处理机和算法中的并行操作的基本概念,为后续章节的内容建立了一个基本的框架。 第2章介绍了数据相关性的一些重要思想。使用前缀计算(prefix computation)来说明算法的一些特性,这些特性使得利用不同的计算方法来完成同一个计算问题时,所获得的并行性是不同的。 第3章介绍了多个数据项并行执行同一操作的应用。该章引入了对线性代数中一些简单算法的讨论,同时给出了一个机器语言级的体系结构,其中包含了向量操作。之后还讨论了Fortran 90,Fortran 90是一种对机器级向量处理特性具有高级支持的语言。最后还对流水向量(pipelined vector)处理也进行了讨论。 第4章简要讲述了多处理机体系结构的组织,同时说明了共享存储器和分布式存储器多处理机的区别。并通过描述对串行程序设计的扩展,进一步讨论了共享的存储器,因为必须利用它来协调多个进程共同完成一个任务。利用扩展的OpenMP Fortran来说明高级结构体(construct),这些高级结构体是用来支持共享存储器多处理机的计算的。该章也介绍了具有流水功能的MIMD或者是多线程体系结构的基本知识。 第5章描述了分布式存储器多处理机,在这样一个体系结构中,通过消息传递的观点主要讲解了数据通信的主导作用。介绍了消息的显式发送与接收的有关编程问题,并且利用消息传递接口(MPI)来说明支持这种程序的高级语言。介绍了与分布式共享多处理机相关的Cache一致性的基本概念。 第6章比较深入地讨论了互连网络,包括用来连接向量处理机的互连网络以及连接共享存储器和分布式存储器多处理机的互连网络,比较了动态网络和静态网络的特点,同时比较了各种网络拓扑结构以及这些拓扑结构的特点,讨论了在NYU巨型机中得到应用的互连网络。 第7章中有关数据相关性的讨论是很重要的,它是从并行算法的结构过渡到程序的结构的基础。它涉及到代码的优化技术和一些与编译器编写者相关的主题,编译器编写者担负着为并行计算机生成代码的任务。该章还介绍了数据流语言和体系结构的概念,有了这些概念,就可以从编程语言和机器中消除不必要的相关性。 第8章扩展了在第4章讨论共享存储器时提到的同步概念,并把其和第5章中强调的数据传输的观点结合起来,深入地探讨了同步中的关键问题,涉及到了协作通信的同步、管理共享事务、等待机制、以及如何证明一个同步机制是可以正确地实现的。 第9章集中讨论了性能问题,这些问题在前面的章节中时常被提到。该章讨论了各种性能模型,通过对统计数据和实际系统的实例研究说明了它们的作用。还讨论了并行机制的不同调度和不同实现对运行效果的影响。 第10章讨论了对并行程序执行的性能与并行程序的一些局部特性的关系。通过对实际系统的实验来说明性能特性模型,从单个高速缓存系统,具有分布式高速缓存的多处理机系统到消息传递系统,都进行了局部性测试。 第11章对I/O操作并行性的多个方面进行了讨论。对作为并行I/O硬件的并行访问磁盘阵列(RAID)进行了讲解,介绍了I/O操作的相关性,讨论了对文件的并行输入输出方法,最后,利用MPI-IO,讨论了对多处理机中多个I/O操作的并行性。