可在www.sciencedirect.com在线获取理论计算机科学电子笔记330（2016）5-25www.elsevier.com/locate/entcs基于JIT的动态程序转换成本分析John Magnus Morton1，4 Patrick Maier2，4 Phil Trinder3，4格拉斯哥大学计算机科学学院英国摘要跟踪JIT编译会生成易于分析且已知会频繁执行的编译单元。AJITPar项目研究JIT跟踪中的信息是否可用于动态转换特定并行架构的程序。因此，JIT跟踪需要一个轻量级的成本模型。本文介绍了一个从Python JIT编译器中提取JIT跟踪信息的系统的设计与实现。我们定义了三个越来越多的参数化成本模型的Pyrocket跟踪。 我们使用线性回归确定成本模型参数的最佳权重。我们评估的有效性的成本模型预测转换程序的相对成本保留字：成本模型，JIT制造商，程序转换，骨架，并行化1引言通用硬件领域主要是并行架构-多核、众核、集群等。编写高性能的并行代码对于固定的架构来说并不简单，但是如果目标架构事先不知道，或者如果代码打算在一系列架构中移植，那么就更难了现有的解决性能可移植性问题的方法，例如OpenCL[21]，或者更高的设备抽象，但保留了一个相当低级的编程模型，通常用于特定的问题域，例如。用于数值数据并行问题。在其他领域中，对多种体系结构的语言支持较少。例如，符号计算，如组合搜索或计算代数，通常表现出很大程度的并行性，但并行性是不规则的：1 电子邮件：research.gla.ac.uk2 电子邮件：Patrick. glasgow.ac.uk3 电子邮件：Phil. glasgow.ac.uk4这项工作由英国EPSRC资助AJITPar（EP/L000687/1）。http://dx.doi.org/10.1016/j.entcs.2016.12.0121571-0661/© 2016由Elsevier B. V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。6J.M. Morton等人/理论计算机科学电子笔记330（2016）5并行任务的数量和大小是不可预测的，并且并行任务通常以高速率动态创建[28]。自适应即时并行（AJITPar）项目[2]研究了一种新方法，通过将声明性任务并行与动态调度和动态程序转换相结合，为跨一系列架构的不规则并行程序提供可移植的并行性能具体来说，AJITPar建议通过在运行时转换任务来调整任务粒度以适应架构，从而根据架构改变并行度。为了促进动态转换，AJITPar将利用Racket语言及其最近基于跟踪的JIT编译器Pyrocket的动态特性 [13，10]。动态任务调度和任务转换都受益于预测的任务运行时间。本文研究了如何为JIT跟踪构建轻量级成本模型。JIT跟踪是通过编译器识别为经常执行的程序控制流程图的简单线性路径。我们假设，即使是非常简单的成本模型也可以产生足够准确的预测，因为轨迹具有非常有限的控制权，我们只需要比较转换前后表达式的相对本文的主要贡献如下。我们已经设计并实现了一个从Python JIT编译器中提取JIT跟踪信息的系统（第3节）。我们已经为JIT跟踪定义了3种成本模型，从非常简单的到参数化的，我们还使用了一个基于Python基准测试套件的回归分析来自动调整特定于架构的成本模型参数（第4节）。我们已经证明，调整成本模型可以用来准确地预测转换程序的相对执行时间（第5节）。2相关工作2.1AJITPar自适应实时并行化（AJITPar）项目[2]旨在研究一种新方法，为跨一系列架构的不规则并行程序提供可移植的并行性能该方法结合了声明式并行与即时（JIT）编译，动态调度和动态转换。该项目旨在研究基于任务图的自适应调度器（AS）库的性能可移植性潜力，以及相关的并行执行框架，动态调度和自适应转换的任务图。我们将并行性的常见模式表示为一组相对标准的算法框架[17]，以及相关的转换。动态转换尤其依赖于动态编译代码的能力，这是将框架基于JIT编译器的主要原因。此外，基于跟踪的JIT编译器可以通过动态配置和/或动态跟踪成本分析来提供任务粒度的估计，并且这些可以由动态调度器利用。由于函数式程序易于转换，因此选择了基于跟踪的JIT编译函数式语言;动态编译允许更广泛的转换，包括依赖于运行时信息的转换J.M. Morton等人/理论计算机科学电子笔记330（2016）57而基于跟踪的JIT编译器构建可能被计算成本的中间数据结构（跟踪）。在本文中描述的工作的目的是确定一个系统，用于计算相对成本的痕迹，这将被用来确定调度的并行任务的基础上，其相对成本，并选择适当的转换，以优化并行工作中的任务。2.2跟踪JIT基于解释器的语言实现，其中程序在虚拟机上而不是在真实处理器上执行，通常出于各种原因而使用- 包括易用性、动态行为和程序可移植性，但与静态编译语言（如C或FORTRAN）相比，它们的性能通常较差。JIT编译是一种允许解释型语言通过动态地将程序的常用部分编译为机器码来显著提高其性能的技术这使得解释器或虚拟机语言能够接近静态编译程序所达到的性能水平，而无需牺牲可移植性。动态编译还允许执行可能无法静态使用的优化JIT编译并不是在程序执行时编译整个程序，而是编译程序中经常执行的小部分（这些部分被描述为热）。最常见的编译单元是函数（或方法）和跟踪[8]。一个跟踪由一个线性指令序列组成，它构成了循环体的一次迭代。一个完整的跟踪不包含任何控制流，除了在执行可能离开跟踪的点;这些点被称为警卫。与作为编译单元的函数相比，跟踪的主要好处是它可以形成跨越多个函数的循环的整个主体，而不仅仅是单个函数的主体2.3RPython工具链我们使用的特定JIT技术是RPython工具链的一部分。PyPy [32]是Python编程语言[33]的替代实现，以Python作为其实现语言而闻名PyPy是使用Python语言的一个子集RPython实现的，工具链旨在用作通用编译器工具链。Smalltalk [12]和Ruby [39]是在RPython工具链上实现的语言的例子PyPy有一个基于跟踪的JIT，RPython工具链允许将JIT轻松添加到新的解释器实现中PyPy [13]是Racket语言的一个实现，它建立在PyPy 的工具链上. Racket是Scheme Lisp的衍生[37]，具有许多额外的功能。 Python使用Racket前端编译Racket的一个子集，抽象语法树（AST）的JavaScript对象表示法（JSON）表示，并使用RPython工具链构建的解释器来解释8J.M. Morton等人/理论计算机科学电子笔记330（2016）5AST。使用RPython构建的JIT值得注意的是，它们是元跟踪[11]。JIT不是跟踪应用程序级别的循环，而是跟踪实际的解释器循环本身。解释器将注释应用程序循环开始和结束的指令，以便执行适当的这样做的目的是为了让编译器编写者不需要为每一种针对RPython/PyPy的新语言编写新的JIT，他们只需要提供注释。2.4成本分析资源分析在资源有限的系统（如大多数嵌入式系统）、需要定时保证的硬实时系统以及指导程序重构或转换中非常重要在这里，我们寻求一个静态的资源分析，通知动态程序转换。近年来，资源分析的理论和实践都取得了重大进展。在FOPARA研讨会[19]和TACLe EU COST行动[38]中报告了一些这种情况分析技术存在于一系列程序资源中，例如执行时间[41，1，34]，空间使用[36，26]或能量[22]。 这里感兴趣的资源是预测的执行时间。对于许多应用，例如嵌入式和实时软件系统，最重要的性能指标是最坏情况下的执行时间。已经建立了各种工具[41，20，1]来静态估计或测量这一点;一个例子是aiT [20]，它使用控制流程分析和低级工具的组合，例如缓存和流水线分析。缓存和流水线分析试图预测程序的缓存和处理器流水线行为，并使用抽象解释在aiT中执行。然而，这里我们预测的是预期的执行时间，而不是最坏情况下的执行时间。此外，我们不需要精确的绝对成本：近似的相对成本应该允许转换引擎在替代重写之间进行选择。一系列的分析技术被用来估计程序使用的资源。 可以对语法结构执行高级成本分析， 程序的源代码，例如使用C语法结构的数学函数来估计执行时间。代码和字节码的低级表示可以用作静态资源分析的源[3，4，26，7，6]。例如，Java的COSTA工具[4]允许使用参数化成本模型分析各种资源，而CHAMELEON工具[7]建立在这种方法的基础上，并使用它来调整程序。在成本分析中有许多其他方法，包括摊销资源分析[23，6]，增量资源分析[5]，并试图使用证明携带代码[6，9]（MOBIUS项目是一个主要的例子）来执行资源保证控制流程是许多资源分析的关键要素[41，20]。但是，由于JIT跟踪不包含任何控制流程，因此这些类型的分析是多余的，因此可以使用更简单的方法这是幸运的，因为静态分析必须运行作为JIT编译程序执行的预热阶段的一部分。我们的工作是将资源分析应用于并行计算的工作的一部分lelism [40，3，34].J.M. Morton等人/理论计算机科学电子笔记330（2016）592.5代码变换程序转换是优化编译器的核心。例如，GHC通过等式重写积极优化Haskell代码[24，25]。转换也可以用于优化并行性能。[17]第十七话- 高级并行抽象或设计模式-可以通过代码转换来调整，以最佳地利用输入数据的结构或针对特定硬件体系结构进行优化。这方面的例子包括PMLS编译器[35]，它通过基 于 对 象 代 码 分 析 数 据 转 换 骨 架 来 调 整 并 行 ML 代 码 ， 以 及 ParaphraseProjectPMLS是标准ML的自动并行化编译器，它将嵌套的顺序高阶函数调用转换为并行骨架调用，并基于程序子部分的运行时行为执行代码转换;与AJITPar不同，这些转换完全是并行的，并且没有尝试解决性能可移植性的问题。PARTE使用重构来允许引入并行框架和现有并行框架的转换;这些重构完全是提前应用的，并且是在用户的指令下应用的，而转换则是由对象轮廓化驱动的。3语言基础结构3.1Pyrocarbon Trace结构JIT跟踪由解释器记录的一系列指令组成，如果返回到跟踪（或循环）开始处的跳转次数高于给定阈值，则跟踪变为热跟踪，这表明跟踪可能被频繁执行，值得编译。Python跟踪中的其他重要概念包括：guards：在执行失败时导致执行离开跟踪的断言;bridge：从经常失败的guard开始的跟踪;以及trace graphs：表示跟踪集合。跟踪图的节点是入口点（循环或桥的入口点）、标签、保护和跳转指令。跟踪图的边是有向的，指示控制流程。请注意，控制流只能在守卫处发散，只能在标签或入口点处合并。 跟踪片段是跟踪的一部分，从标签开始，在跳跃时，在连接有桥的警卫处，或者在另一个标签处，中间没有标签。图1中的清单显示了一个Racket程序，它在一个双重嵌套循环中递增累加器，对于外部循环的每次迭代，执行外部循环105次，内部循环105次，因此计数到1010。图1还显示了Pyrocast生成的跟踪图。节点表示与通过循环的控制流程相关的指令。在图中，标签由l个节点表示，g个节点表示防护，j个节点表示跳转指令。内环（首先变热）对应于从l2到j1的路径，外环对应于桥。联合调查队10J.M. Morton等人/理论计算机科学电子笔记330（2016）5（d efine100000美元）（d efine（100，000美元）（d efine（i n n e rITERacc）（i f（> iter 2）ACC（i n n e r （+ITER第一章 （+ACC（1）（d efine（外ITERacc）（i f（> iter 1）ACC（o ute r（+ITER第一章 （i n n e r0acc）（外部0 0）Fig. 1. Racket中的双套圈及相应的Pyrocket迹图l a b e l（i 7，i 13，p1，d e s c r=TargetToken（4321534144））debug_merge_point（0，0，'（l e t（[ i f_ 0（>ITER（见附件2）]）...）’) guard_not_invalidated ( d e s c r=i 14=int_gt（i 7，100000）guard_false（i 14，d e s c r= Guard0x10196a170 >）[ i 13，i 7，p1 ]debug_merge_point（0，0，'（i f i f_ 0 acc . . .）debug_merge_point（0，0，'（l e t（[ AppRand0_0. . . ]. . .）. . . "i 15= int_add（i，第一章debug_merge_point（0，0，'（+ACC1 ) ’ ) i 16 = int_add_ovf ( i 13 , 1guard_no_overflow（d e s c r= Guard0x10196a100 >）[ i 16，i 15，i 13，i 7，p1 ]debug_merge_point（0，0，'（i n n e r AppRand0_0 AppRand1_0）'）debug_merge_point（0，0，'（l e t（[ i f_ 0（>ITER（见附件2）]）...）跳跃（i 15，116，p1，d e s c r=TargetToken（4321534144））图二、从l2到j1的碎片编译器展开循环一次以优化循环不变代码，产生从l1到l2的路径跟踪图是读取跟踪片段的方便表示。在这个例子中，有以下四个片段：l1到l2、l2到g2、l2到j1和l3到j2。跟踪片段可以重叠：例如，l2到j1与l2到g2重叠。图2显示了一个示例跟踪片段，l2到j1，对应于内部循环。除了调试指令外，该片段还包括3条算术逻辑指令和3个保护（只有第二条经常失败，需要连接桥接器）。开头的标签将范围3变量带入：循环计数器i7、累加器i13和指针p1（在此片段中不起作用）。结尾处的跳转将控制权转移回开头，同时也复制更新后的循环计数器和累加器分别为i15和i16至i7和i13循环入口l1l2g1G2G3桥梁入口b2J1L3J2J.M. Morton等人/理论计算机科学电子笔记330（2016）5113.2访问跟踪和计数器RPython工具链为语言开发人员提供了一组丰富的API来与通用JIT引擎进行交互。在这些API中，有许多回调可以拦截跟踪的中间表示，无论是在记录之后还是在优化之后。我们使用后一个回调函数来获得优化的跟踪以进行成本分析。在调试模式下，RPython可以用计数器记录跟踪，记录控制到达入口点或标签的频率。RPython提供了在运行时检查这些计数器值的方法。AJITPar将在未来使用此功能，从其组成跟踪片段的成本和频率中获得整个循环嵌套的成本估计。现在，我们在程序终止时转储计数器，并使用此信息来评估跟踪成本分析的准确性（第4节）。JIT编译器计算到达标签的次数，但我们更感兴趣的是计算跟踪的执行次数不幸的是，我们的系统收集的完整跟踪幸运的是，我们可以计算出跟踪片段的执行计数，因为在守卫和他们的桥之间存在一一对应的关系基本上，片段l到g的频率是连接到保护g的桥的频率。痕迹碎片是我们可以准确计数的痕迹中最大的离散部分。从l开始并且不以保护结束的片段的频率是标签l的频率减去从l开始的所有较短跟踪片段的频率。L.表1和表2在嵌套循环示例的跟踪片段上演示了这一点。前两列显示JIT计数器，其余三列显示四个跟踪片段的频率，以及它们是如何从计数器派生的。请注意，并非所有计数器都达到循环边界所期望的值。这是因为计数只在代码编译后才开始; JIT编译器预热阶段的迭代会丢失。当前循环的热度阈值为131。JIT计数器JIT计数nl1100,001nl210,000,098,957nb299,801nl399,800表1图1中程序的JIT计数器和计数。3.3JIT指令类在讨论成本模型时，将RPython JIT指令分类为不同的集合是有用的我们从所有指令的集合开始。最初，决定将all细分为两个子集：设置调试指令debug和all12J.M. Morton等人/理论计算机科学电子笔记330（2016）5片段频率表达式频率l1至l2nl1100,001L2到G2nb299,801L2至J1L3至J2nl2−nb2nl 39,999,999,15699,800表2图1中程序的JIT计数器和跟踪片段频率。其他指令;这是基于调试操作被优化移除并且不计入运行时执行成本的想法。进一步的理论是，一些指令将比其他指令更昂贵。所有非调试指令的集合根据其预期的相对性能进一步细分为高成本指令高和低成本指令低。类示例指令调试数字守卫分配数组对象debug_merge_pointint_add_ovfguard_truenew_with_vtablearraylen_gc获取字段_gc表3RPython JIT指令类指令的进一步分类可以基于它们的概念分组进行，并且不假设它们的性能特征。这些类是对象读写指令、对象保护、数字指令、内存分配指令、数组指令。表3中描述了这些类别。跳转指令被忽略，因为在跟踪中只有一个。外部调用被排除在外，因为两个外部函数调用可以做完全不同的事情。图3中显示的JIT操作直方图取自所有交叉实现基准生成的跟踪，显示总体上这些跟踪也由来自守卫、对象和数值类的指令支配4基于JIT的成本模型在JIT编译过程中，Pyrocast生成的跟踪为成本分析提供了极好的线性控制流程使跟踪易于分析，并且跟踪仅针对足够“热”的代码生成，在本节中，我们根据从Pyrocode收集的跟踪信息J.M. Morton等人/理论计算机科学电子笔记330（2016）513图3.第三章。跨实现Python基准测试中最常见的指令4.1跟踪成本模型我们从单个跟踪的成本模型开始。设Tr是长度为n的任意迹，即Tr=op1. opn是指令opi的序列。跟踪成本模型γ是将Tr映射到其预测跟踪成本γ（Tr）的函数，其中γ（Tr）是无量纲数，（理想地）与执行Tr的时间成比例。由于Tr的运行时间可能取决于硬件架构，因此跟踪成本模型可能专用于特定架构。4.1.1成本模型（CM0）最简单的跟踪成本模型为每个跟踪分配相同的成本，而不管它的长度和包含的指令。这个零成本模型的目的是作为一个基准，用来比较其他成本模型的准确性。使用这个模型来计算整个程序的成本（4.2节）可以被认为大致等同于使用循环计数控制流分析来估计程序的执行时间注意，零成本模型是与架构无关的。γ（Tr）= 1（1）4.1.2计数成本模型（CMC）一个稍微复杂一点的跟踪成本模型声明跟踪的成本是它的长度，计算指令的数量（忽略调试指令，这些指令不在运行时执行）。该计数成本模型由等式（2）定义，并且与架构无关。γ（Tr）=γ.0，如果opi∈debug（二）i=11、 否则n14J.M. Morton等人/理论计算机科学电子笔记330（2016）5⎧⎪⎪⎪⎪⎩γ（Tr）=γΣ如果OP，则为∈数值4.1.3加权成本模型（CMW）某些类型的指令可能具有更长的执行时间，例如存储器访问可能比寄存器访问慢几个数量级通过对3.3节中描述的每个指令类应用加权因子，可以获得更复杂的成本模型。等式（3）显示了这个加权成本模型的定义，由抽象权重a、b、c、d和e参数化。0， 如果opi∈debug a， 如果opi∈arrayn我i=1c， 如果opi∈alloc d， 如果opi∈guard e，如果opi∈object模型的准确性取决于具体的权重，而权重的选择取决于实际的架构。第4.3节演示了如何为合理精确的模型获取具体4.2全项目成本模型P是一个程序。 在P的执行期间，JIT编译器生成m不同的轨迹Trj和m个相关的轨迹计数器nj。给定一个（空、计数或加权）跟踪成本模型γ，我们通过对所有跟踪的成本求和来定义P的（空、计数或加权）成本Γ（P），每个跟踪都由其执行频率加权;见公式（4）的正式定义。MΓ（P）= njγ（Trj）（4）j=1请注意，Γ不是一个预测成本模型，因为它的定义依赖于跟踪和跟踪计数器，后者仅在程序执行后可用然而，如第5节所示，Γ仍然可以用于预测转换的成本。4.3CMW的校准砝码为了使用抽象的加权成本模型CMW（第4.1.3节），必须找到加权参数a，. e在等式（3）中。理想情况下，程序成本r（P）与程序运行时间t（P）成比例。也就是说，理想情况下，k>0，使得等式（5）对于所有程序P都成立。Γ（P）=k t（P）（5）给定足够多的程序，我们可以使用等式（5）通过线性回归来校准给定架构的CMW的权重，如第4.3.2节所详述。（J.M. Morton等人/理论计算机科学电子笔记330（2016）515Σ⎪⎩Σ 2004年4月。797×10−3，如果工作2004年。623×10−4， 如果opi∈guardγ（Tr）=我∈alloc（i=14.3.1基准为 了 校 准 权 重 ， 我 们 使 用 了 标 准 Python 基 准 套 件 pycket-bench[31] 和RacketProgramming Languages Bench-mark Game套件[18]中的41个程序使用的程序是完整套件的一个子集，因为导致基准测试运行失败或包含外部函数调用的程序被省略。外部函数调用被删除，因为任何两个外部函数调用都不可能做相同的事情或花费相同的时间。对于每个程序，我们记录执行时间，平均超过10次运行。我们还记录所有跟踪和所有跟踪计数器的值;因为所有基准测试都是确定性跟踪，跟踪计数器在运行之间不会变化用于这些实验的Python版本是我们自定义fork的跟踪分析分支的修订版e56ba66d71，使用RPython工具链的Racket版本6.1和修订版79009构建。 实验在16核2.0 GHz Xeon服务器上运行，具有64 GB RAM，运行Ubuntu 14.04。4.3.2线性回归选取k的任意值，例如k=1，我们从等式（5）和（4）导出以下关系。MLt（Pl）=Γ（Pl） +l=nljγ（Trlj） +l（6）j=1Pl是第l个基准程序，生成ml个跟踪Trlj和跟踪计数器nlj，t（Pl）是Pl的观察到的平均运行时间，并且m（Pl）是误差项。方程（6）通过根据其定义（3）扩展γ而成为线性回归模型，这将右侧变为五个未知权重a，.的线性表达式， e.权重被隐式地约束为非负的，因为负权重将暗示对应的指令花费负时间来执行，这在物理上是为了遵守非负约束，权重通过非负最小二乘线性回归来估计。2004年4月。884×10−4，如果opi∈numeric0，否则等式（7）显示了Xeon服务器架构的加权成本模型。该模型仅将非零成本归因于分配、数值指令和保护，这意味着对象和数组访问指令的成本可以忽略不计。该成本模型的回归拟合如图4所示。拟合显然是线性的，但相当粗糙，表明CMW不是一个非常准确的模型。有一个异常值（trav 2基准测试K16J.M. Morton等人/理论计算机科学电子笔记330（2016）5图四、使用线性回归确定CMW的执行时间与成本而不是编译的代码，由于缺乏跟踪输出来衡量，导致低估了成本我们注意到CMC和CM0的线性回归拟合明显比CMW的拟合差，这意味着它们的准确性低于CMW。5成本转换AJITPar项目中成本模型的主要目的是选择和参数化适当的动态转换。本节将识别转换，并探索成本模型如何准确地预测转换前后程序的执行时间5.1骨架变形在AJITPar中，并行程序通过从自适应子程序（AS）库[27]中组合算法框架[17自适应骨架基于一组标准的算法骨架，用于规范Racket内基于任务的并行性。AS框架将骨架扩展为任务图，并将任务调度给工作者;扩展和调度在运行时发生AS框架依赖于Python来分析任务执行时的成本。 成本信息 用于指导动态任务调度器以及骨架转换引擎。后者通过根据一组标准方程重写骨架来调整运行程序的任务粒度以适应当前架构[27]。AJITPar中使用了许多不同的骨架类型。 基本类型的骨架是平行地图，平行减少和分而治之。AJITPar中骨架的实际版本是可调的，因为它们是用一个数字参数化的，该数字以某种方式指定了并行度的粒度。这些可调骨架中的一些，parMapChunk，parMapStride和J.M. Morton等人/理论计算机科学电子笔记330（2016）517→ →→−−→ → →→→ → →→→ → → → → →→−−→ → →→地图骷髅parMap：：（a）[b]parMapf []= [客户端]parMapf （x：xs）= spawnFX： parMapf xsparMapChunk* Int（a b）[a][b]parMapChunkkFxs =concat$parMap（mapf）$chunkk xsparMapStride：：In t（ab）[a][b]parMapStrideKFXS = concat$ 转置$ parMap（地图f）的$转置$块 k xsD i vide和征服某人帕尔迪夫孔：： （a [a]）（[b] b）（a b）a bparDivconqdiv comb conq x = casediv x o f[]→产卵conq xYS →产卵梳 （地图（parDivconqdiv梳 conq）ys）parDivconqThresh：：（a）→布尔）→（a）→[a ]）→（[ b ]→b）parDivconqThresh=I f打谷机（a b）ab thresh divcomb conq x然后 产卵（divconqdiv梳 conq）x e l se case div x o f[]→产卵conq xYS→梳子（map（parDivconqThreshpdiv梳conq）ys）−−锡格纳图水库的辅助功能chunk：：I n t→〔一〕→[[ a]]地图：：（a）→b）、→〔一〕→[b]concat：：[[ a ]]→[a]迪夫孔：：（a） →[a ]）→（[ b ]→b）、 →（a） →b）、 →一 →b转置：：[[ a ]]→[ a ]图五、AJITPar基本骨架和可调骨架。parDivconqThresh，如图5所示，在Haskell风格的伪代码5中指定。使用这些骨架的代码可以通过修改作为调优参数的第一个参数来转换;我们将使用τ来表示这个调优参数。AJITPar系统的目标是转换骨架，使生成的任务具有最佳粒度，即平均执行约10到100毫秒。为此，系统监视任务的运行时间并计算其成本当它们完成时，遵循等式（4）。如果系统发现太多的任务超出了最佳粒度范围，它将尝试转换生成任务的骨架。在最简单的情况下，这是通过改变调谐参数τ如下。设t0和γ0为观测到的由骨架的当前调优参数τ 0生成的任务的平均运行时间和成本。系统计算k=t0/γ0，并选取目标粒度t1（在10到100毫秒的范围内）和相应的目标成本γ1=t1/k。然后，系统选取新的调谐参数τ1，使得成本比γ1/γ0和调谐比τ1/τ0与骨架的成本导数相关。成本导数是表示成本γ的响应变化的函数5 扩展了一个基本的spawn，其中spawn f x形式的表达式创建了一个新的任务计算 函数应用f x.18J.M. Morton等人/理论计算机科学电子笔记330（2016）5基准输入骨架矩阵乘法1000x1000矩阵parMapChunkSumEuler[1] 4000]parMapChunk; parMapStride斐波那契42parDivconqThreshk-means样本数据parMapChunkMandelbrot6000x6000parMapChunk表4基准及其输入和应用的框架调谐参数τ的变化。例如，parMapChunk骨架的成本导数是常数函数1，因为块大小τ加倍会使任务成本加倍。相比之下，parMapStride的导数是函数1/x，因为步幅宽度τ加倍会使单个任务的成本减半。请注意，一般来说，成本衍生物是特定于骨架的，但与基准应用程序和架构无关。这种调整τ的方法的基础是时间/成本比k与τ无关的假设。在本节的其余部分，我们将通过经验证明，只要任务粒度不是太小，情况确实如此5.2实验成本模型的适用性进行评估，用于预测应用转换对执行时间的影响如果执行时间与预测成本的比率k在每个程序的不同τ5.2.1基准测试和转换这些实验中使用的基准如表4所示，基准的来源可在[30]中获得。对于大多数基准测试，任务计算的内容是显而易见的，例如。在矩阵乘法的情况下，结果矩阵的一组行k-means是一种特殊情况，它的任务不是计算聚类，而是根据当前质心对输入数据的一个块进行分类;这是标准聚类细化算法每次迭代的并行部分。k-means的输入数据由1024000个维度为1024的数据点组成，分为5个聚类。实验在与第4.3.1节相同的硬件和软件平台上进行。5.2.2实验设计基准测试表示在执行单个任务期间由工作者执行的顺序代码。每个基准测试都是以各种不同的调谐参数τ值运行的。例如，Fibonacci的阈值为15、16、17、18、21、24、27、30等。由于Pyrocode还不支持对跟踪计数器文件进行快照，因此每次运行都要执行两次;一次只使用预热代码，然后再次使用预热代码和要测量的任务的J.M. Morton等人/理论计算机科学电子笔记330（2016）519两次运行之间的跟踪计数器的差异准确地反映了任务6的跟踪计数器。Mandelbrot和SumEuler是不规则的基准，也就是说，工作是不均匀分布的，使得一些任务比其他任务更难。为了研究存在不规则并行性的成本模型的准确性，我们用不同的块重复了Mandelbrot和分块SumEuler实验5.2.3结果每个基准和成本模型的时间/成本比k与可调参数τ的关系图可以在图6至图11中找到。每个图上最右边的点代表相当于一个工人的τ，因此是该代码的未转换版本;沿着x轴向右移动对应于越来越粗粒度的任务。图12显示了Mandelbrot的三个不同块的k（对于成本模型CMW）与τ的关系图，显示了不规则性如何影响预测。表5显示了基准测试收敛到的时间/成本比k的稳定值;该表还显示了k可以取值的范围和见图6。 矩阵乘法基准的k与τ5.3讨论图6到图11中的图形的整体形状对于所有基准和成本模型都是相同的：时间/成本比k开始很高（在左边），然后在第一个下降随着任务粒度的增加，然后趋于稳定。图稳定的k值取决于基准和成本模型;对于CMW，稳定的k值列于表5中。通过CMW的设计，这些值聚集在1周围，尽管它们中没有一个特别接近1，这表明CMW对于任何基准都不是特别准确，通过6除非JIT没有充分预热。20J.M. Morton等人/理论计算机科学电子笔记330（2016）5图第七章 不规则分块SumEuler基准的kvsτ图八、kvsτ，适用于跨步SumEuler基准见图9。 斐波那契基准的kvsτ2到7倍。考虑到上一节中所示的CMW拟合的粗糙度，这是预期的（图4）。图之间的一个区别是k随任务时间变化的范围J.M. Morton等人/理论计算机科学电子笔记330（2016）521见图10。 k均值基准的k与τ见图11。 Mandelbrot基准的k与τ见图12。 Mandelbrot基准（CMW）的k与τ，比较3个块粘度 增加 ;该范 围列于 表5中。 对于 SumEuler 基准 ，以及 在较 小程度 上对于Fibonacci，这个范围很大。这与最小任务的非常低的粒度（大约几十微秒）一旦22J.M. Morton等人/理论计算机科学电子笔记330（2016）5基准稳定k系列k稳定k的最小任务粒度矩阵乘法0.5790.201<11400μs跨SumEuler6.871450306μs分块求和Euler4.311460129μs斐波那契0.5421.55294μsk-means0.5350.847<12100μsMandelbrot0.2510.0187<117000μs表5每个基准的稳定k值（成本模型CMW）粒度超过表5中列出的100至300μs的特定阈值时，k值稳定。这表明，成本模型对于小任务尤其不准确，这可能是由于较小的任务通过较少的迹线运行的事实，但是随着任务大小的增加确实变得更准确。特别是，成本模型对于10到100毫秒的目标粒度范围内的任务是相当准确的对于矩阵乘法和Mandelbrot，表5中列出的k的范围很小。 对于k均值，范围也很小（约为0。3）如果最小任务粒度的异常高的k7这与相当高的最小任务粒度（10到120毫秒）相关;事实上因此，对于这些基准，成本模型在整定参数τ的整个范围内是相当准确的。除了超低任务粒度之外，成本预测的另一个不准确性来源分块的SumEuler和Mandelbrot基准测试确实表现出不规则的并行性。在SumEuler的情况下，区间下端的块产生的任务比上端的块小，在Mandelbrot的情况下，图像顶部和底部的块产生的任务比中间的块小。图7和图11中的曲线图示出了间隔或图像的中间的块的k的曲线图，而不是所有块的平均值，以试图解释不规则性的影响。图12对比了图像顶部的块（块0）与中间的两个块的时间/成本比k块0的k与其他两个明显不同，并且不稳定，尽管图形确实随着粒度的增加而收敛，这与不规则性随着块大小的增加而减少的事实相关。我们注意到，虽然Mandelbrot的适度不规则性会导致一些准确性损失，但这并不太糟糕：块0的最极端k与Mandelbrot的稳定k值之间的比率小于3倍相比之下，Chunk 0的任务运行时间与Mandelbrot的平均任务运行时间之间的比率因此，成本模型在某种程度上能够平滑由不规则任务大小引起的预测不准确性。最后，根据这里提供的证据，看起来所有三种成本模型都是7实验数据表明，这个异常值是由不充分的JIT预热引起的，尽管我们还不知道为什么。J.M. Morton等人/理论计算机科学电子笔记330（2016）523同样适用于预测转型的成本。虽然这是仅改变单个调谐参数τ的值的简单变换的情况，但是当尝试花费两个变换的链时，不再需要这种情况在未来的工作中，我们的目标是系统地预测由多个骨架组成的骨架表达式的变换链的成本我们预计，在这些情况下，转换前后的轨迹集之间的差异将比我们目前看到的更大。因此，我们希望跟踪的实际内容更重要，并且成本模型CMW在预测准确性上击败其他两个6讨论和正在进行的工作我们已经设计并实现了一个从Python JIT编译器中提取JIT跟踪信息的系统（第3节）。 我们已经为JIT跟踪定义了三个轻量级成本模型，从非常简单的循环计数模型CM0到相对简单的指令计数模型CMC，再到特定于架构的加权模型CMW。为了自动确定CMW的适当权重，我们在Pyrocket基准套件上运行了一个线性回归（第4节）。我们使用了所有三个成本模型来比较转换前后六个基于框架的基准测试生成的任务的相对成本，其中框架转换是通过改变特定于框架的调优参数来诱导的。我们已经发现，一旦任务粒度上升到阈值以上，这些转换对任务运行时间的影响可以使用我们的成本模型准确预测（第5节）。我们已经证明，即使是本文中描述的最简单的、与架构无关的成本模型，也允许我们准确地预测简单转换对任务运行时的影响。我们期望特定于架构的模型CMW在预测更复杂的转换的任务运行时间时会更准确，例如转换链（当通过重写转换复杂的骨架表达式时自然出现）。我们进一步推测，类似的技术可以用于识别轻量级成本模型的基础上产生的跟踪JIT编译器为其他语言，例如。Python、JavaScript等在未来的工作中，AJITPar项目计划在其电子竞技中使用成本模型CMW更准确地说，CMW将用于调整骨架参数（如第5节所述），并选择最有希望的候选表达式进行骨架重写。AJITPar项目计划通过对多个架构（从多核桌面到数百个核心的服务器集群）的案例研究进行基准
我的内容管理
展开
