ACM通信
实践
十年来并行编程生产力的进步
来源:斯特皮克Srdjan
2002年，美国国防高级研究计划局(DARPA)启动了一项关于高效计算系统(HPCS)的重大计划。这个项目的动机是相信，在peta规模下，编写、调试、调优和维护软件的难度决定了未来一代并行机器的利用。
作为该计划的一部分，DARPA鼓励开发新的编程语言、运行时和工具。它相信，通过简化并行构造的表达，将运行时模型与开发中的异构处理器体系结构相匹配，并提供强大的集成开发工具，程序员的工作效率可能会得到提高。这是一个合理的猜想，但我们试图超越猜想，去实际衡量生产率的提高。
虽然没有测量程序员生产力的既定方法，但很明显，生产力度量必须采用比率的形式:实现的编程结果超过实现它们的成本。在这种情况下,结果被定义为成功地创建了一组在两个工作站核心上正确运行的并行程序。这距离peta的规模还有很长的路要走，但由于新的并行软件通常以这种方式开始(然后在越来越多的处理器上进行扩展和调整)，我们认为它是一个合理的近似。此外，对于编写几乎所有并行应用程序(无论多么小)的人来说，使用两个核心所得到的结果都是有意义的。成本一旦定义了结果，处理起来就更简单了，因为创建这组并行程序所花费的时间可以合理地近似于结果。
这项研究的目的是衡量程序员的生产力，从而定义，从2002年开始的十年的大部分时间，HPCS倡议的开始。比较主要集中在两种并行编程的方法上:SPMD(单程序多数据)模型，如C/MPI(消息传递接口)，以及APGAS(异步分区全局地址空间)模型，该模型由X10 (http://x10-lang.org)，虽然也研究了环境和工具的差异。注意，比较是不在C/MPI和现在的X10之间。相反，这是2002年的情况与现在的情况的历史对比。事实上，c++和它的例外，MPI-2和它的单边通信协议都可能提高程序员的生产力，它们本身都是值得研究的。
鉴于我们的目标，我们试图尽可能地为C/MPI用户复制2002年的编程环境。其中包括gdb调试器，以及一组典型的命令行工具。对于X10，我们使用Eclipse (http://www.eclipse.org)使用X10插件，因为它是在2010年发现的，也就是这项研究的日期。X10是HPCS计划的一部分。它结合了Scala (http://www.scala-lang.org)，其并发编程模型可以很好地映射到现代并行机器的PGAS模型。十年后，这种语言仍在进化，但在这项研究开始时，基本模型是稳定的。重要的是，在这项研究完成之前，X10调试器是不可用的，所以当前X10用户可以期望看到比本文中报告的更大的改进。
之前的工作
这并不是第一个试图衡量X10编程效率的研究。Ebcioglu et al。5还有丹妮斯和霍尔沃森3.描述一个实验，在该实验中，本科生(并行编程方面的新手)在C/MPI、UPC(统一并行C)或X10(一个非常早期的版本)中接受训练，然后尝试并行SSCA 1(可伸缩合成紧凑应用1)的字符串匹配算法，如Bader等人所描述的那样。2C/MPI的平均完成时间约为510分钟，UPC为550分钟，X10为290分钟。当去掉测试期间的代码执行时间差异后，C/MPI的时间大约为360分钟，UPC为390分钟，X10为180分钟。然而，由于没有明确的代码完成成功标准，对这一大约两倍的生产率提高的解释有些复杂。
在随后的研究中，霍尔沃森和丹妮斯6将Eclipse编程环境添加到X10程序员可用的工具中。这项研究的参与者更有经验，在早期的课程中有一些并行编程的训练。在这里也发现了X10和Eclipse比C/MPI的生产率提高，但计算这种提高的大小是复杂的，因为7个C/MPI参与者中只有1个完成了任务(在407分钟内)，而7个X10参与者中有5个平均在321分钟内完成了任务。
在这两个早期的研究中，只编码了一个程序(SSCA 1的一部分)，只有相对新手的并行程序员被测试，任务被限制在并行一个尴尬的并行算法，该算法被提供给工作的串行代码测试参与者。所有这三个缺陷都在这里报告的评估中得到了解决。
实验方法
在一项长期的研究中，我们测量了用两种语言分别开发6个并行程序的时间，总共12个程序。每个程序都是从问题陈述和/或算法描述中开发出来的，没有利用任何现有的代码示例。在使用双核心工作站的两个核心进行第一次成功的并行运行时，完成了任务。
六个项目中的两个是在DARPA HPCS项目的第二阶段定义的，即SSCA 1和SSCA 2，并在Bader等人中进行了描述。2SSCA 1是之前两个参考研究中使用的字符串匹配问题。然而，在这项研究中，每种语言都开发了两个版本的SSCA 1:当目标字符串比搜索字符串短得多时，令人尴尬的并行版本运行良好;还有一个更复杂的反对角线版本它更适合两根弦长度大致相等的情况。SSCA 2对于这种评估是新的，所有四个内核都用每种语言编码。
在对Berkeley母题分析的基础上，除了这两个ssca之外，还定义了另外四个问题。1我们将描述这六个问题。
开发这12个项目花了将近一年的时间。尽管让多个熟练的程序员执行这项任务是可取的，但这将大大超过可用的资金。相反，通过在我们的生产力评估团队中只有一个程序员成员，并且本报告的作者之一作为测试参与者，研究成本得到了控制。作为一名训练有素的数学家博士，他从1979年就开始用C语言进行专业编程，编写了IBM第一个C编译器的前端，并从2007年开始为多核系统编写MPI。他在2007年也开始编写X10，开发了霍尔沃森和丹尼斯6研究测试平台，并编写了X10教程的几个部分。虽然我们很容易将单个程序员的结果视为轶事，但观察到的生产率提高是在较简单任务的新手程序员的范围内，而且考虑到该程序员对C的熟练程度更高，并且在研究期间缺乏X10调试器，这可能是相当保守的。
这些项目．本研究定义了六个编程问题，每个问题代表一类并行应用。总的来说，它们涵盖了大量典型的小型并行程序:
- SSCA 1(第一内核)．这涉及到一个由染色体和蛋白质研究引起的字符串匹配问题。其中一个要求在一对大写字母字符串的子字符串之间找到最佳近似匹配。
- SSCA 2(所有四个内核)．这个问题涉及到一个稀疏图的有效表示，它的边集是先验已知的随机分布在可用处理器的集合。第一个内核以一种可被所有后续内核用作输入的格式构造图形。第二个核按权重从图表示中提取边缘，并形成一个具有最大权重的边缘列表。第三种方法从初始顶点集合中提取一系列由指定长度的路径组成的子图。最终的内核计算一个网络中心性度量，以确定图中最短路径上的关键重要顶点。
- Consumer-producer．这个问题使用一个进程作为服务器来管理多个客户机进程的队列，这些进程可以随机添加或删除队列。因为一个缓冲区是所有操作的目标，所以第一个编程问题是尽量减少争用。由于向队列中添加元素和从队列中删除元素发生在相对的两端，这是避免争用的主要机会;如果队列足够大，可以安全地同时执行这两个操作。
- 不平衡树搜索．与前面通过中心服务器进程管理协调的问题不同，这里是一组对等进程，每个进程管理自己的工作队列，并在需要时与其他进程共享工作。整个任务是广度优先搜索已知从根到叶的深度变化很大的树。每个处理器都在管理自己的未访问树节点队列，但空闲的对等点可能会要求它提供一些节点供它执行。
- 弗洛伊德的算法．给定一个带加权边的有向图，它要么是无环的，要么只有非负权值，我们计算所有顶点对之间最短路径的权值之和。
- 离散傅里叶变换．实现的算法是原始的Cooley-Tukey快速傅里叶变换。输入是一个2的数组n复数，作为输出。至少到n= 3和2n=8时，传统的串行算法优于Cooley-Tukey，这意味着可以有效地将数组分布在2上n/ 8的过程。
观察到的生产力增益
随附的表格总结了第一次成功并行运行的天数，以及为12个程序中每个程序编写的代码行数。X10的六个程序总共需要39天的开发时间。MPI C语言的6个程序总共需要129天的开发时间。因此，由于语言(其次是环境)的原因，生产率的整体提高超过3倍。在编写X10的39天里，以每天159行代码的总体速度编写了6195行代码。在使用MPI编写C语言的129天里，以每天79行代码的总体速度编写了10245行代码。虽然我们没有测量这些程序的性能，Saraswat等人的一项研究。7研究了X10实现的一个不平衡树搜索程序的卓越并行性能，这个程序与我们的很相似。
生产力的贡献者
在这项研究中，是什么原因使生产率提高了三倍?虽然有些好处是由Eclipse和X10插件提供的集成工具带来的，但大部分好处要归功于X10语言的特性。提供的任务和数据分区活动而且的地方，提供灵活的任务支持异步而且完成，以及一个集成得很好的异常处理机制。结合起来，这些简化了并行性的表达，并允许程序结构更紧密地反映自然问题结构。此外，自动垃圾收集消除了管理内存的繁琐工作，面向对象简化了处理复杂结构的任务，同时避免了内存引用的错误计算。以下部分提供了这些特性如何提高生产力的示例。
表达并行性．X10程序从在单个位置执行单个活动开始。活动是单个顺序执行的线程，而位置是将处理能力与分区的全局内存共享结合起来的系统的一部分。任何活动都可以根据需要在当前运行的地方或任何其他方便的地方发起新的活动。
本地线程．作为一个简单的示例，SSCA 1需要从某个外围源读取一对字符串。如果字符串非常长(因为这个问题被设计成可以扩展到任意长的字符串，所以它们很可能是这样)，那么就需要同时读取这两个字符串。如果要从单个处理器访问两个流，则需要的X10代码显示在图1．
简单的fork-join并行性在X10中使用异步语句来执行fork，用一个完成块来实现联接。的试一试块包围整个计算捕获任何可能在文件I/O或活动启动/关闭中发生的错误。
对于C语言，基本问题是如何获得第二个线程，使原始线程可以与之共享内存。图2显示了与在C语言中使用POSIX线程可能完成的相同的代码。
SPMD模型在试验中拟合较差我_ id = = 0，一个典型的C/MPI习惯用法。如果发生I/O错误，处理器0必须让其他处理器知道有问题。这就是为什么必须无论是否有任何问题，都要在字符串被读入后进行广播。这个函数_读吗封装第二个线程的任务。即使它正在执行与根线程完全相同的读取操作，它也必须是独立的。
远程线程．前面的例子是如此简单，以至于很容易低估它的重要性。为了更好地理解，考虑一个轻微的变化。假设不是已知处理器0处理大部分工作，而是只有在运行时才知道数据所在的处理器，就像数据来自网络或一组数据库时一样。代码如何更改?图3显示X10代码。
X10程序中的位置(如MPI进程)具有惟一的整数ID。在图3从有id的地方读取两个序列seq1Id而且seq2Id．读取操作与原始操作的区别仅在于在必须提供条款来说明每次阅读将在哪里进行。所有剩下的代码都没有改变，包括错误处理，尽管现在可能涉及多个处理器．这是X10异常模型的结果，该模型被设计成反映程序的活动树。它允许该树中的任何活动处理它下面的子树中的任何东西引发的异常。(X10异常不会自动包含它被抛出的位置，尽管程序员可以很容易地创建异常的子类并插入位置信息。还有一种情况是，异常对发生异常的活动的子活动或兄弟活动没有影响。)虽然c++引入了try / catch2002年以前串行代码异常处理的风格，没有一个线程框架能够像X10那样简单地将其应用到多进程集中，在X10中不加更改地同时支持单线程和多线程情况。
访问序列化．单服务器队列是一种常见的模式，在这种模式中，一组玩家对条目流的串行写入由另一组玩家读取。通常的解决方案是缓冲数组中的项，直到它们被使用为止。在数组的末尾添加项，但从数组的开头删除项。
对于多个参与者，这种情况下出现竞争条件的可能性是显而易见的。删除数组中的操作必须相互序列化，必须如此增加了．另一方面，除非剩下的东西很少，否则添加和一个删除不需要相互序列化，因为它们影响数组的两端。
如何通过允许一个函数来获得最后一点性能呢添加与…平行删除什么时候才是安全的?序列化两增加了或两个删除只需要C的后缀++的一个轻量级原子版本。当剩下的条目很少时，所有的操作都必须序列化，这需要一个原子代码块来保证一个线程，一旦在块中处于活动状态，在退出块之前将是块中唯一的线程。
在X10的课堂AtomicInteger提供对单个整数值变量的原子更新。因为这使用了硬件支持，所以它比保护整个块要轻得多。关键字原子在一个语句块前面序列化对该块的访问。因此，X10提供了编写650行读起来非常自然的代码所需的内容。到2002年为止，还没有类似的标准C APIAtomic-Integer或原子块。(见http://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html．这个API本质上就是C11中标准化的API。)从原子块和原子更新中需要的序列化可以通过使用同步MPI调用来实现，例如MPI _ Recv，但结果代码在我们的实现中是更长的1100行，而且相当难以遵循。
对于那些想知道什么需要1100行代码的人来说，只有非常小的一部分代码支持队列操作。这是一个客户机-服务器应用程序。服务器必须启动，它必须停止，客户端必须发出请求，必须有访问控制(不是每个人都可以使用每个数组)，等等。使X10版本如此短的原因是更简单的错误处理，并且不必同时编写客户机和服务器API。
对等协调．在前面的示例中，协调是通过中央服务器进程进行管理的。当一组对等进程各自管理自己的队列，并在需要时与其他进程共享条目时，会发生什么情况?在这里，每个进程同时充当活动进程的某些子集的客户端和服务器。在我们编写的示例中，对预先知道基本上不平衡的树执行了宽度优先搜索。每个处理器管理自己的未访问节点队列，但是，为了更均匀地分配工作负载，可能会要求处理器将一些未处理的节点发送给另一个处理器。
这里最大的问题是终止:一个进程如何知道自己以及其他所有进程何时都停止工作?处理这个问题的算法(至少在低阶规模下)可以追溯到大约30年前的Dijkstra等人。4并且从那以后被改进了很多次。SPMD解决方案就是基于这些问题。X10解决方案完全不同，它依赖于按需线程。
让我们先看看X10。单个X10活动通过请求集合中的每个对等点开始搜索树的一部分来开始操作。如果这些对等点中的一个没有工作，它有一个“附近”对等点的列表，允许它请求更多的工作。它通过向它的每个邻居发送一个对自己的引用，然后让它当前的活动终止来实现这一点。但是，发送这些请求的对象将继续存在。因此，如果空闲对等体的一个邻居有多余的工作，它可以在空闲对等体的位置产生一个新的活动，在那里该对等体可以恢复工作。如果对方想要确保只有一个人的工作被接手，那就需要稍微握手，但除此之外，一切都是如此。由于根活动已经衍生了多个对等活动作为异步在一个完成块，当这些都不存在时，它只能退出该块异步保持活跃从而完成工作。
C的解决方案完全不同。每个处理器上都没有对等对象准备接收远程进程调用，即使有，也没有类似X10的对象完成块。naïve处理空闲的对等体的方法是让它挂起在一个同步接收上，但是谁负责知道什么时候向对等体发送“全部完成”消息呢?这正是Dijkstra等人所要解决的问题，他们采用了一种聪明的方法，即对所有对等体进行轮询。
在C解决方案中，每个处理器必须执行三个活动:主要工作(即搜索和处理其共享的树);监听终止控制消息;并倾听邻居的共享工作请求。通过使用两个非阻塞接收来侦听控制和共享通信，每个处理器实际上有三个并发活动:主活动和两个待处理的接收。每个处理器的主循环负责及时处理传入的控制和共享请求。最复杂的是决定谁向谁发送什么控制信息。
C语言中缺乏内省也是一个严重的问题。在诸如X10这样的面向对象语言中，对象知道它们有多大以及存在哪些突出的引用。
管理内存和处理错误．前面讨论的问题涉及我们程序的自然线程模型与X10 APGAS和MPI SPMD并行模型之间的匹配。还有几个众所周知的与c相关的缺点影响了我们编写连续代码段的效率。这些缺点在X10中不存在。平均而言，在每1000行C代码中，我们会遇到大约6个或更多这样的众所周知的问题，总体影响是显著的。许多人需要额外的努力，因为他们没有在需要纠正的地方暴露自己。
内存泄漏．与许多最近的语言一样，X10具有自动垃圾收集功能。长期以来，显式管理存储的需求一直被认为是C编码效率的严重障碍之一。您可能认为像SSCA 1这样的简单问题，大约有1200行相对简单的字符串匹配代码，这不会是一个问题，但它确实是，特别是如果代码要运行很长时间(或合并到经常调用的库例程中)。这里需要找到并消除内存泄漏，对于代码中分配但从未释放内存的地方，这个任务可能需要一到两天的时间。
获得正确的内存引用．C语言中缺乏内省也是一个严重的问题。在诸如X10这样的面向对象语言中，对象知道它们有多大以及存在哪些突出的引用。在C语言中，这些计算必须手工完成。这并不是说，使用X10就不能错误地计算数组范围。这仍然是可能的，但X10将在运行时在访问点捕获对数组的出界访问。即使是熟练的C程序员也不可能花时间对每个数组访问进行防弹处理。由于错误访问通常是在远离需要纠正代码的地方检测到的，所以这些错误不容易发现和修复。
错误处理．C语言中缺乏方便的异常机制，这迫使程序员更加冗长。例如，当我们的程序员想要一个泛型输入流来读取数字值的ASCII流时，Floyd的算法就出现了这个问题。他的API有一个条目，用于标记流，将标记转换为适当的数字类型，并确保值是合法的。显然，流可能会遇到许多问题。问题是如何处理这些错误。
对于X10中的错误，将抛出一个异常，其类型标识遇到的问题。应用程序可以避免提供用于检测通用错误的特殊代码，例如由较低级函数发现的意外文件结束符，因为它们也可以通过抛出异常来发出错误信号。因此，应用程序可以专注于通知内容中的语义错误。
对于大多数一次性代码，错误处理不是一个严重的问题，但对于生产代码和复杂的通信模式，如Dijkstra等人的终止算法，它肯定是一个严重的问题。C的信号机制最适合专家使用。然而，C的问题在多线程SPMD世界中更加严重。考虑标准库例程strtoll流调用将找到的标记转换为长整数。这里讨论的是strtoll的“man”页给出的错误指示:
“strtol, strtoll．.．函数返回转换的结果，除非值会下溢或溢出。如果不能执行转换，则返回0和全局变量errno被设置为EINVAL(最后一个特性不能在所有平台上移植)。如果发生溢流或下溢，errno被设置为ERANGE．.．"
考虑C应用程序为了处理各种可能的错误而需要的代码。代码应该确保为零吗errno在调用之前strtoll？毕竟，由于一个完全不相关的早期问题，它可能是非零的。用于检查的代码errno此外，要了解发生了什么，仅仅检查这一点是不够的errno为非零，因为错误可能是I/O错误、解析错误或范围错误。你也不能肯定errno是线程安全的——不是在所有系统上。然后什么?以及你应该在申请的哪些地方写清楚errno，谁的值是一个全局?其他哪些流程需要意识到这个问题，以及应该如何意识到它们?
结论
C和MPI在并行编程社区占据主导地位是有充分理由的。它们都是经过精心实施的、文档化的、优雅的、干净的设计。在经验丰富、纪律严明的专业人士手中，他们提供了在其他地方根本无法获得的控制水平。C和MPI都不是一个长期的目标:它们都在不断改进，尽管它们现在已经是成熟的技术。
然而，C/MPI的好处是否经常超过其成本?通过我们所有的三个研究，特别是最后一个，我们已经看到了使用高级语言和编程模型的显著好处，从2到6倍的快速开发到第一次成功的并行运行。对于需要维护多年的大型程序来说，这些生产率优势可能更大。
X10及其APGAS编程模式目前正在许多研究机构和大学中进行探索。尽管该语言可能会也可能不会成为主流语言，但使它变得如此高效的特性可能会在并行社区中得到很好的建立:灵活的线程、自动垃圾收集、运行时类型驱动的错误检查、分区的全局内存和根化的异常处理都是有价值的。我们希望我们的实验能够鼓励那些希望提高并行程序员生产力的人认真研究X10的设计及其好处。
致谢
这项工作由国防高级研究计划局根据其编号为。hr0011 - 07 - 9 - 0002。作者感谢IBM HPCS生产力评估团队的成员Catalina Danis、Peter Malkin和John Thomas，感谢他们对这项研究的宝贵贡献。
相关文章
在queue.acm.org
解锁并发
Ali-Reza Adl-Tabatabai, Christos Kozyrakis和Bratin Saha
http://queue.acm.org/detail.cfm?id=1189288
理想的HPC编程语言
尤金Loh
http://queue.acm.org/detail.cfm?id=1820518
软件事务性内存:为什么它只是一个研究玩具?
Calin Cascaval, Colin Blundell, Maged Michael, Harold W. Cain, Peng Wu, Stefanie Chiras和Siddhartha Chatterjee
http://queue.acm.org/detail.cfm?id=1454466
参考文献
1.Asanovic, K.， Bodik, R.， Catanzaro, B.C.， Gebis, J.，丈夫，P.， Keutzer, K.， Patterson, D.， Plishker, W.， Shalf, J.， Williams, S.和Yelick, K.并行计算研究的前景:来自伯克利的观点。技术报告。UCB /电- 2006 - 183。电气工程与计算机科学，加州大学伯克利分校，2006;http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.pdf．
2.Bader, D, Madduri, K, Gilbert, J, Shah, V, Kepner, J, Meuse, T.和Krishnamurthy, A.设计可伸缩的合成紧凑应用基准高生产力计算系统;http://www.cse.psu.edu/~madduri/papers/SSCA-CTWatch06.pdf．
3.Danis, C.和Halverson, C.在研究高性能计算程序员生产力的综合方法中，从观察成分得到的价值。在第三届高端计算生产力与性能研讨会论文集,(2006), 1121。
4.Dijkstra, E.， Feijen, W.和van Gasteren, a .的分布式计算终止检测算法的推导。信息处理信件16， 5(1983)， 217219。
5.Ebcioglu, K.， Sarkar, V.， El-Ghazawi, T.和Urbanic, J.测量三种并行编程语言生产率的实验。在第三届高端计算生产力与性能研讨会论文集,(2006), 3036。
6.Halverson (C.)和Danis (C.)迈向科学计算中程序员行为的生态有效研究。在第一届计算机科学与工程软件工程研讨会论文集,(2008)。
7.Saraswat, va, Kambadur, P.， Kodali, S.， Grove, D.和Krishnamoorthy, S.生命线的全球负载平衡。在16年会议纪要thACM并行编程原理与实践研讨会,(2011), 201212。
©2014 0001 - 0782/14/11 ACM
如果您不是为了盈利或商业利益而制作或分发本作品的部分或全部，并在第一页注明本通知和完整引用，则允许您免费制作本作品的部分或全部数字或纸质副本，供个人或课堂使用。本作品的组成部分必须由ACM以外的其他人享有版权。信用文摘是允许的。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org或传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2014 ACM股份有限公司
评论
R Oldehoeft
鲜为人知的是，已故的Ken Kennedy提出了MPI作为一个运行时库的想法，他的并行编译器可以在它们的实现中使用，从来没有想过这样一个粗糙的库会暴露给人类。他对同事的这个库的要求得到了它自己的生命，现在几十年的HPC程序员已经被要求使用一种非常低级的并行编程风格，从而阻碍了更高效的并行编程方法的开发。为了供人类使用，MPI已经发展成为一个具有巨大API的非常大的库。
杆Oldehoeft
显示1评论