OpenCilk：高效的任务并行编程和可扩展性基础设施

1×OpenCilk：一个用于快速任务并行代码的模块化和可扩展的摘要陶湾SchardlMIT CSAILneboat@mit.edu华盛顿大学圣路易斯分校。angelee@wustl.edu- 这使得人们对寻找简单的AP越来越感兴趣，本文介绍了OpenCilk，一个开源的软件基础设施的任务并行编程，允许大量的代码重用和容易探索的设计选择，语言抽象，编译策略，运行时机制，和生产力工具的开发。OpenCilk基础设施由三个主要组成部分组成：一个编译器，旨在编译fork-join任务并行代码，一个高效的工作窃取运行时调度程序，和一个生产力工具开发框架的基础上编译器仪器设计fork-join并行计算。 OpenCilk是模块化的--修改一个组件大部分不需要修改其他组件--并且易于扩展--它的构造自然鼓励代码重用。 尽管是模块化的，易于扩展，OpenCilk产生高性能的代码。我们通过几个案例研究调查了OpenCilk OpenCilk的设计使新的编译器后端能够快速原型化，以针对不同的并行运行时ABI。每个后端需要少于2000行的新代码。 我们在15个基准Cilk程序上对OpenCilk运行时的性能进行了实证研究，发现它在1个核心上的几何平均值为4%-26%，在48个核心上的几何平均值为10%-120%。关键词：位代码，Cilk，编译，编译器插入的指令，fork-join并行，OpenCilk，OpenMP，oneTBB，并行计算，并行运行时系统，生产力工具，Tapir，任务并行1引言多核平台的广泛部署-从个人计算机到移动设备再到超级计算机本作品采用知识共享署名国际4.0许可协议进行许可PPoPP©2023版权归所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.3577509为他们编程。任务并行性1是一种流行的方法，其中平台提供高级编程抽象来表达计算的逻辑并行性，并允许底层运行时系统自动化负载平衡和同步。任务并行性继续吸引研究界的大量关注，以探索不同的语言抽象（例如，[11，34，35，55，70，71，79]），com-脱毛技术（例如，[8，9，25，53，66，80，85]），sched-使用算法（例如，[5，6，54，72-Nisms（例如，[4，31，46，49，51，69，78]），以及生产力工具(e.g.、[28，33，62，65，81任务并行性已被被主流编译器[3，30，38，50]和主流编程语言采用，例如通过Rust [1]中Tokio运行时的task：：spawn和Go [2]中的goroutine。虽然任务并行正在成为主流，其软件开发工具链仍然是初级的。今天1）解析和类型检查输入程序并将其翻译成抽象的目标无关语言（称为中间表示（IR））的前端; 2）对IR执行分析和优化的中间端;以及3）将优化的IR翻译成目标特定的机器代码的后端。串行控制结构在IR中表示，中间端在执行优化时负责它们的相比之下，前任务并行平台（例如，[7，15，16，23，29，48，56]）支持并行控制结构作为对运行时库的不透明函数调用的语法糖。并行构造在前端被排他地处理，其中每个并行构造被转换成与到对应运行时系统中的调用交织的指令序列，该运行时系统通常被链接为单独的库。这种方法有几个缺点。首先，编译过程与特定的并行语言和特定运行时系统的应用程序二进制接口（ABI）紧密耦合。更改此ABI通常需要更改运行时系统和编译器，编译器的代码库通常比运行时系统的代码库大100因此，编译器和运行时系统就像一个难以修改和扩展的单片软件。其次，这种方法只支持最小的代码重用。1在文献中，任务并行也被称为协作线程、动态多线程或细粒度并行。PPoPP陶湾Schardl和I-Ting Angelina Lee2用于基于C/C++的任务并行平台的编译器-运行时组合难以移植到不同的语言前端或不同的运行时系统。最后，这种方法可能会损害性能。编译器在很大程度上忽略了并行语义，对运行时系统的调用被视为具有未知的副作用，从而阻止编译器优化。重新启用编译器优化的努力最终被绑定到特定的编译器运行时ABI（例如，[25]）。OpenCilk这项工作的目的是改善软件基础设施的任务并行，使大量的代码重用和易于探索的设计选择语言抽象，编译策略，运行时调度，和生产力工具的开发。本文介绍了OpenCilk，一个开源软件基础设施2，它由三个主要组成部分组成：一个编译器，旨在编译fork-join任务并行代码，一个高效的运行时系统，实现随机化的工作窃取[12]，以及Momme3工具开发框架，提供专门为fork-join并行程序设计的编译器插装。OpenCilk专注于满足三个设计目标：模块化：修改OpenCilk的一个组件不需要修改其他组件。可扩展性：OpenCilk性能：OpenCilk生成高性能代码。OpenCilk建立在三种现有技术之上-LLVM编译器[43，44]，Tapir [66]和CSI[64]-每一种都没有达到OpenCilk的设计目标。LLVM提供了一个主流的模块化编译器基础设施，可以产生高性能的代码，但对并行性的支持有限Tapir扩展了LLVM的IR，以表达高性能并行代码的fork-join并行性。但是Tapir/LLVM编译器- 在LLVM中的Tapir的原始实现-具有有限的模块性和可扩展性。例如，Tapir/LLVM只实现了Cilk Plus运行时ABI，而扩展Tapir/LLVM以支持其他并行运行时需要大量的、容易出错的编译器开发工作。CSI提供了一个灵活而强大的框架，允许在编译器之外开发的工具使用编译器插入的程序插装，但它不提供对任务并行性的一般支持。此外，CSI依赖于链路时间优化（LTO）[76]来产生高性能代码。最后，CSI缺乏对堆栈分配的工具数据结构的支持，这意味着用CSI编写的工具不能将工具特定的数据插入到被测程序的函数框架中。这样的特征可以简化工具开发并导致更好地执行工具。2OpenCilk软件基础设施可在https：//github上免费获得。com/OpenCilk.为了克服它们的局限性，OpenCilk结合了这些技术，并以三种关键方式构建它们首先，OpenCilk编译器构建在Tapir/LLVM之上，并引入了一个Tapir降低框架，该框架提供了一个通用的基础设施来降低Tapir，即转换Tapir以适应不同并行运行时系统的ABI这个框架允许将特定运行时系统因为Tapir降低框架在Tapir上操作，而不是程序的源代码，所以它允许任务并行程序可互换地使用不同的并行运行时系统，而不管它们的源任务并行语言。其次，OpenCilk引入了位码ABI，这是一种用于实现组件ABI的机制，可以促进模块化和可扩展性。位码ABI允许组件（例如OpenCilk运行时系统或OpenCilk工具套件中的工具）以LLVM位码实现其所有ABI定义。因此，ABI不需要硬编码到OpenCilk编译器中，这与编译器-运行时ABI的传统设计不同。因此，对组件ABI的许多复杂更改可以在不对OpenCilk编译器进行任何更改的情况下实现。此外，位代码ABI确保将编译器运行时ABI与编译器代码库分离不会损害性能。第三，Momme工具开发框架以多种方式扩展了CSI，以支持任务并行程序的有效工具。Momme允许工具基于Tapir的并行表示来检测任务并行程序。因此，Momme支持分析被测程序的逻辑并行性的工具，而不管程序的源语言或并行运行时系统。此外，Momme可以将工具的位码ABI作为输入。 Momme使用位码ABI来优化和定制工具的插装，而无需LTO，并允许工具将自定义数据结构插入到测试中的OpenCilk的评价本文通过六个案例研究来展示OpenCilk的模块化和可扩展性。在一个案例研究中，我们通过为OpenMP运行时[61] 4和英特尔oneAPI线程构建块（oneTBB）[39]添加新的Tapir目标，扩展了OpenCilk 以支持多个并行运行时ABI。Tapir-lowering 框 架 和 位 码 ABI 允 许 快 速 原 型 化 。 添 加OpenMP和oneTBB Tapir目标分别只需要大约850和750行新代码。在另一个案例研究中，我们扩展了OpenCilk以支持确定性并行随机数生成器（DPRNG）[49]。在CilkPlus运行时中，添加对DPRNG的有效在3Momme在日语中是一个传统上用来衡量质量的单位。丝绸面料。4具体来说，OpenMP运行时与LLVM 14一起分发。OpenCilk：A Modular and Extensible Software Infrastructure for Fast Task-Parallel Code PPoPP3////1.210.80.60.40.20OpenMP oneTBB Cilk Plus OpenCilk1.210.80.60.40.20图1. 在15个基准Cilk程序上比较了OpenMP、oneTBB、Cilk Plus和OpenCilk运行时系统的性能。左边的图表示每个可执行程序的工作效率，其中，工作效率是串行投影的运行时间���������右边的图表示每个可执行程序的48核加速比除以使用OpenCilk运行时的相应可���������越高对两个图越好相比之下，OpenCilk的设计允许我们通过仅更改运行时系统的代码库来向OpenCilk运行时系统添加DPRNG支持。此外，这种模块化不会牺牲性能。OpenCilk运行时系统，修改，以提供两种机制，以支持DPRNG，运行的几何平均速度比Cilk Plus运行时系统，它只提供了一个这样的机制5%。最 后， 为 了 证明 OpenCilk产 生高 性 能 代码 ， 我 们使 用OpenCilk编译了15个基于C/C++的fork-join并行程序，这些程序可以在OpenCilk运行时、Cilk Plus运行时[36]、OpenMP运行时[61]或oneTBB [39]上运行，我们比较了结果可执行文件的性能。图1显示了结果。5在图中，左图显示了每个可执行文件������ ��������� 右边的图显示了每个可执行程序���������的48核加速比，48除以使用OpenCilk运行时的相应可执行程序的48核加速比。 如图所示，OpenCilk运行时系统始终提供与其他运行时系统相当或更好的工作效率和加速。特别是，在48个核心上，OpenCilk运行时的几何平 均 速 度 比 Cilk Plus 快 10% ， 比 oneTBB 快 50% ， 比OpenMP快120%。总之，本文的贡献如下：第2节介绍OpenCilk，一个开源的软件基础设施fork-join并行，包括编译器，运行时系统，和工具开发框架工作。OpenCilk采用了几个新颖的设计功能，包括Tapir降低框架和位代码ABI，使其模块化，易于扩展和快速。第3节展示了OpenCilk比传统方法更容易扩展通过几个案例研究，我们说明了OpenCilk的设计如何使其易于添加5附录A给出了这些图的运行时间数据新的语言抽象、运行时机制和快速生产力工具。第4节演示了OpenCilk在实践中产生高性能代码，并根据经验评估了使用第3节中讨论的OpenCilk基础设施构建的运行时扩展。第5节讨论了相关的工作，第6节提供了结论性的评论。 附录A描述了如何设置OpenCilk和基准程序来运行本文中的实证评估。2OpenCilk系统架构本节介绍OpenCilk系统架构以及使其易于修改和扩展的功能。 OpenCilk包括一个编译器，一个工作窃取运行时系统[12]，以及一个用于开发生产力工具的框架，包括一个竞争检测器和一个可伸缩性分析器。 图2展示了OpenCilk系统架构，其中突出显示了关键方面. OpenCilk编译器引入了统一的Tapir降低框架，以将任务并行程序编译到不同的并行运行时系统，以及Momme框架，以支持生产力工具的开发。图2还显示了OpenCilk运行时系统和OpenCilk工具如何实现为传统库和位代码ABI的组合，以使它们易于修改和扩展而不牺牲性能。预赛OpenCilk支持（递归）fork-join并行，其中函数可以产生子任务，从而允许它与其父任务的延续并行执行。一个函数也可以执行同步，以等待它的所有派生子任务完成。任务本身可以产生和同步子任务。我们将执行派生的任何函数或任务称为派生函数。目前，OpenCilk编译器支持使用Cilk语法编写的基于C/C++的fork-join并行代码和多个运行时系统后端，包括OpenCilkTS/T1cilksortbfsmatmulstrassen吕三角热矩形kcoreminifenqueenspagerank快速傅立叶CholeskyT48（OpenCilk）/T48热小 斯 特拉 森三 角形bfskcorecilksortqsortpageranknqueensmatmul卢赖克穆尔快···PPoPP陶湾Schardl和I-Ting Angelina Lee4并行代码改良型貘OpenCilk工具套件锡尔克斯优化貘比特码ABI图书馆妈妈貘OpenCilkTapir降低运行时Bitcode ABI图书馆OpenMP运行时库Cilk Plus运行时库∈∈（）下一页∅∈∈∈打开-MPLLVMIRCilkPlusLLVMIR打开-CilkLLVMIR密码-密码-密码-GenGenGenASMASMASM链路链路链路EXEEXEEXE图2. OpenCilk系统架构图。圆角矩形区分OpenCilk编译器、运行时系统和工具套件.矩形描述编译器和链接器阶段。“Tapir降低”矩形内的矩形表示Tapir目标。文档形状以某种形式表示代码 突出显示了第2节中讨论的OpenCilk的关键方面。运 行 时 ， Intel Cilk Plus 运 行 时 [36] ， LLVM 14 中 的OpenMP运行时[61]和IntelOpenMP和oneTBB的运行时后端仅利用并行化fork-join代码所需的OpenMP和oneTBB运行时系统的子集。在讨论OpenCilk的架构时，本节重点讨论第3节讨论其他后端。OpenCilk编译器基于Tapir/LLVM [66]， 它扩 展 了LLVM的IR，以独立于语言前端和并行运行时系统的方式编码fork-join并行性。 LLVM IR将函数表示为控制流图（CFG）���������，其中每个顶点控制流表示基本块-一个指令序列，其中控制流必须通过第一个指令进入并从最后一个指令离开，这被称为终止符- 并且边缘控制流表示基本块之间的Vertex0表示函数���Tapir在LLVMIR中添加了三个终止符来表示任务的生成和同步。貘将每个派生的任务表示为subCFG，并保证所有任务都嵌套良好。 每个基本块最多包含在一个任务 中，这意味着它包含在派生任务的subCFG 中，而不是派生任务的subCFG 中。降塔架OpenCilk编译器实现了一个Tapir降低框架，以使其易于将Tapir降低到不同的并行运行时ABI。 尽管并行运行时系统的ABI有很大不同，但许多ABI，包括OpenCilk、CilkPlus [36]、Habanero [7，15]和OpenMP的ABI[57]有几个共同点特别是，这些运行时都需要一个派生的任务最终被编码为二进制的函数，这样，例如，运行时系统可以使用函数指针在内部引用任务。然而，Tapir直接在派生函数的CFG中编码派生任务，以促进编译器优化[66]。 为了降低Tapir，Tapir-lowering框架提供了一个通用工具来有效地为每个派生的任务创建一个单独的函数。算法1：根据给定的Tapir目标将Tapir降低到并行运行时ABIData：一个函数 的CFG和一个Tapir目标Target。结果：一组函数，使得每个并行任务都在一个单独的函数中编码，所有Tapir指令都在根据由Target编码的并行运行时ABI来转换对象。1 System.out.println（F）;2←，←;3 为在事后订购时，4ifchildren（t）5目标。int n（t）;6个儿童（t）做7目标。int n（t，n）;8因为同步（t）做9目标。int n（i）;10[]←ComputeInputs（t，I）;11←SpawnHelper（���，[]）;12[] ←（，spawnsite（t），���[ ]）;������算法1给出了Tapir降低框架实现的高级算法的伪代码 该算法 以具有Tapir指令的CFG和Tapir目标的形式对函数进行操作，Tapir目标编码编译器内部操作以实现特定运行时系统的ABI。OpenCilk编译器还实现了一个单独的，但实质上类似的算法，特别是减少并行循环让我们浏览一下算法1，暂时忽略第4-9行中Tapir目标的使用。第1行调用ComputeTaskTree来计算任务树���，其中每个顶点表示中的一个任务���-其中根表示���其本身 - 而 边 表 示 一 个 任 务 可 以 产 生 另 一 个 任 务 。ComputeTaskTree还将中的每个基本块���与包含它的任务相关联。第3OpenCilk编译器OpenCilk：A Modular and Extensible Software Infrastructure for Fast Task-Parallel Code PPoPP5[客户端][客户端]后订单。 对于每个任务���，第4 ������- ������9行调用Tapir目标来处理每个子任务的派生站点（在CFG中派生的位置）和每个同步。第10行调用ComputeInputs来计算输入的集合numb���。���第11行调用SpawnHelper来创建一个新的spawn helper函数spawn。第12行记录了footswitch（footswitch的生成站点）和���footswitch（供Tapir目标稍后处理虽 然 算 法 1 很 简 单 ， 但 ComputeTaskTree 、ComputeInputs和DataSpawnHelper子例程封装了相当大的复杂性。这些例程处理真实程序中出现的各种复杂性，例如识别具有不同任务的异常处理代码、处理函数和参数属性以及维护调试信息。Tapir-lowering框架旨在最小化Tapir目标本身处理这些复杂性的需求 算法1还有助于确保降低过程是有效的，通过在所有基本块上执行恒定数量的传递，为函数中的所有任务（包括嵌套任务）创建派生助手。貘靶为了实现特定的并行运行时ABI，算法1将Tapir目标作为参数 。 Tapir 目 标 定 义 了 一 组 例 程 ApplySpawnerABI 、ApplySpawnABI和ApplySyncABI，用于根据ABI修改生成和生成帮助函数的CFG。图3给出了一个简单的C伪代码示例，展示了Tapir降低框架如何使用OpenCilk Tapir目标。概念上，图3（a）示出了在算法1中的行4的点处的产生函数，在算法已经为产生的任务（行9）创建了产生帮助器之后。 Tapir-lowering框架使用OpenCilk Tapir目标从图3（a）生成图3（b），如下所示。 ApplySpawnerABI插入第11、12、14和22行。ApplySpawnABI插入第26、27、28和30行，并将第4行转换为第18-19行。 ApplySyncABI将行6转换为行21。某些运行时ABI要求将ABI函数内联到其调用者中，以确保正确性或性能。 为了支持这样的ABI并通常优化运行时ABI代码，Tapir降低框架在对所有函数运行算法1之后运行一些简单的优化，包括函数内联，常数传播，公共子表达式消除和死代码消除。比特码ABI尽管Tapir降低框架可以灵活地将Tapir降低到不同的运行时ABI，但它仍然需要更改OpenCilk编译器的内部（即，Tapir目标），以便更改运行时ABI。例如，一些运行时系统ABI会为每个派生函数和派生帮助程序添加一个本地堆栈框架变量。要插入这些变量，相应的Tapir目标必须知道变量的类型定义。因此，更改一B图 3. C- 伪 代 码 ， 说 明 OpenCilkTapir 目 标 如何在 并 行OpenCilk程序上操作以计算Fibonacci数。在调用Tapir目标之前Tapir降低的结果的C伪代码 b C-伪代码，说明了Tapir目标转换的（a）代码。运行时系统中的stack-frame变量也需要改变Tapir目标。为了放宽这一要求，OpenCilk为运行时系统引入了位代码ABI，并引入了与编译器交互的工具。图2说明OpenCilk运行时系统由标准库和位代码ABI文件组成，位代码ABI文件是 LLVM 位 代 码 文 件 -LLVMIR的二 进 制 表 示 - 对OpenCilk编译器运行时ABI的定义进行编码。该位码ABI文件包括OpenCilk运行时的堆栈帧变量的类型定义以及运行时ABI函数的定义（例如，cilkrts_stack_frame和图3（b）中名称以cilkrts_开头的函数）。 当Tapir降低运行时，OpenCilk Tapir目标在其任何例程被调用之前读入并内化Open-Cilk运行时的bitcode-ABI文件，允许OpenCilkTapir目标在插入任何该类型的局部变量之前从bitcode-ABI文件中获取堆栈帧变量的类型定义。通过使用位代码ABI，OpenCilk Tapir目标可以实现OpenCilk运行时ABI，而无需010203040506070809public intfindDuplicate（ intn）{if（n2）returnn;intx，y;fib_helper（x，n-1）; y=fib（n-2）;<同步;返回x+y;}voidfib_helper（ int*x， intn）{fib（n）;}10111213141516171819202122232425262728293031public intfindDuplicate（ intn）{ int findDuplicate（intn）;public intfindDuplicate（n）{

下载后可阅读完整内容，剩余1页未读，立即下载