第十章高性能计箕和并行算法 §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） 中粒度并行算法；它所含的计算任务的大小和计算
程序的长短在粗粒度和细粒度兩种类烈的犷法之 间。 棂据并行计算的基本对可以分为:数值并行计和非数 并行计。际上网者之间外无严格的界限。非数值计算也会用 于高贛度数值讣算,数值计算中也会有查找、匹配亭非数值计算 成分。实际分类时,主戛是权据主要的计犷量所属范嚼以及宏观 的计算方法来判斷。 根据外行计选程间的赖关系可以分为 (1)同乡并行算法;该算法是过一个全局的时钟来控制 部分的步世。将任翕中的各个部分计犷同步地向前 (2)异步并行算法;它执行的吝部分计算步化之间没有关 联,互不同步;在操作中,咆们根据计过程的不同 阶段决定穆、继鲼成终止。对于SDM并行计算机一 舭适合用同步并行算法,而MM并行计算机则适合用 异步外行算法。 §10.3并行编程 设计一个高放的外行法并不是一件容易的事。它的设计过 程比較复杂。通常编程设计过程可以分为四步 ●任务划分( Partitioning)。该阶斆将蓬个倇用域或功能分解
程序的长短在粗粒度和细粒度两种类型的算法之 间。 根据并行计算的基本对象可以分为：数值并行计算和非数值 并行计算。实际上两者之间并无严格的界限。非数值计算也会用 于高精度数值计算，数值计算中也会有查找、匹配等非数值计算 成分。实际分类时，主要是根据主要的计算量所属范畴以及宏观 的计算方法来判断。 根据并行计算进程间的依赖关系可以分为： （1） 同步并行算法；该算法是通过一个全局的时钟来控制 各部分的步伐，将任务中的各个部分计算同步地向前 推进。 （2） 异步并行算法；它执行的各部分计算步伐之间没有关 联，互不同步；在操作中，它们根据计算过程的不同 阶段决定等待、继续或终止。对于 SIDM 并行计算机一 般适合用同步并行算法，而 MIMD 并行计算机则适合用 异步并行算法。 §10. 3 并行编程 设计一个高效的并行算法并不是一件容易的事，它的设计过 程比较复杂。通常编程设计过程可以分为四步： z 任务划分(Partitioning)。该阶段将整个使用域或功能分解
成一些小的计算任奇,它的目的是耍羯示和亓拓并行执行的 机食; ●通信( Communication)分析。由任务划分产生的各项任务一般 都不能独立完成。可能辯要确定各项任毒中所鲁交换的教据 和协调音项任务的执行。信分析可以检测在任务捌分阶段 划分的合理性; 任务组合( Agglomeration)。换照性能戛求和实现的代价來考 寒角两个阶段的结果,必要时可以将一些小的任务组合成夏 大的任办以提高执行效亭和减少通信开销; 处理器映射 Mapping)。效是设计的最后阶段。要决定将每 个任务分配到哪个处理器上去执行。目的是最小化全局执 行时间和通讯成本,并最大化处理器的利用率。 上迷效程简称为PCAM设计过程 目前量量的并行编程棋乳 (1)数据行( Data Paralle1)模型(它的初裹是为了 SIMD并行机) (2)消息递( Message Passing)模型(其物哀是为了多计 算机) (3)共享变量桃型 (4)函数式糗型善 后面两种的疝用都没有前面两种那禅普
成一些小的计算任务，它的目的是要揭示和开拓并行执行的 机会； z 通信(Communication)分析。由任务划分产生的各项任务一般 都不能独立完成，可能需要确定各项任务中所需交换的数据 和协调各项任务的执行。通信分析可以检测在任务划分阶段 划分的合理性； z 任务组合(Agglomeration)。按照性能要求和实现的代价来考 察前两个阶段的结果，必要时可以将一些小的任务组合成更 大的任务以提高执行效率和减少通信开销； z 处理器映射(Mapping)。这是设计的最后阶段。要决定将每一 个任务分配到哪个处理器上去执行。目的是要最小化全局执 行时间和通讯成本，并最大化处理器的利用率。 上述过程简称为 PCAM 设计过程。 目前最重要的并行编程模型： （1） 数据并行（Data Parallel）模型（它的初衷是为了 SIMD 并行机）、 （2） 消息传递(Message Passing)模型（其初衷是为了多计 算机）、 （3） 共享变量模型、 （4） 函数式模型等， 后面两种的应用都没有前面两种那样普遍
數据并行的含义是将相同的操作同时作用于不同數据,因此 不但鸶用于在SIM计算机上实親。也可以在SPM并行计算机上 运行,这取决于粒度大小。SIMD程序着量开发指令级中细粒度 的外行性,SPMD程序着量开发子程序級中粒度的并行性。在向 量机上遠尅教据并行求解问题的虫崴也说明教据并行可以高放 率地解决一大类料学和工程计算问题数据外行编程模型是一种 较痛层次上的棋到。咆提供鋡鑰程者一个全局的地址空间。一般 这种形式的语言本身就提供外行执行的语义。对于编程者,实现 据并行的程序,只帚要筒单地指明执行什么并行操作以及行 操作对永。例如对于教组的运算,遢过语旬 A=B+C(或共它的襄达方式) 就可以实现B和C数组的对应元素相加后结果赋给A。因此教据 并行的衰达是相对筒单和简洁的,它不卿要编程者关心并行机是 如何对该操作选行外行执行的。对于非数据并行类问题編程棋 型,如景也釆用数据并行的方式來解决,一舭难以取得高的效率, 数据外行不率易歌达,甚至无法达其它形式的外行征。数据 外行鑰程目前面临的主要问题是要实淝高效的編译。有了高效的 编译器。教据外行程序就可以在共事内存和分布式内存的并行机 上部得到高执行效率。有了高效的編译器,就可以提高外行程序 的开效率,提高养行程序的可移植性。 消息食递鱻程模型是在各个并行执行部分之间食递消息,相 互遠讯。消丸可以是指令、数据、同步信号或中斷信号瞢。消胤
数据并行的含义是将相同的操作同时作用于不同数据，因此 不但适用于在 SIMD 计算机上实现，也可以在 SPMD 并行计算机上 运行，这取决于粒度大小。SIMD 程序着重开发指令级中细粒度 的并行性，SPMD 程序着重开发子程序级中粒度的并行性。在向 量机上通过数据并行求解问题的实践也说明数据并行可以高效 率地解决一大类科学和工程计算问题。数据并行编程模型是一种 较高层次上的模型。它提供给编程者一个全局的地址空间。一般 这种形式的语言本身就提供并行执行的语义。对于编程者，实现 数据并行的程序，只需要简单地指明执行什么并行操作以及并行 操作对象。例如对于数组的运算，通过语句 A=B+C（或其它的表达方式） 就可以实现 B 和 C 数组的对应元素相加后结果赋给 A。因此数据 并行的表达是相对简单和简洁的，它不需要编程者关心并行机是 如何对该操作进行并行执行的。对于非数据并行类问题编程模 型，如果也采用数据并行的方式来解决，一般难以取得高的效率， 数据并行不容易表达，甚至无法表达其它形式的并行特征。数据 并行编程目前面临的主要问题是要实现高效的编译。有了高效的 编译器，数据并行程序就可以在共享内存和分布式内存的并行机 上都得到高执行效率。有了高效的编译器，就可以提高并行程序 的开发效率，提高并行程序的可移植性。 消息传递编程模型是在各个并行执行部分之间传递消息，相 互通讯。消息可以是指令、数据、同步信号或中断信号等。消息
食递一舭是对分布式内存并行计机的方法,但是也可以适用于 失事式内音的并行计算机。消丸食递为鑰程者提供了更灵活的挖 制手段和达并行的方法,一些用数据外行很难歌达的并行算法 都可以用消丸传濋編程桃型来实砚。消息传递鑰程τ型比数据外 行编程褀到叉活,还具有各种各样的控制手段,这就可以使程 序高效率运行。消胤递程序是由多个选程组成,每个选程都有 自己的控侧纜。由于采用消食濋編程模型猾贔鑰程者来明确地 为进程分配教据和负敢,因此它也俍得编程者的工作量增加,其 編程的級别比較低。虽然这禅,消食递的基本邋儈模式是筒单 和清楚的,习和尊这些部分外不困难,因此大量的并行程序 设计仍嶽是消丸俊递并行编程模式的。 并行程序是鼎过并行语言来褒达。并行语言的产生有三 种方式 (1)设计金新的并行语言 (2)扩晨原來串行语言的语法成分,使它文持并行征; 3)为串行语言提供可调节的行库,并不欧变串行语言。 目常用的是第(2)和(3)两种方式,最常用的是第(3) 种。并行语言的发展十分迅逭,并行语言的种类也很多,但是真 正用起来外被广泛接曼的语言却寥寥无几。对 FORTRAN和C 语言的扩充是最常见的外行语言产生办法。如MI就是 FORTRAN 和C语言绪合起来奧现的
传递一般是对分布式内存并行计算机的方法，但是也可以适用于 共享式内存的并行计算机。消息传递为编程者提供了更灵活的控 制手段和表达并行的方法，一些用数据并行很难表达的并行算法 都可以用消息传递编程模型来实现。消息传递编程模型比数据并 行编程模型更灵活，还具有各种各样的控制手段，这就可以使程 序高效率运行。消息传递程序是由多个进程组成，每个进程都有 自己的控制线。由于采用消息传递编程模型需要编程者来明确地 为进程分配数据和负载，因此它也使得编程者的工作量增加，其 编程的级别比较低。虽然这样，消息传递的基本通信模式是简单 和清楚的，学习和掌握这些部分并不困难，因此大量的并行程序 设计仍然是消息传递并行编程模式的。 并行程序是需要通过并行语言来表达。并行语言的产生有三 种方式： （1） 设计全新的并行语言； （2） 扩展原来串行语言的语法成分，使它支持并行特征； （3） 为串行语言提供可调节的并行库，并不改变串行语言。 目前常用的是第（2）和（3）两种方式，最常用的是第（3） 种。并行语言的发展十分迅速，并行语言的种类也很多，但是真 正使用起来并被广泛接受的语言却寥寥无几。对 FORTRAN 和 C 语言的扩充是最常见的并行语言产生办法。如 MPI 就是 FORTRAN 和 C 语言结合起来实现的