第一章小结本章从并行计算的角度出发,着重讨论当代科学和工程计算问题所要求的高性 能并行计算系统,包括并行计算机系统的互连技术、并行计算机的系统结构模型、存储访问 模型和存储结构组织等。值得注意的是,所介绍的并行计算机系统,与计算机体系结构或并 行处理技术等课程所讲的出发点不一样,在此着重介绍一类并行计算机的体系结构,而不是 某一具体并行机的详细介绍:着重介绍当代能满足高速并行计算要求的主流并行计算机类 (SMP、MPP、COW等等),而对历史上曾占主导地位的SMD和PVP则不作重点介绍;同 时所选讲的内容和叙述的深浅程度都是为了并行算法的设计和并行编程的需要,而对有些相 关知识的介绍,也只能点到为止.不能深入全面展开讨论,尤望读者能以此为线索,进一步 迫踪和深入地学习 第二章小结本章讨论了当代共享存储多处理机、分布存储多计算机和机群三种并行计算机 系统。MPP和COW之间的界线渐趋模糊,例如 IBM SP2被视为MPP,但它具有机群结构 (除了使用高性能开关网络作为通信网络外)。COW的性能/价格比优于MPP,所以机群技术 是发展可扩放并行计算的主流趋势。 第三章小结并行计算的性能与所使用的并行计算机本身的性能有关,所以研究并行计算的 性能先了解以下并行机的一些基本性能指标也是很必要的。在并行系统上进行计算的主要目 的就是要加速整个计算的过程,所以研究并行计算(并行算法、并行程序)的加速比性能是 最根本的。随着计算负载的增加和机器规模的扩大,研究并行计算的性能是否能随处理器书 目的增加而按比例的增加(这就是所谓的可扩放性)也是很重要的。为了客观、公正的评估 计算机性能,提高并行机的使用水平和效率,减少用户引进和购买高性能计算机的盲目性, 所以了解掌握一些基本的基准测试程序也是很必需的。本章对以上四方面的问题逐一做了简 要讨论。 第四章小结并行计算模型是设计和分析并行算法的基础。PRAM模型由于过于抽象而不 能很好地反映并行算法的实际运行性能,所以硏究考虑通信、同步等因素从而能较真实反映 并行算法运行性能的所谓更实际的计算模型( More Realistic Computation Models成为当今并 行算法硏究的主要动向之一。本节所讨论的 APRAM、BSP和LogP等模型就是属于这种模 型,此外还有C3模型。但过去几年来,主要是从理论分析的角度,来研究它们之上的一些 典型的并行算法的设计与分析;而近期的研究热点却从这些模型上的算法研究转向这些模型 的编程的研究,即从理论研究转向实际应用。因为任何并行算法的应用都最终落实到具体的 编程上,所以这种转变是顺应应用要求的。例如,一些研究考就为BSP模型构造了一些函 数库,这些BSP库就是一些为程序员编写BsP应用程序(这些应用程序按照BSP的超级计算 步的风格进行编写)所提供的一组简单有力的编程界面函数,此函数可改善程序的可移植性 而不依赖于具体的并行机结构。尽管PVM和MPI等也是目前可供使用的开发可移植并行代 码的方法,但它们的功能过于复杂而不易被掌捏,且它们均没有为编程者提供能设计高效代 码的成本函数,而像BSP模型却提供了简单和可定量分析程序运行时间的成本函数。因此 研究基于这些实用计算模型的并行编程方法是非常有意义的 第六章小结本章所介绍的都是并行算法设计的最基本的技术,远非所有的设计技术。这些 技术虽具有一定的普适性,但也并非对所有问题均行之有效,况且也不全面,同时也只能作 为设计并行算法的一般性指南,绝非是可直接引用的手册。其它的设计技术还有破对称 ( Symmetry Breaking)技术,它是打破某些问题的对称性的一种设计方法,在图论问题和随机 算法中经常使用:加速级联( Accelerated Cascading)技术,它试图将一个最优但相对不快的算第一章小结 本章从并行计算的角度出发，着重讨论当代科学和工程计算问题所要求的高性 能并行计算系统，包括并行计算机系统的互连技术、并行计算机的系统结构模型、存储访问 模型和存储结构组织等。值得注意的是，所介绍的并行计算机系统，与计算机体系结构或并 行处理技术等课程所讲的出发点不一样，在此着重介绍一类并行计算机的体系结构，而不是 某一具体并行机的详细介绍；着重介绍当代能满足高速并行计算要求的主流并行计算机类 (SMP、MPP、COW 等等)，而对历史上曾占主导地位的 SMD 和 PVP 则不作重点介绍；同 时所选讲的内容和叙述的深浅程度都是为了并行算法的设计和并行编程的需要，而对有些相 关知识的介绍，也只能点到为止．不能深入全面展开讨论，尤望读者能以此为线索，进一步 迫踪和深入地学习。 第二章小结 本章讨论了当代共享存储多处理机、分布存储多计算机和机群三种并行计算机 系统。MPP 和 COW 之间的界线渐趋模糊，例如 IBM SP2 被视为 MPP，但它具有机群结构 (除了使用高性能开关网络作为通信网络外)。COW 的性能/价格比优于 MPP，所以机群技术 是发展可扩放并行计算的主流趋势。 第三章小结 并行计算的性能与所使用的并行计算机本身的性能有关，所以研究并行计算的 性能先了解以下并行机的一些基本性能指标也是很必要的。在并行系统上进行计算的主要目 的就是要加速整个计算的过程，所以研究并行计算（并行算法、并行程序）的加速比性能是 最根本的。随着计算负载的增加和机器规模的扩大，研究并行计算的性能是否能随处理器书 目的增加而按比例的增加（这就是所谓的可扩放性）也是很重要的。为了客观、公正的评估 计算机性能，提高并行机的使用水平和效率，减少用户引进和购买高性能计算机的盲目性， 所以了解掌握一些基本的基准测试程序也是很必需的。本章对以上四方面的问题逐一做了简 要讨论。 第四章小结 并行计算模型是设计和分析并行算法的基础。PRAM 模型由于过于抽象而不 能很好地反映并行算法的实际运行性能，所以研究考虑通信、同步等因素从而能较真实反映 并行算法运行性能的所谓更实际的计算模型(More Realistic Computation Models)成为当今并 行算法研究的主要动向之一。本节所讨论的 APRAM、BSP 和 LogP 等模型就是属于这种模 型，此外还有 C 3 模型。但过去几年来，主要是从理论分析的角度，来研究它们之上的一些 典型的并行算法的设计与分析；而近期的研究热点却从这些模型上的算法研究转向这些模型 的编程的研究，即从理论研究转向实际应用。因为任何并行算法的应用都最终落实到具体的 编程上，所以这种转变是顺应应用要求的。例如，一些研究考就为 BSP 模型构造了一些函 数库，这些 BSP 库就是一些为程序员编写 BsP 应用程序(这些应用程序按照 BSP 的超级计算 步的风格进行编写)所提供的一组简单有力的编程界面函数，此函数可改善程序的可移植性 而不依赖于具体的并行机结构。尽管 PVM 和 MPI 等也是目前可供使用的开发可移植并行代 码的方法，但它们的功能过于复杂而不易被掌捏，且它们均没有为编程者提供能设计高效代 码的成本函数，而像 BSP 模型却提供了简单和可定量分析程序运行时间的成本函数。因此 研究基于这些实用计算模型的并行编程方法是非常有意义的。 第六章小结 本章所介绍的都是并行算法设计的最基本的技术，远非所有的设计技术。这些 技术虽具有一定的普适性，但也并非对所有问题均行之有效，况且也不全面，同时也只能作 为设计并行算法的一般性指南，绝非是可直接引用的手册。其它的设计技术还有破对称 (Symmetry Breaking)技术，它是打破某些问题的对称性的一种设计方法，在图论问题和随机 算法中经常使用；加速级联(Accelerated Cascading)技术，它试图将一个最优但相对不快的算