OpenCilk：用于快速任务并行代码的模块化可扩展软件基础设施

10OpenCilk：一种用于快速任务并行代码的模块化和可扩展的软件基础设施0Tao B. SchardlMIT CSAILneboat@mit.edu0I-Ting Angelina Lee华盛顿大学圣路易斯分校angelee@wustl.edu0摘要0本文介绍了OpenCilk，一种用于任务并行编程的开源软件基础设施，它允许在语言抽象、编译策略、运行时机制和产品性工具开发方面进行大量代码重用和设计选择的轻松探索。OpenCilk基础设施包括三个主要组件：一个设计用于编译分叉-合并任务并行代码的编译器，一个高效的工作窃取运行时调度器，以及一个基于编译器插装的工具开发框架，专为分叉-合并并行计算而设计。OpenCilk是模块化的，对于大部分情况，修改一个组件不需要修改其他组件；而且易于扩展，它的构造自然地鼓励代码重用。尽管是模块化且易于扩展，OpenCilk生成高性能代码。我们通过多个案例研究来调查OpenCilk的模块化、可扩展性和性能，包括一个扩展OpenCilk以支持多个并行运行时系统（包括CilkPlus、OpenMP和oneTBB）的研究。OpenCilk的设计使得可以快速原型化新的编译器后端，以针对不同的并行运行时ABI。每个后端只需要不到2000行新代码。我们通过对15个基准Cilk程序进行实证分析，发现OpenCilk在1个核心上的性能比其他运行时平均提高了4%到26%，在48个核心上提高了10%到120%。0关键词：位码、Cilk、编译、编译器插装、分叉-合并并行性、OpenCilk、OpenMP、oneTBB、并行计算、并行运行时系统、产品性工具、Tapir、任务并行性01 引言0广泛部署的多核平台——从个人计算机到移动设备再到超级计算机0PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔，魏桃、I-TingAngelina Lee版权所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.35775090——导致人们对寻找简单的方法来编程它们产生了更多兴趣。任务并行性是一种流行的方法，其中平台提供高级编程抽象来表达计算的逻辑并允许底层运行时系统自动进行负载平衡和同步。任务并行性一直受到研究界的重视，以探索不同的语言抽象（如[11,34,35,55,70,71,79]）、编译技术（如[8,9,25,53,66,80,85]）、调度算法（如[5,6,54,72-75]）、运行时机制（如[4,31,46,49,51,69,78]）和产品性工具（如[28,33,62,65,81-84,86-89]）。任务并行性已被纳入主流编译器[3,30,38,50]和主流编程语言，例如通过Rust中的Tokio运行时中的task::spawn和Go中的goroutine。尽管任务并行性逐渐成为主流，但其软件开发工具链仍然很基础。当前串行语言的编译器通常包括三个阶段：1）前端，用于解析和类型检查输入程序，并将其转换为一个称为中间表示（IR）的目标无关语言；2）中端，对IR进行分析和优化；3）后端，将优化后的IR转换为特定目标的机器代码。串行控制结构在IR中表示，中端在执行优化时考虑其语义。相比之下，现有的任务并行平台（如[7,15,16,23,29,48,56]）将并行控制结构作为语法糖，转换为对运行时库的不透明函数调用。并行结构仅在前端进行处理，其中每个并行结构被转换为一系列与对应的运行时系统调用交替的指令。这种方法有几个缺点。首先，编译过程与特定的并行语言和特定的运行时系统的应用程序二进制接口（ABI）紧密耦合。更改此ABI通常需要同时更改运行时系统和编译器，而编译器的代码库通常比运行时系统大100倍。因此，编译器和运行时系统就像一个难以修改和扩展的整体软件。其次，这种方法只支持最小的代码重用。01 在文献中，任务并行性也被称为协作线程、动态多线程或细粒度并行性。0这项工作采用Creative Commons Attribution International 4.0许可协议。20PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，魏桃、I-Ting Angelina Lee0为基于C/C++的任务并行平台开发的编译器-运行时组合难以移植到不同的语言前端或不同的运行时系统。最后，这种方法可能会影响性能。编译器在很大程度上忽略并行语义，并将对运行时系统的调用视为具有未知副作用的阻塞编译器优化。重新启用编译器优化的努力最终与特定的编译器-运行时ABI绑定在一起。0OpenCilk0本工作旨在改进任务并行性的软件基础设施，以实现大量代码重用和在语言抽象、编译策略、运行时调度和产品性工具开发方面的设计选择的轻松探索。本文介绍了OpenCilk，一种开源软件基础设施，由三个主要组件组成：一个设计用于编译分叉-合并任务并行代码的编译器，一个实现了随机工作窃取的高效运行时系统[12]，以及一个专为分叉-合并并行程序设计的编译器插装工具开发框架Momme。OpenCilk专注于满足三个设计目标：0模块化：修改OpenCilk的一个组件不需要改动其他组件。0可扩展性：OpenCilk的架构自然地鼓励代码重用。0性能：OpenCilk生成高性能代码。OpenCilk基于三种现有技术——LLVM编译器[43,44]、Tapir[66]和CSI[64]，每种技术都无法达到OpenCilk的设计目标。LLVM提供了一个流行的模块化编译器基础架构，能够生成高性能代码，但对并行性的支持有限。Tapir扩展了LLVM的IR，以表达高性能并行代码的分叉-合并并行性。但是Tapir/LLVM编译器——即LLVM中Tapir的原始实现——具有有限的模块化和可扩展性。例如，Tapir/LLVM仅实现了CilkPlus运行时ABI，要扩展Tapir/LLVM以支持其他并行运行时需要大量的、容易出错的编译器开发工作。CSI提供了一个灵活而强大的框架，允许在编译器之外开发的工具使用编译器插入的程序插装，但它不提供对任务并行性的通用支持。此外，CSI依赖于链接时优化（LTO）[76]来生成高性能代码。最后，CSI不支持堆栈分配的工具数据结构，意味着使用CSI编写的工具无法将工具特定的数据插入到待测程序的函数框架中。这个特性可以简化工具开发并提高工具的性能。02 OpenCilk软件基础设施可在https://github.com/OpenCilk免费获取。3Momme是一个传统上用于衡量丝绸面料质量的单位。0为了克服它们的限制，OpenCilk以三个关键方式结合了这些技术并在其基础上构建。首先，OpenCilk编译器建立在Tapir/LLVM之上，并引入了一个降低Tapir的框架，为不同并行运行时系统的ABI提供通用的基础设施。这个框架允许特定运行时系统的ABI被实现为一个简单的插件，称为Tapir目标。因为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，并允许工具将自定义数据结构插入到程序的函数帧中。0OpenCilk的评估0本文通过六个案例研究展示了OpenCilk的模块化和可扩展性。在一项案例研究中，我们通过为OpenMP运行时[61]和Intel oneAPI Threading Building Blocks(oneTBB)[39]添加新的Tapir目标，扩展了OpenCilk以支持多个并行运行时ABI。Tapir降低框架和位码ABI的应用使得快速原型开发成为可能。添加OpenMP和oneTBBTapir目标只需要大约850和750行新代码。在另一个案例研究中，我们扩展了OpenCilk以支持确定性并行随机数生成器（DPRNGs）[49]。在CilkPlus运行时中，为DPRNGs添加高效支持需要修改运行时的ABI，而修改运行时的ABI又需要改变编译器[49, 82]。04 具体来说，是与LLVM一起分发的OpenMP运行时。00.20.40.60.811.200.20.40.60.811.230OpenCilk：用于快速任务并行代码的模块化和可扩展软件基础设施PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔0cilksort0bfs0matmul0strassen0lu0triangle0heat0rectmul0kcore0minife0nqueens0pagerank0fft0qsort0cholesky0T S/ T10heat0minife0strassen0triangle0bfs0kcore0cilksort0qsort0pagerank0nqueens0matmul0lu0rectmul0fft0cholesky0T48（OpenCilk）/T 480OpenMP oneTBB Cilk Plus OpenCilk0图1. OpenMP、oneTBB、CilkPlus和OpenCilk运行时系统在15个基准Cilk程序上的性能比较。左图显示每个可执行文件的工作效率 � � / � 1 ，其中 � �是串行投影的运行时间。右图显示每个可执行文件的48核加速比 � � / � 48，除以使用OpenCilk运行时的相应可执行文件的48核加速比。两个图形的值越高越好。0相比之下，OpenCilk的设计使得我们只需改变运行时系统的代码库就能为OpenCilk运行时系统添加DPRNG支持。此外，这种模块化不会牺牲性能。经修改的OpenCilk运行时系统，为支持DPRNGs提供了两种机制，运行时间比CilkPlus运行时系统（只提供一种机制）快了几何平均值的5%。最后，为了证明OpenCilk生成高性能代码，我们使用OpenCilk将15个基于C/C++的分叉-合并并行程序编译为在OpenCilk运行时、CilkPlus运行时[36]、OpenMP运行时[61]或oneTBB[39]上运行，并比较了生成的可执行文件的性能。图1显示了结果。在图中，左图显示了每个可执行文件的工作效率 � � / � 1 ，其中 � �是程序的串行投影的运行时间，� 1是1个核心上并行可执行文件的运行时间。右图显示了每个可执行文件的48核心加速比 � � / � 48，除以使用OpenCilk运行时的相应可执行文件的48核心加速比。如图所示，OpenCilk运行时系统始终提供与其他运行时系统相当或更好的工作效率和加速比。特别是在48个核心上，OpenCilk运行时比CilkPlus快约10%，比oneTBB快50%，比OpenMP快120%。总之，本文的贡献如下：0•第2节介绍了OpenCilk，这是一个用于分叉-合并并行性的开源软件基础设施，包括编译器、运行时系统和工具开发框架。OpenCilk采用了几种新颖的设计特性，包括Tapir降低框架和位码ABI，使其具有模块化、易于扩展和快速的特点。0•第3节显示OpenCilk比传统方法更容易扩展。通过几个案例研究，我们说明了OpenCilk的设计如何使添加新的语言抽象、运行时机制和快速生产力工具变得容易。0附录A呈现了这些图表所基于的运行时间数据。0新语言抽象、运行时机制和快速生产力工具。0•第4节演示了OpenCilk在实践中生成高性能代码，并经验性地评估了在第3节中讨论的使用OpenCilk基础设施构建的运行时扩展。第5节讨论了相关工作，第6节提供了结论性的评论。附录A介绍了如何设置OpenCilk和基准程序以运行本文中的经验评估。02 OpenCilk系统架构0本节介绍了OpenCilk系统的架构以及使其易于修改和扩展的特性。OpenCilk包括编译器、工作窃取运行时系统[12]和用于开发生产力工具的框架，包括竞争检测器和可扩展性分析器。图2说明了OpenCilk系统架构的关键方面。OpenCilk编译器引入了一个统一的Tapir降低框架，将任务并行程序编译到不同的并行运行时系统中，并引入了Momme框架，以支持生产力工具的开发。图2还显示了OpenCilk运行时系统和OpenCilk工具是如何作为传统库和位码ABI的组合实现的，以便在不牺牲性能的情况下易于修改和扩展。0准备工作0OpenCilk支持（递归地）分叉-合并并行，其中一个函数可以生成一个子任务，从而允许它与其父任务的继续并行执行。一个函数还可以执行同步操作，等待所有生成的子任务完成。任务本身可以生成和同步子任务。我们将任何执行生成操作的函数或任务称为生成函数。目前，OpenCilk编译器支持使用Cilk语法[29]编写的基于C/C++的分叉-合并并行代码，并支持多个运行时系统后端，包括OpenCilk。40PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔Tao B. Schardl和I-Ting Angelina Lee0OpenCilk工具套件0OpenCilk运行时0库0Cilk Plus0运行时库0OpenCilk编译器0Cilkscale0库0Bitcode ABI0Bitcode ABI0修改的Clang0优化0并行代码0Tapir0Tapir0Tapir0Momme0LLVM0IR0汇编0EXE0代码生成0Tapir降低0CilkPlus0Open- Cilk0Open-0MP0汇编0EXE0代码生成0LLVM0IR0LLVM0IR0汇编0EXE0代码生成0链接 链接 链接0OpenMP0运行时库0图2.OpenCilk系统架构图。圆角矩形区分OpenCilk编译器、运行时系统和工具套件。矩形描述了编译器和链接器的阶段。在“Tapirlowering”矩形内的矩形代表Tapir目标。文档形状表示某种形式的代码。高亮显示表示OpenCilk第2节中讨论的关键方面。0运行时，包括Intel Cilk Plus运行时[36]，LLVM14中的OpenMP运行时[61]和Intel的oneTBB运行时[39]。OpenMP和oneTBB的运行时后端仅使用了并行化fork-join代码所必需的OpenMP和oneTBB运行时系统的子集。本节主要讨论OpenCilk的架构时，重点讨论了OpenCilk运行时后端。第3节讨论了其他后端。OpenCilk编译器基于Tapir/LLVM[66]，它扩展了LLVM的IR，以以与语言前端和并行运行时系统无关的方式编码分叉-合并并行。LLVMIR将一个函数表示为控制流图（CFG）（�，�，�0），其中每个顶点�∈�表示一个基本块-一系列指令，控制流必须通过第一条指令进入，并从最后一条指令离开，称为终止器-并且边�表示基本块之间的控制流依赖关系。顶点� 0∈�表示函数的唯一入口点。Tapir在LLVMIR中添加了三个终止器，以表示任务的生成和同步。0将每个生成的任务表示为子CFG，并保证所有任务都是嵌套的。每个基本块只能包含在一个任务�中，这意味着它包含在�的子CFG中，而不是�生成的任务的子CFG中。0Tapir降低框架0OpenCilk编译器实现了一个Tapir降低框架，使得将Tapir降低到不同的并行运行时ABI变得容易。虽然并行运行时系统的ABI有很大的差异，但许多ABI（包括OpenCilk、Cilk Plus[36]、Habanero [7,15]和OpenMP[57]）都具有一些共同的特性。特别是，这些运行时系统都要求生成的任务最终被编码为二进制中的一个函数，以便运行时系统可以使用函数指针在内部引用任务。然而，为了方便编译器优化，Tapir直接在产生函数的CFG中编码生成的任务[66]。为了降低Tapir，Tapir降低框架提供了一种有效地为每个生成的任务创建单独函数的通用工具。0算法1：根据给定的Tapir目标将Tapir降低为并行运行时ABI。0数据：函数�和Tapir目标Target的CFG，结果：一组函数，使得�中的每个并行任务都在单独的函数中进行编码，并且�中的所有Tapir指令都根据Target编码的并行运行时ABI进行转换。01  �  ←  ComputeTaskTree( F ) ;02  �  ← � ,  �  ← � ;03  对于�∈�按后序遍历执行04 如果  children( t )  ≠  �  则05 Target . ApplySpawnerABI( t ) ;06 对于  �  ∈  children( t )  做07 Target . ApplySpawnABI( t, H[c] ) ;08 对于  �  ∈  syncs( t )  做09 Target . ApplySyncABI( y ) ;010 �  [ �  ] ←  ComputeInputs( t, I ) ;011 �  ←  CreateSpawnHelper ( �, �  [ �  ]) ;012 �  [ �  ] ← ( �,  spawnsite( t ) , �  [ �  ]) ;0算法1呈现了Tapir降低框架实现的高级算法的伪代码。该算法基于一个函数�，该函数以带有Tapir指令的CFG的形式给出，并且一个Tapir目标，该目标编码了用于实现特定运行时系统ABI的编译器内部操作。OpenCilk编译器还实现了一种单独但实质上相似的算法，用于降低特定的并行循环。让我们暂时忽略第4-9行对Tapir目标的使用。第1行调用ComputeTaskTree来计算�的任务树，在任务树中，每个顶点表示�中的任务-其中根表示�本身-而边表示一个任务可以生成另一个任务。ComputeTaskTree还将�中的每个基本块与包含它的任务相关联。第3-12行遍历任务树进行后序遍历。对于每个任务�，第4-9行调用Tapir目标来处理�的每个子任务�的生成点-�在其中生成-和�中的每个同步。第10行调用ComputeInputs来计算�[�]的输入集。第11行调用CreateSpawnHelper为�创建一个新的生成助手函数�。第12行记录�，�的生成点和�[�]以供Tapir目标稍后处理。尽管算法1很简单，但ComputeTaskTree、ComputeInputs和CreateSpawnHelper子例程封装了重要的复杂性。这些例程处理实际程序中出现的各种复杂性，例如将具有不同任务的异常处理代码标识出来，处理函数和参数属性，并维护调试信息。Tapir降低框架旨在最大程度地减少Tapir目标处理这些复杂性的需要。算法1还有助于确保降低过程是高效的，通过对所有基本块执行恒定次数的遍历，为函数中的所有任务，包括嵌套任务，创建生成助手。08 }16}24 }31 }50OpenCilk：用于快速任务并行代码的模块化和可扩展软件基础设施PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔0要实现特定的并行运行时ABI，算法1将Tapir目标作为参数。Tapir目标定义一组例程ApplySpawnerABI、ApplySpawnABI和ApplySyncABI，用于根据ABI修改生成函数和生成助手函数的CFG。图3以简单的C伪代码示例形式展示了Tapir降低框架如何使用OpenCilkTapir目标。从概念上讲，图3(a)说明了算法1中第4行之后的生成函数的位置，在算法已为生成的任务创建了生成助手函数（第9行）。Tapir降低框架使用OpenCilkTapir目标将图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后运行了一些简单的优化，包括函数内联、常量传播、公共子表达式消除和死代码消除。0Tapir的目标是0位码ABI0尽管Tapir降低框架可以灵活地将Tapir降低到不同的运行时ABI，但为了更改运行时ABI，仍可能需要更改OpenCilk编译器的内部结构（即Tapir目标）。例如，某些运行时系统ABI在每个生成函数和生成辅助函数中添加了一个局部堆栈帧变量。为了插入这些变量，相应的Tapir目标必须知道该变量的类型定义。因此，更改0a001 int fib(int n) {002 if (n < 2) return n;003 int x, y;004 fib_helper(&x, n - 1);005 y = fib(n - 2);006 同步;007 return x + y;009 void fib_helper(int *x, int n) {*x = fib(n);}0b010 int fib(int n) {011 __cilkrts_stack_frame sf;012 __cilkrts_enter_frame(&sf);013 if (n < 2) {014 __cilkrts_leave_frame(&sf);015 return n;017 int x, y;018 if (__cilkrts_prepare_spawn(&sf))019 fib_helper(&x, n - 1);020 y = fib(n - 2);021 __cilkrts_sync(&sf);022 __cilkrts_leave_frame(&sf);023 return x + y;025 void fib_helper(int *x, int n) {026 __cilkrts_stack_frame sf;027 __cilkrts_enter_helper_frame(&sf);028 __cilkrts_detach(&sf);029 *x = fib(n);030 __cilkrts_leave_helper_frame(&sf);0图3. C伪代码，说明OpenCilkTapir目标如何在并行OpenCilk程序上操作以计算斐波那契数。a是调用Tapir目标之前Tapir降低结果的C伪代码。b是Tapir目标转换后的代码的C伪代码。0将运行时系统中的堆栈帧变量添加到Tapir目标中也需要更改。为了放宽这个要求，OpenCilk引入了用于运行时系统和工具与编译器交互的位码ABI。图2说明了OpenCilk运行时系统由标准库和一个位码ABI文件组成，该文件是一个LLVM位码文件，即LLVMIR的二进制表示，其中编码了OpenCilk编译器运行时ABI的定义。该位码ABI文件包括OpenCilk运行时的堆栈帧变量的类型定义以及运行时ABI函数的定义（例如图3（b）中以__cilkrts_开头的函数）。当Tapir降低运行时，OpenCilkTapir目标在调用其任何例程之前读取和内部化OpenCilk运行时的位码ABI文件，从而允许OpenCilkTapir目标在插入该类型的任何局部变量之前从位码ABI文件获取堆栈帧变量的类型定义。通过使用位码ABI，OpenCilkTapir目标可以实现OpenCilk运行时ABI，而无需进行任何更改。60PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔Tao B. Schardl和I-Ting Angelina Lee0将ABI硬编码到Tapir目标中。因此，可以更改OpenCilk运行时系统，包括其ABI，而无需修改OpenCilk编译器。只要修改后的运行时系统在降低程序的相同位置使用相同的ABI函数和类型名称，就可以使用修改后的运行时系统而不需要对编译器进行任何更改。此外，这种方法不会牺牲性能，因为OpenCilkTapir目标在执行运行时特定的降低之前会读取和内部化OpenCilk运行时的位码ABI文件，这允许内联和优化运行时变量和函数调用。第3节讨论了位码ABI在简化更改OpenCilk运行时系统方面的重要性。0工具开发0OpenCilk提供了支持Momme工具开发框架，该框架支持包括Cilk-san竞争检测器和Cilkscale可扩展性分析器在内的生产力工具。Momme基于CSI框架[64]，允许在编译器之外开发使用编译器插装的工具。Momme在OpenCilk编译器中添加了一个插装阶段，该阶段在被测试程序中插入通用函数调用，称为（插装）钩子，工具可以实现这些钩子来插装任务并行程序。Momme在三个关键方面建立在CSI之上，以便以模块化的方式轻松开发快速的生产力工具。首先，Momme为Tapir指令提供了钩子，允许工具在分叉-合并并行程序中插装生成和同步操作。通过插装Tapir指令，工具可以独立于程序使用的并行运行时系统分析并行控制流。因此，OpenCilk允许工具和并行运行时系统独立修改，而不会破坏彼此的功能。之前的工作（例如[41,42]）已经证明了类似的钩子用于开发并行程序的快速工具的效用。其次，Momme可以选择性地接受工具的位码ABI。这种能力提供了几个优点。Momme可以使用位码ABI来定制插入到被测试程序中的钩子，如第3节所讨论的。Momme还可以使用工具的位码ABI来优化插入的插装。相比之下，CSI依靠链接时优化（LTO）提供类似的功能。0最后，Momme允许工具在位码ABI中可选地定义变量的结构类型，以便代表工具将其插入到每个函数中。Momme因此允许工具使用分配在程序调用堆栈上的存储来简化其实现或实现更好的性能。与Tapir降低框架类似，Momme在插入插装后运行几个简单的编译器优化来优化该插装和任何插入的工具变量。第3节探讨了在Cilkscale的背景下，位码ABI如何支持工具开发。06Schardl等人描述了一种使用编译时优化（CTO）而不是LTO的CSI的替代设计，这与Momme使用位码ABI文件的方式类似。但是，Schardl等人没有实现CTO策略，也没有探索Momme支持的其他功能。0在插入插装后，插入的工具变量及其插装进行优化。第3节探讨了Cilkscale中的这种能力。03个案例研究0本节介绍了六个案例研究，探讨了OpenCilk的模块化和可扩展性。我们描述了使用Tapir降低框架使OpenCilk编译器能够针对不同的并行运行时ABI的经验。我们研究了如何向OpenCilk运行时系统添加对DPRNGs[49,77]的支持。我们讨论了在Kaleidoscope中添加并行语言结构的经验，Kaleidoscope是一个用于教授LLVM内部工作的简单语言[60]。我们研究了如何在OpenCilk前端添加同步词法作用域。我们研究了位码ABI在Cilkscale和Cilksan的背景下如何支持工具开发。0支持多个运行时系统0我们使用Tapir降低框架使OpenCilk编译器能够针对四种不同的并行运行时ABI进行目标化，即针对OpenCilk运行时、CilkPlus运行时、LLVM 14中支持OpenMP 4.5[56]的OpenMP运行时[61]和oneTBB[39]。我们为每个运行时ABI实现了一个独特的Tapir目标。这些目标允许OpenCilk将Cilk程序编译为使用这些运行时系统中的任何一个。Tapir降低框架极大地简化了实现这些Tapir目标的工作量。OpenCilkTapir目标在OpenCilk编译器中大约有1300行代码（加上380行位码ABI文件），而Cilk PlusTapir目标大约有1900行代码，OpenMP和oneTBBTapir目标各不到700行代码（加上80-150行位码ABI文件）。相比之下，Tapir降低框架要大得多，大约有5800行代码。尽管CilkPlus目标类似于OpenCilk目标-因为它们共享相似的运行时ABI-但它不使用位码ABI文件。相反，CilkPlus目标硬编码其运行时ABI，以便将堆栈帧变量和内联运行时函数插入编译代码中。因此，CilkPlus目标包含的代码行数比OpenCilk目标多，这说明使用位码ABI文件可以简化运行时后端实现。此外，即使对CilkPlus运行时ABI进行微小更改也可能需要进行编译器更改，这对于OpenCilk运行时来说并非如此。最后，我们观察到使用位码ABI文件不会影响性能：与CilkPlus相比，OpenCilk运行时在工作效率上获得了可比或更好的结果（图1），尽管它们共享类似的运行时ABI。我们的OpenMP和oneTBBTapir目标使用相应的运行时调度库的子集。OpenMP目标使用实现omp task和omptaskwait指令的OpenMP运行时函数和数据结构[56]。oneTBB目标在每个生成函数中创建一个本地task_group。为了实现70OpenCilk：用于快速任务并行代码的模块化和可扩展软件基础设施PPoPP’23，2023年2月25日至3月1日，加拿大蒙特利尔0在生成一个spawn时，oneTBB目标创建一个C++lambda来执行spawn帮助函数，并在本地task_group上调用run来执行该lambda。在实现一个sync时，oneTBB目标在本地task_group上调用wait。为了简化它们的实现，OpenMP和oneTBBTapir目标使用了位码ABI文件。OpenMP运行时需要初始化特定的数据结构并调用一系列函数来生成一个任务。位码ABI允许我们将这些协议编码为一个小的C源文件，而不是将其硬编码到编译器中。对于oneTBB，task_group.run函数将生成的任务作为C++函数对象（例如C++lambda）传入。我们的实现将C++lambda的构造和调用委托给位码ABI文件，从而避免了在LLVM IR级别处理C++lambda表达式的C++调用约定（如数据打包和名称修饰）的需要。0支持DPRNGs0为了探索OpenCilk架构如何支持任务并行运行时系统的研究，我们研究了如何扩展OpenCilk以支持确定性并行随机数生成器（DPRNGs）[49]。DPRNG在并行程序中以确定性方式生成伪随机数，而不考虑其如何调度。为了支持Cilk程序的DPRNGs，Leiserson等人引入了一种运行时系统扩展，将一个唯一的标签（称为pedigree）确定地分配给计算的每个strand，即不包含并行控制的执行指令序列。通过对pedigree进行哈希，DPRNG库可以在并行情况下确定地为不同的strand生成伪随机数。Leiserson等人展示了CilkPlus运行时系统如何高效地维护pedigree，并将pedigree纳入了Cilk Plus中。CilkPlus的pedigree实现影响其编译器运行时ABI。与OpenCilk运行时ABI一样，CilkPlus运行时ABI为每个生成函数和生成帮助函数添加了一个堆栈帧变量。为了支持pedigree，CilkPlus增加了这个堆栈帧变量及其使用它的运行时ABI中的函数的功能。因此，修改此对DPRNGs的支持（例如，构建一个将Steele等人的优化[77]实现到运行时系统中的DPRNG）需要同时更改CilkPlus的编译器和运行时系统。我们利用OpenCilk运行时系统的位码ABI开发了OpenCilk-DPRNG，这是OpenCilk的一个扩展，它在Leiserson等人的算法[49]的基础上添加了对pedigree的支持以及一个内置的DPRNG，其中包含Steele等人的一些优化[77]。尽管这些更改影响了OpenCilk运行时ABI，但位码ABI允许将这些更改封装在OpenCilk运行时代码库中。第4节介绍了我们对OpenCilk-DPRNG的实证评估，发现它通常比CilkPlus运行时更快，尽管同时保持pedigree和内置的DPRNG。因此，本研究0证明了位码ABI提供了模块化而不会影响性能。0并行化Kaleidoscope0我们探索了如何使用OpenCilk为Kaleidoscope增加对fork-join并行性的支持，Kaleidoscope是LLVM标准教程中使用的一种简单语言[60]。Kaleidoscope是一种具有函数、条件、循环和基本数学运算的过程化语言。LLVM教程实现了一个用于Kaleidoscope的读取-求值-打印循环，该循环使用基于LLVM的JIT编译器来编译和执行代码。为了探索OpenCilk的可扩展性，我们修改了Kaleidoscope教程代码，为Kaleidoscope添加了fork-join并行语言结构，包括用于生成和同步任务以及并行循环的结构。OpenCilk使我们能够通过向Kaleidoscope代码库中添加几百行代码来为Kaleidoscope添加这些结构。我们添加了大约400行代码来解析新的语言结构并为其生成Tapir。我们添加了大约150行代码来修改JIT编译器，以使用OpenCilkTapir目标调用Tapir降低框架，并可选择调用Momme。我们添加了大约100行代码来修改JIT编译器以链接外部库。这些修改足以使程序员能够编写fork-join并行的Kaleidoscope代码，使用OpenCilk进行编译和运行，并可选择使用Cilksan和Cilkscale分析其并行执行。不需要对OpenCilk运行时系统或任何工具进行更改。0添加同步的词法作用域0我们探索了OpenCilk架构如何支持添加cilk_scope语言结构，该结构定义了一个同步生成的子程序的词法作用域，类似于X10/Habanero中的finish语句[7,15]。直观地说，为了支持cilk_scope，OpenCilk编译器的前端在与cilk_scope结束对应的IR的每个点处插入了一个Tapirsync指令。但是，当cilk_scope同步函数的一部分生成的子程序时，会出现一些复杂性。特别是，OpenCilk运行时系统仅支持以二进制函数为粒度同步生成的子计算。为了支持这种情况，我们修改了OpenCilk编译器，将这样的cilk_scope放在自己的函数中。我们通过对OpenCilk编译器进行了一些更改，而无需对OpenCilk运行时系统或任何工具进行更改，来添加对cilk_scope结构的支持。我们添加了两个outline-scope内在函数（简称内在函数），用于界定cilk_scope的开始和结束。由于这些内在函数具有简单的串行语义，大多数编译器分析和代码转换都会忽略它们，这意味着这些内在函数对编译器优化的影响很小。我们扩展了Tapir降低框架，以为由outline-scope内在函数界定的子CFG生成函数。80PPoPP’23，2023年2月25日至3月1日，加拿大蒙特利尔 Tao B. Schardl和I-Ting Angelina Lee0优化Cilkscale0为了研究使用位码ABI的性能影响，我们研究了Cilkscale如何在有或没有位码ABI的情况下实现。Cilkscale使用了Cilkview算法的并行版本[33]来分析fork-join并行程序的并行性——并行加速的潜力。为了实现这个算法，Cilkscale为每个生成的函数维护状态变量。C