自动备忘录框架：C/C 应用程序的源到源优化和记忆技术的影响

软件X 10（2019）100322原始软件出版物一个自动和参数化的备忘录框架Loic Besnarda，Pedro Pintob，Pennsylvania，Imane Lasria，João Bispob，Erven Rohoua，João M.P. CardosobaUniv Rennes，Inria，CNRS，IRISA Campus de Beaulieu，35042 Rennes，Franceb葡萄牙波尔图大学工程学院和INESC TECar t i cl e i nf o文章历史记录：收到2018年8月2日收到修订版，2019年6月14日接受，2019年保留字：Memoization源到源优化a b st ra ct许多应用程序都需要提高执行时间和能效，并且通常需要复杂的代码转换和编译器优化。优化技术之一是memoization，它保存计算结果，以避免将来使用相同的输入进行计算。在本文中，我们提出了一个框架，自动应用memoization技术的C/C++应用程序。该框架基于自动代码转换，一个源到源编译器和一个记忆库。有了这个框架，用户可以选择要记忆的函数，只要它们遵守我们当前的记忆库所施加的某些限制。我们使用的框架和相关的memoization技术和减少执行时间和能源消耗的四个代表性的基准的影响。©2019作者由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本Clava：v3.0.13备忘录：v1.0用于此代码版本的代码/存储库的永久链接Clava：https://github.com/ElsevierSoftwareX/SOFTX_2018_129备忘录：https：//github.com/ElsevierSoftwareX/ElsevierX_2018_129Clava：Apache许可证，2.0备忘录：LGPL V3使用的代码版本控制系统Clava：git备忘录：svn使用的软件代码语言、工具和服务Clava：C++，Java，LARA Memoi：C，sed编译要求，操作环境依赖性Linux，Windows，macOS如果可用链接到开发人员文档/手册Clava：jbispo@fe.up.pt电邮：loic. irisa.fr1. 动机和意义提高执行时间和能源效率在许多应用中至关重要。可用于这种改进的可能优化是记忆[1]，其是保存计算结果的技术，使得可以跳过未来的计算性能*通讯作者。电子邮件地址：loic. irisa.fr（L. 贝纳德），p.平托@ fe.up.pt（P.平托），imane. inria.fr（I.Lasri），jbispo@fe.up.pt（J. Bispo），erven.inria.fr（E.Rohou），jmpc@fe.up.pt（J.M.P. 卡多佐）。https://doi.org/10.1016/j.softx.2019.100322可以通过缓存可记忆函数的执行结果，并在使用重复输入执行新调用时检索它们而不是重新计算结果来改进。在这项工作中，我们引入了一个记忆化框架，集成在ANTAREX工具流[2]中，可以自动将此技术应用于可记忆的函数。我们定义可记忆函数[3，4]为纯函数，即，确定性和没有副作用，具有我们当前的记忆化实现所强加的三个附加约束首先，函数必须有1到3个相同类型T的参数。这个限制来自于我们当前对哈希函数的选择，它结合了所有的参数，因此需要2352-7110/©2019作者。 由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx2L. Besnard，P.平托岛Lasri等人粤公网安备44010802000110号它们具有相同的位长度。在用XOR运算组合所有参数之后，我们取结果的高阶和低阶位，并使用XOR再次组合它们，留下一半的原始位。我们重复这个过程，直到我们达到索引哈希表所需的位数，如果需要，屏蔽任何位第二个约束是函数必须返回相同类型T的数据。最后，第三个约束是T是int、float或double中的一个。在关键代码段中具有可记忆功能的应用中，记忆化可以提供重要的执行时间减少和能耗节省。我们的memoization框架依赖于内部表，这些表存储先前计算的结果，并通过表查找替换未来的调用内部表的元素用一个从memoized函数的调用参数计算的散列进行索引记忆化方法可以从分析应用程序和识别可记忆函数对应用程序整体执行的贡献开始分析步骤还可以记忆化技术。我们的框架允许在应用程序运行之前加载内部表（例如，具有简档数据）和/或在运行时更新它们（允许适应在简档阶段期间未考虑的执行上下文）。该解决方案可以实现多种应用的节省，并且允许用户编写运行时自适应策略以使应用对上下文变化更具弹性并且能够实现预定的执行阈值。记忆化技术可以集成到任何具有可记忆函数或方法的C或C++应用程序基于选定的memoizable函数，我们的框架生成一个新版本的应用程序增强memoization支持依赖于Clava1源到源编译器。该框架还负责生成包含memoization实现核心的C库，该库与新生成的应用程序相链接。Clava的编译过程由LARA [5]领域特定语言（DSL）控制。通过这种设置，还可以使用LARA对代码执行分析和转换，例如，在这种特定情况下，在何处以及如何应用记忆化技术LARA代码中的主要模块化单元是方面，它可以被认为是一个函数，具有输入和输出，但具有与应用程序源代码的内部表示进行交互的能力。当开发几个方面来实现一个特定的目标时，我们有一个LARA计划，我们经常称之为战略。我们的记忆化框架基于[4]中提出的记忆化方法，该方法使用动态库并在二进制级别应用记忆化我们的框架已经推广到C++，增加了扩展，允许应用程序的灵活性，增加了有关表加载和表运行时更新的选项，并适用于在应用程序源代码的水平2. 软件描述本文中提出的软件解决方案依赖于两个不同的组件，这两个组件相结合，可以轻松地增强应用程序的记忆支持。第一个组件是Clava，一个源到源编译器，能够自动生成新版本的应用程序代码，并进行必要的更改以支持memoization。这是通过用户可以调用和参数化的一系列LARA方面来执行的，所有这些方面都作为Clava存储库的一部分分发。第二个组件是memoization C库本身，它是从标识1 https://github.com/specs-feup/clava网站。要应用memoization的函数该库针对Clava修改过的输入应用程序版本进行 如图 1、使用该方法包括三个步骤：（1）源到源编译;（2）存储库的生成和编译;（3）与库链接的应用程序的编译。考虑图1所示的可记忆C函数foo。二、这是一个纯函数，它接受一个float参数并返回相同类型的数据。源到源步骤包括两个阶段，第一个阶段是添加另一个功能的程序。这个新函数包装了目标函数，并包含了与记忆库接口的记忆逻辑 这种包装也说明了图。 二、第二个阶段将所有对原始函数foo的调用（可以指定一个LARA方面，只对某些调用位置应用memoization）替换为对其相应的包装器foo_wrapper的调用。这种技术适用于C和C++函数以及C++方法，并考虑到名称修改、函数重载和对对象的引用。用户可以通过LARA方面或手动地进一步改变应用以与备忘库交互例如，memoization库公开了一组变量来控制其内部行为。要动态停止和重新启动特定函数的记忆，可以更改变量_Memoize，其中对应于目标函数的变形名称类似地，为了控制表更新策略，用户可以更改变量_al-waysReplace和_FullyOffLine。这可以用于控制记忆库关于内部表的更新的运行时行为记忆库的生成和编译从函数标识文件（funs-static.def）开始。用于记忆的LARA库除了更改应用程序的源代码外，还生成 此 文 件 。在 本 文 中 ， 我 们 建 议 通 过 Clava 使 用memoization，依靠LARA DSL编程的方面。然而，也可以使用独立库2，而不依赖LARA和Clava编译器。 为此，用户必须手动编写函数标识文件（funs-static.def），更改源代码以包含包装器，并将原始调用替换为包装器。流程的其余部分保持不变：生成库并在编译应用程序时链接它。使用LARA策略的优点是，存储库集成到应用程序中，而无需手动修改源代码。Clava生成的代码然后被编译并与相关的生成的记忆库链接。为了增强具有LARA策略的备忘录化的应用程序，用户可以调用库方面并定义许多参数。首先，可以定义存储计算数据的内部表的大小。这个决定变成了一种折衷，可以根据当前应用程序或场景的需要进行微调。较大的表可以容纳更多的数据，但需要更多的内存。最重要的是，根据底层架构，表的大小可能会影响缓存性能。第二，可以指定一个文件，从该文件加载先前初始化的记忆表。如果未指定，则程序将以空表开始。这允许从一个执行到下一个执行构建记忆表，并保持最频繁请求的输出。对于此功能，我们还可以指定一个文件，在其中保存执行结果最后，如果打算使用近似能力，也可以在此步骤配置库以忽略来自参数的输入表示的多个位到记忆化函数。2 https://gforge.inria.fr/projects/memoization网站。L. Besnard，P.平托岛Lasri等人粤公网安备44010802000110号3图1.一、 建议备忘录框架的工具流程。2.1. 技术细节图二、可记忆的 C函数及其包装器。执行组，由扩充的应用程序代码和记忆库组成。虚线箭头表示，包装器的第一个操作是执行查找，以检查所提供的输入的输出是否已经存储。查找操作将对输入进行散列，以获得内部表中的正确插槽。如果该位置为空，则查找失败并返回false，表示未命中。如果发生这种情况，则调用原始目标函数并返回正确的值。另一方面，如果表槽不为空，我们将存储的输入与当前调用的输入进行比较。如果这些值相同，我们认为这是命中，则查找函数设置输出值并成功返回包装器将返回该值。如果输入不相等，则会发生冲突，这意味着两个不同的输入被散列到同一个插槽中。在这种情况下，lookup函数返回false。同样，返回值是通过调用原始函数来计算的，最终返回。无论是命中、未命中还是碰撞，都将始终返回正确的值表更新逻辑发生在计算出正确的输出值（或从表中获取正确的输出值）之后，因此它与技术的安全性无关图图3示出了描述总体记忆化技术（在顶部）和查找过程（在底部）的两个流程图。2.2. 软件构架图4显示了架构的概述我们的memoization- tion框架。这四个主要组成部分可以分为一个组件生成另一个组件，并且实线箭头指示组件之间的运行时交互。Clava是一个用Java编写的源到源编译器，它使用Clang3作为前端来解析C和C++源代码。编译器维护应用程序的内部表示，该表示根据策略进行分析和转换在输入LARA代码中定义。Clava包含多个LARA库，可以用于不同的目的，包括本文中介绍的memoization框架。LibraryGenerator是一个sed脚本，它使用函数定义文件（*.def）和几个代码模板来生成memoization库的最终定制代码这些代码可以被编译成一个库。库本身为每个memoized函数以及用于运行时控制和接口函数的关联变量维护一个表。这些是从插入Clava存储策略的每个包装器调用的函数最终的应用程序保留了原始功能。在源代码中，不同之处在于它为每个目标函数提供了一个包装器。这个包装器被调用，而不是原来的包装器，并执行对生成的记忆库的调用。2.3. 软件功能本文提出的备忘录框架允许用户半自动地增强应用程序的备忘录支持。典型的用户干预与两组，生成和执行。世代集团，与Clava和Library Generator，负责生成3个https://clang.llvm.org/。4L. Besnard，P.平托岛Lasri等人粤公网安备44010802000110号图三. 描述整个记忆技术和查找过程的流程图。配置选项和选择要记忆的函数。然而，函数选择也可以在没有用户干预的情况下执行，因为LARA库还提供了自动检测可记忆函数和方法的代码。此选项返回检测到的可记忆化函数的列表，用户可以决定是否对这些返回的函数应用记忆化。集 成 到 Clava 编 译 器 中 的 LARA 库 有 几 个 方 面 用 于 将memoization 应 用 于 不 同 类 型函 数 ： 数 学 函 数 （ 来 自math.h），C函数和C++函数。对于每一个，都有LARA方面，允许用户使用默认参数或定义所有需要的参数来记忆函数。此外，该 库 还 包 括 一 个 方 面 ， 可 以 自 动 对 所 有 math.h 函 数 执 行memoization，以及将memoization应用于C++函数和方法的方面，同时考虑函数重载。由于我们的框架包括源到源编译，因此可以使用LARA方面编写复杂的分析和转换策略。例如，这可以用来选择哪些函数要memoize，使用任何用户在库返回的可能memoizable函数列表之上设计的语法。我们的memoization库的另一个功能是在处理浮点数时可以这实质上是从函数的输入中删除了一些（用户指定的）位，将接近的数字分组在一起，并为这些数字返回相同的输出。更准确地说，我们删除了尾数的一些最低有效位在某些精度损失是可容忍的情况下（例如，在图像处理的某些情况下），这可以进一步减少执行时间和能耗。所有这些功能都增强了应用程序在某些特定和关键功能上利用重复输入的能力，同时仍然能够适应变化，因为表可以动态更新。此外，用户可以探索运行时策略，以决定何时更改表的更新策略或完全关闭记忆化，这要归功于为每个目标函数公开这种类型的控制的变量。3. 说明性实例本节介绍LARA方面的一个示例，该示例说明了用户与前一节中描述的备忘库之间的接口考虑一个使用数学函数cos、acos和sqrt的C应用程序示例。此外，见图4。拟议备忘录化解决方案的主要组成部分。该应用程序显示存在对称为myfunc的用户函数的大量调用。 图图5示出了名为Launcher的LARA方面，其可用于应用备忘录化。首先，我们导入包含memoization方面的类（第1行）。然后，识别要记忆的函数（第5-6行这是所有LARA代码用户需要编写的增强C/C++应用程序与memoization。方面的执行将产生（1）应用程序的新版本，其中所有对FOO（FOO是cos、acos、sqrt、myFunc之一）的引用都被FOO_wrapper替换，(2)funs-static.def文件，其中包含一行每个memoized函数，如图所示。六、每一行都编码了生成memoization C库所需的所有参数。Memoize_Function方面是一个帮助方面，它在调用其他更通用的方面时自动设置一些默认参数。例如，图6的第4行展示了可以在那些更一般的方面上指定的一些参数。它指定它是一个C用户函数（值2），后跟函数的名称（myfunc）及其相关的包装器（myfunc_wrapper），以及该函数具有3个double类型的输入参数的标识。提供了其他参数来控制memoization框架：特别是最后两个参数（编号65536）用于指定更新表（替换或不替换）时管理可能冲突的策略，并定义内部表的大小LARA方面提供给用户来设置这些参数，但在所呈现的示例中，我们调用使用默认值的更简单版本。L. Besnard，P.平托岛Lasri等人粤公网安备44010802000110号5图五、LARA Launcher方面的一个例子，定义为memoization。见图6。一个funs-static.def文件的例子。图7.第一次会议。 一个 为C++记忆化定义的LARA方面的例子。例如，图7示出了作为记忆库的一部分的LARA方面之一的实现的示例。这是库代码，而不是用户需要编写的代码这是用于目标C++方法，并允许用户指定所有memoization参数。这个例子定义了一个类（aClass）的C++方法（aMethod）的memoization（第1-13行经过一些验证（本例中未提供）后，在第17-24行中搜索目标方法。在成功的情况下，添加包装器的代码（第28行）以产生记忆库，并且修改应用程序的代码以调用生成的包装器（第30行），其也被声明为类的新方法。4. 影响为了显示我们的memoization框架的影响，我们已经将其应用到四个C/C++程序。对于每一个程序，我们已经测试了原始版本以及代表两个参数的组合的四个不同的非线性化版本。第一个参数是内部表的大小，我们测试了包含256和65，536个元素的表。第二个参数是在哈希冲突的情况下是否执行表更新。对于这些实验，我们不考虑在执行应用程序之前设置表。因此，当记忆增强程序开始执行时，其表为空，并且随着请求的执行而开始被填充。同一函数的两个不同输入可能会产生相同的哈希值，这会导致冲突。在这个例子中，我们的策略是要么忽略冲突，不改变表，要么用最新的条目替换以前的条目。我们的基准应用程序包括：ATMI[6]是一个用于模拟微处理器中的稳态和时变温度的库，例如使用J0、J1、exp和sqrt。·6L. Besnard，P.平托岛Lasri等人粤公网安备44010802000110号×××=equake是从SPEC OMP中提取的应用程序。它在其临界区域调用数学函数sin、cos和sqrt。FFT是一个快速傅立叶变换的实现，从BenchFFT 4基准套件中提取。它调用函数sin和cos。rgb2hsi是一个将图像从RGB模型转换为HSI模型的基准测试内核它调用cos、acos、sqrt和一个纯用户函数。测试是在2.60 GHz的Intel（R）Core（TM）i7- 5600 U CPU上进行的，C/C++代码是使用GCC和-O3编译的。为了解决这种技术可能过于依赖于测试输入的问题，我们在fft和rgb2hsi基准测试中使用了几种不同的输入。 对于fft，我们尝试了三个样本数（10000000，20000000，30000000）和三个频率（123.6，256.89，88.7）。对于rgb2hsi，我们使用了八个不同的图像。由于缺乏可用的工作负载，其他基准测试使用单一输入进行测试。表1给出了使用四种测试的记忆化配置获得的加速比，超过了原始版本（即，没有记忆化）。表2显示了相同配置下与原始配置相比的能耗改进。 这是使用依赖于英特尔RAPL计算器的实用工具测量的。低于1的值表示能耗降低。例如，对于配置为65536-nu的atmi基准测试，我们只消耗了原始配置的71%（表中的0.71）。总的来说，使用我们的备忘录框架，使我们能够实现在执行时间和能源消耗的显着减少。这一点通过平均线得到了证实，平均线表示每个测试配置获得的结果的基准几何平均值。考虑到执行时间，最差的平均结果是0。97当使用小表且没有更新时会减速（在冲突的情况下）。另一方面，启用更新的较大表实现了1. 十六岁对于atmi和rgb2hsi基准测试，更大的表有积极的影响，而这在其他两个基准测试中没有发生。ATMI和RGB2HSI仅示出少量命中（即，在表上找到的结果），当表大小增加时，256表的增长相当大，而在EQUAKE和FFT基准上，这种增长没有那么大。这可能是因为记忆化函数的输入随时间变化的方式以及这些输入采用多少不同的值我们注意到，在哈希冲突的情况下启用更新可以改善所获得的结果。这是每个基准测试的情况，除了ATMI在使用大表的情况下。当更新被禁用时，可以在执行的其余部分中使用最不频繁请求的输入来这在某种程度上是通过打开冲突情况下的更新功能来纠正的，因为最频繁的输入应该能够推出其他不太频繁的输入，并在大多数执行中保留在表中。然而，在atmi的特定情况下，当启用更新时，贝塞尔函数显示出越来越多的冲突，这似乎表明两个频繁的输入正在冲突并不断将彼此推离表，导致未命中并迫使重新计算其相应的输出。fft基准测试表明，无论表大小如何，使用memoization而不更新时，性能都会下降。4http://www.fftw.org/benchfft。表1比原始版本更快的记忆版本。四列中的每一列对应于具有两个不同参数的备忘录化基准，表大小和冲突更新策略（nu表示无更新，u表示更新）。 表格的最后一行显示了每个配置的加速比的几何平均值。0的情况。89± 0。021. 13± 0。101. 18 ± 0。06平均值为0。97± 0。061. 08± 0. 051. 14± 0。221. 16 ± 0。10表2与原始版本相比，备忘录版本的能耗有所改善。四列中的每一列对应于具有两个不同参数的备忘录化基准，表大小和冲突更新策略（nu表示无更新，u表示更新）。低于1的值表示能耗降低。表格的最后一行显示了每种配置改善的几何平均值。基准256-nu 256-u 65536-nu 65536-u1 .一、20± 0。030. 95± 0。080. 88 ± 0。04平均1. 05± 0.110. 94± 0。05 0. 89± 0。140. 88 ± 0。04当查看更详细的执行数据（此处未提供）时，可以看到cos有一个命中（在200，000，000个调用中），sin有0个命中（在100，000，000个调用中）。这意味着这些表最初填充的是以后不会再次请求的输入，这会导致开销，从而略微降低原始性能。 另一方面，当更新被启用时，这些初始值最终会被更频繁的输入覆盖。对于cos和sin，点击次数分别增加到137，227，265和74，893，090rgb2hsi基准测试表明，当使用一个小表而不更新冲突时，性能会严重下降。这个基准测试极大地受益于更大的表和从表中删除不太频繁的值在没有更新的情况下，通过简单地使用更大的表，命中数当输入以这样的方式分布时，可能会发生这种情况，即大多数调用使用相同的输入集，但这个集合足够大，以至于它无法放入一个小表中实际上，我们不经常使用256个元素的小表格。然而，这说明了用户可以执行的权衡，以根据当前需要微调该框架。在某些情况下，例如当目标是资源有限的嵌入式系统时，由于内存限制，可能需要较小的表。表3给出了对fft和rgb2hsi基准测试（这两个基准测试使用多个输入进行测试）的执行时间测量进行双尾配对样本t检验的结果。对能量结果的测试遵循相同的模式。应用该统计检验以将每个记忆化配置的结果与原始版本的结果（即，没有记忆），当以不同的输入（9个FFT配置和8个RGB2HSI图像）运行时。有一个单一的配置（在表中突出显示），我们不能声称α 0具有统计学显著性。05，rgb2hsi基准测试，表中有256个元素，在发生冲突时没有更新对于8种配置中的其他7种，t检验认为数据具有统计学差异。考虑到除了如何应用记忆化之外，实验中没有其他变量，我们可以自信地说，所显示的差异是由该技术引起的。···基准256-nu256-u小行星6553665536-uatmi1.011.021.461.26地震1.021.061.011.04FFTRGB2HSI0的情况。98± 0。011 .一、13 ±0。020的情况。98± 0。021 .一、12 ±0。021 .一、22 ±0。08atmi1.021.010.710.83地震0.960.930.950.94FFTRGB2HSI1 .一、03 ±0. 030的情况。89± 0。031 .一、04 ±0. 030的情况。90± 0。030的情况。86± 0。05L. Besnard，P.平托岛Lasri等人粤公网安备44010802000110号7表3双尾配对样本t检验的结果。基准2 5 6 -nu256-u65536-nu65536-u致谢这项工作得到ANTAREX项目的部分资助FFT（df=8）rgb2hsit= 3. 50p= 0。008t= 3. 63t= 6. 45p= 0。000t= 2. 02t= 2. 91p= 0。020t= 2. 50t= 6. 01p= 0。000t= 2. 53通过欧盟H2020 FET-HPC计划，批准号为671623。Bispo感谢葡萄牙科学和技术基金会（FCT）通过博士后项目（df = 7）p = 0。008p = 0。083p = 0。041p= 0。0395. 结论本文提出了一个自动将memoization应用于C/C++应用程序的框架。生成的应用程序存储由其输入映射的纯函数的输出。如果使用相同的输入调用这些纯函数，则框架返回存储的值，而不是重新计算它。因此，这种技术可以通过简单地避免在使用重复输入调用关键函数的情况下不必要的计算来改善执行时间和能耗。我们的框架包括两个主要组成部分。首先，一个源到源编译器，它修改输入C/C++应用程序，方法是针对可记忆的函数，并将它们的调用替换为对与C记忆库接口的包装器的调用。这个库是我们框架的第二个组件，它维护所有的数据结构，并包含通过这种优化来增强应用程序所需的记忆逻辑。源到源编译器可以由用户控制，以执行分析并决定目标函数。我们在四个有代表性的基准测试中展示了记忆技术的影响，并通过测量执行时间和能耗的减少来展示我们软件的实用性。奖学金SFRH/BPD/118211/2016。竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作引用[1]米奇·D“备忘录”功能和机器学习。Nature1968;218（5136）：19.[2]Silvano C，Agosta G，Barbosa J，Bartolini A，Beccari AR，Benini L，Bispo J，Cardoso JMP，Cavazzoni C，Cherubin S，Cmar R，Gadioli D，Manelfi C，MartinovicJ，NobreR，PalermoG ，PalkovicM ，PintoP，RohouE，SannaN，Slaninová K. 用于监控和自动调整高能效HPC系统的ANTAREX工具流程。 2017年嵌入式计算机系统国际会议：架构，建模和仿真; 2017年。 第308- 316页。[3]Suresh A，Narasimha Swamy B，Rohou E，Seznec A.用于记忆化的截取函数：使用超越函数的案例研究。ACM TransArchit Code Optim2015;12（2）.[4]Suresh A，Rohou E，Seznec A.时间函数记忆。在：2017年第26届编译器构造国际会议。p. 45比54[5]Cardoso JM ， Coutinho JG ， Carvalho T， Diniz PC， Petrov Z， Luk W ，Gonçalves F.使用lara面向方面编程方法的性能驱动插装和映射策略。Softw -PractExp2016;46（2）：251-87。[6]作者：Michael P. ATMI：微处理器温度的解析模型. 2007年：第三届建模、基准和模拟年度研讨会