高性能Fortran的兴衰(2011)

作者：Ken Kennedy，Charles Koelbel，Hans Zima Communications of the ACM，2011年11月，第54卷第11期，第74-82页10.1145/2018396.2018415评论并行性同时执行多个任务是计算机设计的基础。即使是非常早期的计算机系统也采用了低级并行性(例如，将输入-输出与计算重叠)。后来的设计将并行性推向了更高的水平，包括20世纪70年代的矢量处理器和80年代的共享内存和分布式内存并行超级计算机。对这些机器的软件支持从未完全达到商业软件开发的标准，这主要是因为高性能计算的专业市场，以及与用户相关的困难，非常关注目标代码的性能。在这里，我们追溯高性能Fortran(Hpf)的历史，这是一种由一组业界和学术界领袖标准化的高级数据并行语言，19911993。它最初受到社区的欢迎，引起了人们对该语言及其实现的极大兴趣，但从未成功地建立起强大的用户基础。我们集中在设计HPF的技术和社会过程，以及它的成功和不足的因素。

HPF是自20世纪80年代末以来积极开发并行编程技术的众多努力之一。在这里，我们不会全面地对待这些努力，也不会回顾HPF之前的所有工作；有关这些主题的更多信息可以在本文15的会议版本和编程语言会议历史(http://www.acm.org/sigplan/hopl).)中找到。相反，我们提供了开发HPF时可用的并行计算机和编程系统的背景知识，然后转到定义HPF的过程、语言本身的特点以及它的成功和失败。最后，我们讨论了其他语言的开发人员和用户要吸取的经验教训。

创建HPF的环境(请参见此处的图)指导了我们的大部分讨论，矩形表示计算机类，附加的圆圈表示每个类最常用的编程语言。从语言L到体系结构A的一行表示在A上实现L所需的编译器/运行时或转换技术。为了完整性，我们包括顺序计算机和FORTRAN 77。

数据并行计算模型的特征在于可以在数据集合的每个元素上并行执行操作序列或语句。这个模型的部分动机是关于NESL语言的工作。4两种常见的实现是向量处理器(以高度流水线CPU为特征，在向量寄存器上操作)和单指令多数据(SIMD)计算机(以在单个控制单元下操作的数千个简单处理器为特征)。由于这种精细的控制，这些机器最自然的语言提供了数组算术和数组函数，它们反映了许多科学代码中的向量和矩阵运算。

经过多年的发展，矢量化编译器能够识别和利用FORTRAN77程序中的这种并行性。关键的启用技术是依赖分析和编译器转换，依赖分析识别对相同数据的冲突操作，从而阻止并行执行；编译器转换重新组织循环中的操作，以增加向量操作的机会。其结果是，许多向量机用户继续使用顺序语言编程。

然而，由于需要识别和开发更高级别的并行性，纯自动并行化在SIMD机器上并不成功。这些架构上的程序员用明确的数据并行语言(如NESL和Connection Machine Fortran，或CMF 22)编写。后来，Fortran 901通过标准化数组操作、数组赋值和内部数据并行函数(如SUM之类的缩减)，代表着迈向数据并行语言的重要一步。HPF后来就是基于这种编程模型的。

多指令多数据(MIMD)计算机通过为每个处理器提供其自己的指令流和与所有其他处理器异步操作的能力，允许更通用和更大粒度的并行执行。

MIMD计算机可以分为共享内存架构和分布式内存架构。在共享内存的MIMD机器中，所有处理器都连接到单个共享主存，这使得访问公共数据和在处理器之间交流结果变得很容易。这些机器的语言具有数据的全局视图和创建并行活动的多种方式(例如可以同时执行迭代的并行循环)和同步操作，以强制不同处理器上的活动之间的顺序。并行计算论坛公布了一套标准的FORTRAN扩展

然而，这些体系结构出现了两组问题：第一，无法大规模隐藏传统处理器的延迟，以及实现高速缓存一致性的硬件开销限制了其可伸缩性；第二，数据竞争的可能性，因此如果两个并行线程访问相同的内存位置，其中至少有一个线程写入该位置，则缺乏适当的同步可能会导致不同并行调度的不同结果。

这些问题导致了分布式存储器MIMD机器的发展，在这种机器中，处理器通过网络互连，每个处理器都有自己的本地存储器。到20世纪90年代初，这个组织允许机器扩展到大约1000个处理器。这种架构简单性的代价是软件复杂性；当两个处理器必须共享数据时，它们将不得不交换消息，这是一项昂贵的操作。降低这一成本依赖于正确放置数据以最大限度地减少所需的通信，并将消息传递调用放置在最合适的程序位置。到20世纪90年代初HPF工作开始时，消息传递库(如PVM和PARMACS)已经用于与标准顺序语言相关的MIMD系统编程。此后不久就开始了消息传递的标准化活动，该活动效仿HPF的工作并与之密切相关。11所产生的消息传递接口(MPI)20库提供对位置和通信的高效显式控制。尽管这种编程范例的复杂性较高，但由于其能够利用分布式内存计算机的性能，它很快就变得流行起来。

HPF的目标是一个可以在所有类型的并行机上高效执行的通用编程模型。

HPF的目标是一个可以在所有类型的并行机上高效执行的通用编程模型。开发人员必须回答是否可以在分布式内存机器上模拟共享内存的优势，即使是单个控制线程；还必须回答如何将并行性扩展到数百或数千个处理器。这些问题是通过数据并行语言来解决的，其中应用程序的大型数据结构是全局名称空间的一部分，该全局名称空间可以跨分布式存储器机的存储器或数据分布来布局。以这种方式映射到处理器的本地存储器的数据元素被认为是处理器所拥有的数据元素。在数据并行语言中，应用程序的大型数据结构是全局名称空间的一部分，该全局名称空间可以跨分布式存储器机的存储器或数据分布来布局。以这种方式映射到处理器的本地存储器的数据元素被认为是由处理器拥有的。程序执行由单个控制线程建模，但是分布式数据结构的组件可以并行操作。数据分配控制如何在处理器之间分配工作。编译技术(如后面讨论的技术)允许MIMD体系结构放松SIMD模型的锁步语义以提高效率。

HPF设计主要基于早期数据并行语言的语言设计和实现经验。这里，我们重点介绍HPF中体现的数据并行方法。可以肯定的是，它并没有得到编译器研究社区和应用程序社区的普遍接受。其他编程范例，包括函数式和数据流语言，也有很大的智力优势、热情的用户社区和/或两者兼而有之。

1991年在新墨西哥州阿尔伯克基举行的超级计算会议上，莱斯大学的肯·肯尼迪和印第安纳大学的杰弗里·福克斯会见了许多商业供应商，讨论将Fortran的数据并行版本标准化的可能性。这些供应商包括Think Machines(当时生产SIMD机器)、Intel和IBM(当时生产分布式存储器MIMD机器)和Digital Equipment Corp.(当时有兴趣为SIMD和MIMD机器生产跨平台的Fortran系统)。

肯尼迪和福克斯与学术界和工业界代表组织了一次物以类聚的会议，他们同意通过一个名为高性能Fortran论坛(HPFF)的小组探索更正式的进程，肯尼迪担任主席，查尔斯·科尔贝尔(Charles Koelbel)担任执行董事。在赖斯大学并行计算研究中心(CRPC)的支持下，1992年1月在休斯顿组织的一次有近100名与会者参加的会议以一次商业会议结束，20多家公司在会上承诺制定新标准的过程。

他们一致认为，这一过程应该在大约一年内产生结果。事实证明，这一紧凑的时间表将影响语言，导致采用规则，即HPF将只包括至少在一种语言和编译器(包括研究编译器)中演示过的功能。这限制了一些可以考虑的特性，特别是在高级数据分发领域。

然后，30到40名活跃的HPFF参与者每六周左右会面两天，主要是在达拉斯的一家酒店。除了肯尼迪和科尔贝尔，担任标准文件编辑的参与者包括Marina Chen，当时在耶鲁，Bob Knighten，然后在Intel，David Loveman，然后在DEC，Rob Schreiber，然后在NASA，Marc Snir，然后在IBM，Guy Steele，然后在Think Machines，乔尔·威廉姆森，然后在Convex，和Mary Zosel，然后在劳伦斯·利弗莫尔国家实验室。与会者来自5个政府实验室、12所大学和18家公司(供应商和用户)；他们也来自至少5个国家。HPFF是一个建立共识的过程，而不是一个单一组织的项目。

它处理了许多困难的技术和政治问题，其中许多问题是由于需要支持广泛应用程序的高级语言功能和需要生成高效的目标代码之间的紧张关系。此外，在编译数据并行语言方面的经验有限，更是雪上加霜。研究编译器大多是学术原型，应用于任何规模的应用程序都很少。另一方面，工业强势语言CMF相对较新，缺乏研究语言的一些先进特征。因此，在没有充分了解它们对编译器复杂性的影响的情况下，不得不做出许多决定。

结果是1993年初定稿的一种新语言12，并在同年晚些时候在俄勒冈州波特兰举行的超级计算会议上提出。1994年举行了另一组HPFF会议，旨在解决对现有标准的更正和澄清问题，并考虑支持更多应用的新功能。肯·肯尼迪(Ken Kennedy)再次担任主席，而玛丽·佐塞尔(Mary Zosel)现在是执行董事。与会者大多与19921993次会议相同，值得注意的是增加了阿贡国家实验室的伊恩·福斯特和当时在马里兰大学的乔尔·萨尔茨，每个人都领导着新的小组。这些更正包括在HPF1.1标准中，这是对1994年在华盛顿特区举行的超级计算会议上提交的1993年文件的轻微修订。HPF1.1中讨论但没有包括的一些新功能和澄清被收集在HPF1.1中，后来作为HPF2.0标准化工作的起点，19951996。

这项工作将合并新的功能，最显著的是在独立循环结构中执行累加的能力、高级数据分布和ON子句，该子句通过标识执行并行循环的每个迭代的处理器来提供对计算映射的控制。HPF 2.0还定义了被认为过于复杂而无法在所有编译器中使用的批准扩展。HPFF的目的是让供应商首先实现所有核心语言功能，然后根据客户需求确定扩展的优先级。不足为奇的是，结果是混乱，因为不同供应商提供的功能集各不相同。

为HPF建立的目标相当简单：(主要)基于(概念上)共享内存中的数据并行操作为可伸缩计算机系统提供高级的、可移植的编程模型，并生成性能可与给定机器上的最佳手工编码本机语言代码相媲美的代码。为了实现它们，HPF1.0定义了一种具有几个新特征的语言。为简单起见，我们不讨论HPF 1.1或HPF 2.0中的增强功能，尽管它们的思路大致相同。

首先，该语言基于Fortran 90，1扩展被定义为结构化注释形式的一组指令。HPF编译器可以将这些指令解释为有关如何生成并行程序的建议。在标量机器上，假设机器有足够的内存，只需忽略指令，就可以不加更改地执行HPF程序。该设备允许HPF并行性扩展与底层Fortran 90程序完全分开；相同的程序可以在串行和并行系统上运行。顺序到并行的可移植性是调试代码的一个巨大优势。

语言的主要补充是一组分发指令。数组集可以彼此对齐，然后通过内置分布跨处理器分布。这些指令可用于以连续块或循环方式将数组的各个行或列分配给处理器。通过将指令应用于两个简单的Fortran数组来说明此功能。

现在，假设我们想要将第一个维度(以及该维度上的计算)拆分到一台并行机的处理器上。此外，假设因为A和B的相应元素经常一起访问，它们应该始终具有相同的分布。这两种效果都可以通过目录来实现

HPF还提供循环分布和循环(K)，在循环分布中，元素以循环方式分配给处理器，在循环(K)中，K个元素的块被循环分配给处理器。一般而言，块是使用最近邻元素通信的计算的首选分布，而循环变体允许对某些计算进行更精细的负载平衡。

子例程参数的数据分布特别复杂。形式子例程参数可以与ALIGN和DISTRIBUTE指令相关联。如果它们完全指定了数据分布，则相应的实际参数将在调用时重新分布，并在返回时重新分布回其原始分布。如果调用方和被调用方的分发相匹配，则预计编译器或运行时系统将放弃重分发中所需的复制。HPF还定义了继承分布的系统，其中形式参数的分布将与实际参数相同。此声明需要显式的子例程接口(如Fortran 90接口块)。在这种情况下，可以避免复制，但子例程的代码生成必须处理所有可能的传入分发。据我们所知，它的复杂性是如此之大，以至于没有一个编译器完全实现它。

除了分布指令之外，HPF还提供了帮助识别并行性的指令，通过前面描述的数组上的简单平滑操作进行了说明。

HPF还提供了取自CMF的forall语句，作为表示数组赋值的另一种方式。我们松弛示例中的内部DO循环可以写成。

显式索引允许forall方便地表达比标准数组赋值更广泛的数组形状和计算。

HPF能够指定循环的迭代应该使用INFICATE指令并行执行。而在这个内部循环中，编译器可以很容易地派生出这个属性，并且下标的下标通常需要运行时分析，而不需要独立指令提供的显式断言。程序员通常具有特定于应用程序的知识，这将允许并行执行这样的循环，如下所示。

HPF也是首批将关联库HPF Library作为其定义的一部分包括在内的语言规范之一，它通过提供对全局数组的并行操作(如求和减少、聚集/分散和部分前缀操作)来增强语言的功能。

最后，HPF包含了一些旨在提高兼容性并促进与其他编程语言和模型互操作的功能。特别是，外部接口使调用用其他语言(如标量Fortran和C)编写的子程序成为可能。特别重要的是调用用MPI编写的子例程的能力，这种能力使重新编码HPF子程序成为可能，从而提高效率。

HPF语言设计和相关编译技术背后的概念由HPF之前的早期数据并行语言率先提出，特别是CMF、22Fortran D、13和维也纳Fortran。6它们共有的关键方法是采用高级表示法来指定数据分布，从而将显式生成通信的任务降级到编译器和运行时系统。Fortran D和维也纳Fortran最初采用所有者计算规则编译到分布式内存MIMD机器。因此，编译器以这样的方式为每个语句生成代码，即所有计算都在拥有计算输出的处理器上执行。后来，该策略被修改为在任何处理器上执行计算，从而最大限度地减少通信。该规则由通用执行模型补充，其中调度执行计算的每个处理器执行以下三个步骤：生成消息以将其拥有的数据发送到需要它们的所有其他处理器；等待来自包含所需非本地数据的其他处理器的消息的到达；以及使用其本地数据和从其他处理器传送的非本地数据来完成计算。通过此范例生成的点对点消息是分布式内存MIMD实现所需的所有同步。这个想法非常成功，以至于当思维机器在1993年推出MIMD CM-5计算机时，它保留了数据并行的CM Fortran语言。类似的技术可以产生共享内存MIMD计算机所需的同步。

在这里，我们概述执行源代码到源代码转换的HPF编译器的主要阶段：3、14。

在编译器前端之后，数据分发阶段分析。

.