第一章小结本章从并行计算的角度出发,着重讨论当代科学和工程计算问题所要求的高性 能并行计算系统,包括并行计算机系统的互连技术、并行计算机的系统结构模型、存储访问 模型和存储结构组织等。值得注意的是,所介绍的并行计算机系统,与计算机体系结构或并 行处理技术等课程所讲的出发点不一样,在此着重介绍一类并行计算机的体系结构,而不是 某一具体并行机的详细介绍:着重介绍当代能满足高速并行计算要求的主流并行计算机类 (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)技术，它试图将一个最优但相对不快的算
法与另一个非常快但非最优的算法“串接”起来,形成一个快速最优的算法,此法虽不具有 普适性.但对有些问题却效果甚佳;随机法是在算法设计时,引入随机性使得算法在执行时 可以随机地选择下一执行步,从而可望得到平均性能较好的算法(即其复杂度比同一问题的 确定性算法的最坏情况的复杂度要好),随机算法设计简单,但分析较复杂,经常要分析算 法可在多少时间步内以多大的概率结束,用随机法设计的算法,其运行结果也可能是不正确 的,但这种错误的概率应是很小的;贪心法( Greedy Method)是一种最直接的设计技术,其设 计特点是.在算法的每一步都力图确保获得局部最优,这种设计方法的副作用是容易陷入局 部最优。对于组合问题的算法设计技术,有动态规划法( Dynamic Programming),它是在每 判定步,列出多种可能的解,然后按照某种条件,舍弃那些肯定不能导致最优解的局部解, 它和贪心法的区别在于,贪心法仅产生一个判定序列,而动态规划法可能产生很多判定序列, 但依据“最优性原理“,非局部最优解的序列肯定不是最优的,所以不予考虑:回溯法 ( Backtracking)是一种穷举法,在问题求解时常使用深度优先搜索( Depth- First searching)快, 在搜索过程中,一旦碰到某个无法搜索下去的分支,就向其父节点回溯,再搜索该父节点的 其它分支,如果所有的分支节点均无希望的解,则再向上追溯,如此等等,回溯法虽提供了 一种规律性求解的方法,但其时间复杂度较高:分支界限法 Branch and bound)与回溯法颇 类似.但它是基于广度优先搜索( Breadth- First searching)法,它利用部分解的最优性信息, 避免考虑那些不能导致最优的解,以加快问题的求解,其解题过程是:对解集合反复进行分 支,即反复构造其子集合,每次分支时都对所得到的子集合计算最优解的界,若它不能优于 当前已知的最优解,则对此子集合就不再进行分支,否则继续分支,以探索更好的解,直到 所得的子集合仅有一个解为止。 第七章小结本章已经描述了并行算法设计的四个步骤:首先将给定问题划分成一些小的任 务,划分方法可以使用域分解法或功能分解法;其次分析诸任务之间的通信需求,通信可以 是局部的和全局的,静态的和动态的,结构化的和非结构化的以及同步的和异步的:然后使 用组合方法.在尽可能保持灵活性的同时,减少通信和开发成本:最终以最小化总执行时间 为目标将诸任务分配给处理器,使用负载平衡和任务调度技术可以改善映射的质量,在每个 设计步骤之后均列出了相应的设计检验推则以评价设计的好坏 经过上述四个步骤设计出的并行算法,在开始编码实现之前尚须考虑以下几件事:对算 法进行性能分析以选得好的算法,根据要求证实所作的设计是否满意,考虑算法具体实现时 的代价和代码重用的可能性:最终考虑如何将算法装配到一个更大的系统中去 第十章小结线性代数方程组的求解在科学和工程计算中应用非常广泛,这是因为很多科学 与工程问题的计算,最终大都可以化为线性代数方程组的求解。本章主要讨论最基本的线性 方程组的求解,包括三角形方程组、三对角方程组、稠密和稀疏线性方程组等的经典解法。 线性代数方程组的数值解法通常有两种:直接法和迭代法。直接法,又称消元法,是利 用矩阵变换技巧,将一般的系数矩阵化为特殊形式(如上三角和对角形式)的矩阵以对方程组 消解。其优点是可以预先估计运算量,并可得到问题的推确解,但由于实际计算过程中总存 在着舍入误差,因此直接法得到的结果并非绝对精确,并且还存在着计算过程的稳定性问题 迭代法是一种逐步求精的近似求解过程,此法一般总是假定方程组中的系数a≠0(i 1,…,n)。其优点是简单,易于计算机编程,但它存在着迭代是否收敛和收敛快慢的问题 迭代求解的过程是,先给定初始解,然后逐次迭代下去,且理论上讲,每次迭代的结果都 应改善前一次的计算结果。迭代过程由预先给定的精度要求来控制,但由于方程组的准确解 般是不知道的,因此判断某次迭代是否满足精度要求是困难的,通常我们总是认为当相邻 两次迭代值ⅹ(k)与x(k-1)也很接近时,x与x(k)也很接近,因此就可直接用条件
法与另一个非常快但非最优的算法“串接”起来，形成一个快速最优的算法，此法虽不具有 普适性．但对有些问题却效果甚佳；随机法是在算法设计时，引入随机性使得算法在执行时， 可以随机地选择下一执行步，从而可望得到平均性能较好的算法(即其复杂度比同一问题的 确定性算法的最坏情况的复杂度要好)，随机算法设计简单，但分析较复杂，经常要分析算 法可在多少时间步内以多大的概率结束，用随机法设计的算法，其运行结果也可能是不正确 的，但这种错误的概率应是很小的；贪心法(Greedy Method)是一种最直接的设计技术，其设 计特点是．在算法的每一步都力图确保获得局部最优，这种设计方法的副作用是容易陷入局 部最优。对于组合问题的算法设计技术，有动态规划法(Dynamic Programming)，它是在每 一判定步，列出多种可能的解，然后按照某种条件，舍弃那些肯定不能导致最优解的局部解， 它和贪心法的区别在于，贪心法仅产生一个判定序列，而动态规划法可能产生很多判定序列， 但依据“最优性原理“，非局部最优解的序列肯定不是最优的，所以不予考虑：回溯法 (Backtracking)是一种穷举法，在问题求解时常使用深度优先搜索(Depth-First Searching)快， 在搜索过程中，一旦碰到某个无法搜索下去的分支，就向其父节点回溯，再搜索该父节点的 其它分支，如果所有的分支节点均无希望的解，则再向上追溯，如此等等，回溯法虽提供了 一种规律性求解的方法，但其时间复杂度较高；分支界限法(Branch and Bound)与回溯法颇 类似．但它是基于广度优先搜索(Breadth-First Searching)法，它利用部分解的最优性信息， 避免考虑那些不能导致最优的解，以加快问题的求解，其解题过程是：对解集合反复进行分 支，即反复构造其子集合，每次分支时都对所得到的子集合计算最优解的界，若它不能优于 当前已知的最优解，则对此子集合就不再进行分支，否则继续分支，以探索更好的解，直到 所得的子集合仅有一个解为止。 第七章小结 本章已经描述了并行算法设计的四个步骤：首先将给定问题划分成一些小的任 务，划分方法可以使用域分解法或功能分解法；其次分析诸任务之间的通信需求，通信可以 是局部的和全局的，静态的和动态的，结构化的和非结构化的以及同步的和异步的；然后使 用组合方法．在尽可能保持灵活性的同时，减少通信和开发成本；最终以最小化总执行时间 为目标将诸任务分配给处理器，使用负载平衡和任务调度技术可以改善映射的质量，在每个 设计步骤之后均列出了相应的设计检验推则以评价设计的好坏。 经过上述四个步骤设计出的并行算法，在开始编码实现之前尚须考虑以下几件事：对算 法进行性能分析以选得好的算法，根据要求证实所作的设计是否满意，考虑算法具体实现时 的代价和代码重用的可能性；最终考虑如何将算法装配到一个更大的系统中去。 第十章小结 线性代数方程组的求解在科学和工程计算中应用非常广泛，这是因为很多科学 与工程问题的计算，最终大都可以化为线性代数方程组的求解。本章主要讨论最基本的线性 方程组的求解，包括三角形方程组、三对角方程组、稠密和稀疏线性方程组等的经典解法。 线性代数方程组的数值解法通常有两种：直接法和迭代法。直接法，又称消元法，是利 用矩阵变换技巧，将一般的系数矩阵化为特殊形式(如上三角和对角形式)的矩阵以对方程组 消解。其优点是可以预先估计运算量，并可得到问题的推确解，但由于实际计算过程中总存 在着舍入误差，因此直接法得到的结果并非绝对精确，并且还存在着计算过程的稳定性问题。 迭代法是一种逐步求精的近似求解过程，此法一般总是假定方程组中的系数 aii ≠ 0 (i = 1,…,n)。其优点是简单，易于计算机编程，但它存在着迭代是否收敛和收敛快慢的问题。 迭代求解的过程是，先给定初始解，然后逐次迭代下去，且理论上讲，每次迭代的结果都 应改善前一次的计算结果。迭代过程由预先给定的精度要求来控制，但由于方程组的准确解 一般是不知道的，因此判断某次迭代是否满足精度要求是困难的，通常我们总是认为当相邻 两次迭代值 xi(k)与 xi(k-1)也很接近时，xi 与 xi(k)也很接近，因此就可直接用条件
maxx,(k)-x,(k-1)<E来判定迭代是否终止。迭代法在求解稀疏线性方程组时经常使用, Issn 而很多的偏微分方程经差分化后也可化为稀疏线性方程组,所以在偏微分方程数值求解中迭 代法使用得尤其广泛。 第十一章小结本章所讨论的快速傅里叶变换是一类最重要的快速离散变换,此类变换还有 数论变换、多项式变换、卷积和城波等。其中,数论变换物理意义欠弱,所以应用尚不甚广 泛,而卷积与滤波计算在数字信号处理中应用得十分广泛,因为许多数字信号处理问题都要 求高速滤波能力(所谓滤波实际上是指将某些输入序列进行变换,使其具有某些预定的性 质)。但本书限于篇幅就不再讨论它们了 此外,本章所讨论的FFT算法是基-2FFT算法,即将输入序列分为奇数下标和偶数 下标两个n/2点的序列进行进归计算。工程实用中,还常用到基-4FFT算法,即将输入序 列分成四个n/4点的序列进行递归计算,其计算量(乘法和加法)比基一2算法有所减少。如 果n不是单一基的幂,则可以试用混合基算法,要是算法设计得当,则可望达到最佳效果 同样限于篇幅,本章也不予以讨论。 最后,本章所讨论的FFT算法是一维FFT算法,如果输入元素是ahn2形式的二维复序列, 则可相应地定义二维FFT变换(Two- Dimensional FFT Transform),它在光学、地震以及图像 信号处理等方面起着重要的作用。也是限于篇幅,不再予以讨论
1 max ( ) ( 1) i n x k x k i i − − 来判定迭代是否终止。迭代法在求解稀疏线性方程组时经常使用， 而很多的偏微分方程经差分化后也可化为稀疏线性方程组，所以在偏微分方程数值求解中迭 代法使用得尤其广泛。 第十一章小结 本章所讨论的快速傅里叶变换是一类最重要的快速离散变换，此类变换还有 数论变换、多项式变换、卷积和城波等。其中，数论变换物理意义欠弱，所以应用尚不甚广 泛，而卷积与滤波计算在数字信号处理中应用得十分广泛，因为许多数字信号处理问题都要 求高速滤波能力(所谓滤波实际上是指将某些输入序列进行变换，使其具有某些预定的性 质)。但本书限于篇幅就不再讨论它们了。 此外，本章所讨论的 FFT 算法是基－2 FFT 算法，即将输入序列分为奇数下标和偶数 下标两个 n/2 点的序列进行进归计算。工程实用中，还常用到基－4 FFT 算法，即将输入序 列分成四个 n/4 点的序列进行递归计算，其计算量(乘法和加法)比基－2 算法有所减少。如 果 n 不是单一基的幂，则可以试用混合基算法，要是算法设计得当，则可望达到最佳效果。 同样限于篇幅，本章也不予以讨论。 最后，本章所讨论的 FFT 算法是一维 FFT 算法，如果输入元素是 an1,n2 形式的二维复序列， 则可相应地定义二维 FFT 变换(Two-Dimensional FFT Transform)，它在光学、地震以及图像 信号处理等方面起着重要的作用。也是限于篇幅，不再予以讨论