第十章高性能计箕和并行算法 §10.1引言 在过忐的近三十年间。仉经历了计机科学和抆术的迅 敬展。具体褒现在市场上计算机的性能价格比到迅遠地提高。 高性能计犷机的概念并元明确的定义,一舭认为犷滾度非 常快的计算机就可以认为是而性能计算机。严格地讲,高性能计 算机是一个所有最先进的硬件,件,网络和算法的錄合概念, “高性能”的椓渔是隨普救术的发晨而墩晨的。 高性能计犷系统中最为关鍵的景是单处理器的大计犷 度,存贮器访问遠度和内部处理器通讯遠度,多处理器系统獍定 性,计算能力与价格比,以及机性能普 冯.纽曼“瓶颈” 为了要超这个“瓶颈”人们发展了肃种计算机体系结构和 相关软件技术的应用原则。一个是外行算法( parallelism),另 一个是流水戴术( pipelining)。 际上,这两个原则部与外行有关。奥际上外行的概念有 种:一种是仅仅时间上的并行,称为水能计算机,另一种既是 时间,也是空间上笄行的并行计算机。 流水绕技术是源于工业自动化生产中的流水能操作丸。在 生产瀛水能上,一批广品的一部分安漱完毕以后,进入流水能的 下一段兜成另一部分安任亦:个流水能上同时对产品进行不
第十章 高性能计算和并行算法 §10. 1 引言 在过去的近三十年间，我们经历了计算机科学和技术的迅速 发展。具体表现在市场上计算机的性能价格比得到迅速地提高。 高性能计算机的概念并无明确的定义，一般认为运算速度非 常快的计算机就可以认为是高性能计算机。严格地讲，高性能计 算机是一个所有最先进的硬件，软件，网络和算法的综合概念， “高性能”的标准是随着技术的发展而发展的。 高性能计算系统中最为关键的要素是单处理器的最大计算速 度，存贮器访问速度和内部处理器通讯速度，多处理器系统稳定 性，计算能力与价格比，以及整机性能等。 冯.纽曼“瓶颈”。 为了要超越这个“瓶颈”，人们发展了两种计算机体系结构和 相关软件技术的应用原则。一个是并行算法(parallelism)，另 一个是流水线技术(pipelining)。 实际上，这两个原则都与并行有关。实际上并行的概念有两 种：一种是仅仅时间上的并行，称为流水线计算机，另一种既是 时间，也是空间上并行的并行计算机。 流水线技术是源于工业自动化生产中的流水线操作思想。在 生产流水线上，一批产品的一部分安装完毕以后，进入流水线的 下一段完成另一部分安装任务；整个流水线上同时对产品进行不
同部分的安工作。在并行处理中,瀛水錢技术是一项量耍的养 行执术,目前己经在級计机和工作站上得到广泛的应用, 并行计犷机上算法的具体实视则要复杂得多,要高效用它 就頁不容易。造成逭祥局面的原因是修改算法来垽应流水能操 作,比去适应行计算率易一些。但是。毫无问,向量处理超 级计箕机和并行计犷系统的应用会给们物理学的发昃提供更 多的机過。 由于高性能计算机与当前能够应用的新计算技术相关联,因 而咆与外行算法和流水能技术有着切的联系。 §10.2并行计算机和并行算法 并行计算机是由多个处理器组成(在这些处理器之间还可以 相互逋讯和协调),并能够高遮、高效率地行复杂间题讣算的 计算机系统。并行计箕机的名是相对于串行计算机而言的。 行计算机是指只有单个处理器,顺序执行计算翟序的计算机,世 称为顺序计算机。并行计算作为计箕机技术,是在上世纪70年 代中期提出来的,至今已30年的发晨历史了。该技术的应 用已经带来阜机讣能力的亘大欧选。 为什么戛采用外行计算呢?我们有三个方面的理由: (1)并行计算可以大大加快运算速度,即在更短的时间内完 成相同的计算量,或解决原來根本不能计算的非常复桑
同部分的安装工作。在并行处理中，流水线技术是一项重要的并 行技术，目前己经在超级计算机和工作站上得到广泛的应用， 并行计算机上算法的具体实现则要复杂得多，要高效使用它 就更不容易。造成这样局面的原因是修改算法来适应流水线操 作，比去适应并行计算容易一些。但是。毫无疑问,向量处理超 级计算机和并行计算系统的应用会给我们物理学的发展提供更 多的机遇。 由于高性能计算机与当前能够应用的新计算技术相关联，因 而它与并行算法和流水线技术有着密切的联系。 §10. 2 并行计算机和并行算法 并行计算机是由多个处理器组成（在这些处理器之间还可以 相互通讯和协调），并能够高速、高效率地进行复杂问题计算的 计算机系统。并行计算机的得名是相对于串行计算机而言的。串 行计算机是指只有单个处理器，顺序执行计算程序的计算机，也 称为顺序计算机。并行计算作为计算机技术，是在上世纪 70 年 代中期提出来的，至今已有近 30 年的发展历史了。该技术的应 用已经带来单机计算能力的巨大改进。 为什么要采用并行计算呢？我们有三个方面的理由： (1) 并行计算可以大大加快运算速度，即在更短的时间内完 成相同的计算量，或解决原来根本不能计算的非常复杂
的问题 (2)提高々統的计算机的计算遠度一方面曼到物理上光遠 极限和量子效应的限侧,另一方面计犷机器件产品和村 料的生广曼到加工工艺的限制,其尺寸不可能散得无限 因此我仉只能鞭向外行算法。 (3)并行计算对设鲁的投入較低,既可以节省开文又能兜成 计犷任务。 通常的冯.組曼计算机是属于SISD( Single Instruction Single Data stream computers)单指令单数据流计算机类型计 算机,它的绪袍只有一个处理器,同时可以处理一个单教据流。 其阜數据流是指被处理器从存贮器取出貳写到存贮器上的教据 序列。 外行计算机着采用与某种网络相关的多处理器绪构,则食良 其性能讣到欧瞢。计算机系统的处理器和内夺永有冬种音样的可 能排列。觉仉可以根据一个并行计犷机能够同时执行的指令与处 理数据的多少,将如今广泛使用的结构分成以下类塑 (1)SIMD计算机具有处理器器件阵列,它遭过单个控制单完 来控侧动能设备。这个控侧单元向所有处理器发出相同的执行指 令,隨后所有处理器对迣入的不同教据流选行相同的操作。例如 在SIM外行计算机上做数组的赋值還 X=X+1 即用加法指令对教组Ⅹ的所有元素同时敵加1的操作。可以看出
的问题。 (2) 提高传统的计算机的计算速度一方面受到物理上光速 极限和量子效应的限制，另一方面计算机器件产品和材 料的生产受到加工工艺的限制，其尺寸不可能做得无限 小。因此我们只能转向并行算法。 (3) 并行计算对设备的投入较低，既可以节省开支又能完成 计算任务。 通常的冯.纽曼计算机是属于 SISD(Single Instruction Single Data stream computers) 单指令单数据流计算机类型计 算机，它的结构只有一个处理器，同时可以处理一个单数据流。 其单数据流是指被处理器从存贮器取出或写到存贮器上的数据 序列。 并行计算机若采用与某种网络相关的多处理器结构，则会使 其性能得到改善。计算机系统的处理器和内存条有各种各样的可 能排列。我们可以根据一个并行计算机能够同时执行的指令与处 理数据的多少，将如今广泛使用的结构分成以下类型： (1)SIMD 计算机具有处理器器件阵列，它通过单个控制单元 来控制功能设备。这个控制单元向所有处理器发出相同的执行指 令，随后所有处理器对进入的不同数据流进行相同的操作。例如 在 SIMD 并行计算机上做数组的赋值运算 X=X+1 即用加法指令对数组 X 的所有元素同时做加 1 的操作。可以看出
在SIM并行计算机上特别适合选行向量(数组)的算,它 绪枘可以以很高的处理遠度直接支这种妘算。 (2)MIM计算机具有可以同时独立坛行多条指令,对不同的 数据选行操作。例如对数组的如下运算A=B*C+D+E+F/G,可以分 解为乘法(B*C),加法(D+E)和隙法(F/G)真接交给MIMD计 犷机的直接处理部分同时选行计犷。 在非常大的科学计算程序中,大部分的工作常常是风复地量 复同样的操作。SIM绪枸更适用于处理这类问题的计算。因为 在同样的价位下,SIMD体系结构的处理器元件可以散得比MMD 计算机的所有处理器更快。但是MM计算机明显地提供了更大 的灵活性。并可以用作多用户计机,而这在SIM计机上是 不可能的。 换同时执行程序的不同并行计箕机又可以分为: (1) SPMD(Single Program Multiple Data Stream Computers) 单翟序多教据流外行计机; (2) MPMD Multiple Program Multiple Data Stream Computers)多程序多数据流并行计算机。这神划分依据的执 行单位不是指令而是程序。 SPM外行计机一般是由多个相属的计箕机成处理器构成:而 MPM外行计算机內计算机成处理器的地位是不同的,根据分工 的不同,咆们长兜成的工作也不同,因此可以根据要将不周 的程序放到MM外行计箕机上执行。使得这些程序协调一政地
在 SIMD 并行计算机上特别适合进行向量（数组）的运算，它的 结构可以以很高的处理速度直接支持这种运算。 (2)MIMD 计算机具有可以同时独立运行多条指令，对不同的 数据进行操作。例如对数组的如下运算 A=B*C+D+E+F/G,可以分 解为乘法（B*C），加法（D+E）和除法（F/G）直接交给 MIMD 计 算机的直接处理部分同时进行计算。 在非常大的科学计算程序中，大部分的工作常常是反复地重 复同样的操作。SIMD 结构更适用于处理这类问题的计算。因为 在同样的价位下，SIMD 体系结构的处理器元件可以做得比 MIMD 计算机的所有处理器更快。但是 MIMD 计算机明显地提供了更大 的灵活性，并可以用作多用户计算机，而这在 SIMD 计算机上是 不可能的。 按照同时执行程序的不同并行计算机又可以分为： (1) SPMD（Single Program Multiple Data Stream Computers） 单程序多数据流并行计算机; (2) MPMD （ Multiple Program Multiple Data Stream Computers）多程序多数据流并行计算机。这种划分依据的执 行单位不是指令而是程序。 SPMD 并行计算机一般是由多个相同的计算机或处理器构成；而 MPMD 并行计算机内计算机或处理器的地位是不同的，根据分工 的不同，它们擅长完成的工作也不同，因此可以根据需要将不同 的程序放到 MPMD 并行计算机上执行，使得这些程序协调一致地
皃成给定任务。 并行计算机也可以按照内存的结构来分成“分布式内存》 和“共事式内存”两种基本结构的并行计算机。 在分布式系統中每个处理器有它自己的局域内夺,不存在公 共可用的存贮单元,各处理器可以通过通讯网络相互作用(例如, 与它仉的局域内交换数据)。 在失事式内訏绪枹中,所有处器部能够邋过某些逦讯网络 访问共事的内夺(有时它们也可以与向量眚存器或其它处理器的 高遠鰻冲存储器沟通)。在仅仅只有单地址空间的况下,共寡 式内存結枘比分布式内存更容易鑰程。 分布式内存模型在当今几种超级计犷机和并行计犷机工作站 上已经采用。这些并行计犷机上郗装有教十个功能强大的向量处 理器。瘘而,目前流行的机群计算( cluster computing)大部 分釆用分布式失丁内夺棋式绪。 并行犷法是在给定并行下的一种具体明确的计算方法和 步暻。其分类有不同的分类才法棂据外行讣任务的大小分类, 可以分为三类 )粗粒度弊行算法;它所含的计算任务有大的计算 量和校复杂的计算程序。 (2)细粒度外行算法;它斯含的讣算任务有較小的计 量和校短的计犷程序。 (3)中粒度并行算法;它所含的计算任务的大小和计算
完成给定任务。 并行计算机也可以按照内存的结构来划分成“分布式内存” 和“共享式内存”两种基本结构的并行计算机。 在分布式系统中每个处理器有它自己的局域内存，不存在公 共可用的存贮单元，各处理器可以通过通讯网络相互作用（例如， 与它们的局域内存交换数据）。 在共享式内存结构中，所有处理器都能够通过某些通讯网络 访问共享的内存（有时它们也可以与向量寄存器或其它处理器的 高速缓冲存储器沟通）。在仅仅只有单地址空间的情况下，共享 式内存结构比分布式内存更容易编程。 分布式内存模型在当今几种超级计算机和并行计算机工作站 上已经采用，这些并行计算机上都装有数十个功能强大的向量处 理器。然而，目前流行的机群计算（cluster computing）大部 分采用分布式共享内存模式结构。 并行算法是在给定并行模型下的一种具体明确的计算方法和 步骤。其分类有不同的分类方法。根据并行计算任务的大小分类， 可以分为三类： （1） 粗粒度并行算法；它所含的计算任务有较大的计算 量和较复杂的计算程序。 （2） 细粒度并行算法；它所含的计算任务有较小的计算 量和较短的计算程序。 （3） 中粒度并行算法；它所含的计算任务的大小和计算