轮廓引导的混合编译：迪奥戈·努内斯·桑帕约的博士论文审查报告

轮廓引导的混合编译迪奥戈·努内斯·桑帕约引用此版本：迪奥戈·努内斯·桑帕约。配置文件引导的混合编译。自动控制工程格勒诺布尔-阿尔卑斯大学，2016年。英语NNT：2016GREAM082。电话：01428425v2HAL Id：tel-01428425https://theses.hal.science/tel-01428425v22018年1月11日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaireTHAPOSE为了获得等级格勒诺布尔大学博士专业：信息Arrêté ministérial：25 mai 2016Présentée par迪奥戈·努内斯·桑帕约Fabrice Rastello说的准备在INRIA上信息科学与技术学院信息科学与技术学院轮廓引导的混合编译Thèse soutenue publiquement le14/12/2016，devant le jury composé de：史蒂文·德伦法国雷恩IRISA教授，特别报告员，主席阿亚尔·扎克斯软件工程师经理，英特尔，以色列海法，特别报告员Alexandra JIMBOREAN助理教授乌普萨拉大学，瑞典，考试Christophe GUILLON法国格勒诺布尔意法半导体公司高级架构师，审查员路易-诺埃尔·波歇助理教授科罗拉多州立大学，柯林斯堡，美国，考官Fabrice RASTELLOResearch Director，Inria，Directeur de thèse2内容章次1一.导言. 151.1免费午餐时代151.2动机161.3捐款. 182框架212.1理论基础222.2应用程序分析242.3动态依赖图（DDG）272.4检索有利可图的优化272.5获得优化312.6构建运行时测试322.6.1精确的依赖违反测试342.7简化生成的测试372.7.1精确度提高382.7.2变量消除432.7.3去除冗余472.8现状492.9摘要493相关工作513.1使用量化器消除的代码优化3.2扩展数据依赖分析513.3处理多项式523.4阵列去线性化523.5使用运行时保护的5334内容3.6混合、推测、多面体优化4实验结果554.1试验台554.2量词消除565关于量词消除635.1信号检测655.2错误检测655.3表达式分解665.4平等标准化675.5“A little randomness isalways good”6关于DDG71的细节6.1技术细节726.2跟踪事件736.2.1ddg_start_trace736.2.2ddg_alive_in746.2.3ddg_basic_block746.2.4ddg_load/ddg_store746.2.5ddg_loop_begin/ddg_loop_end756.2.6ddg_loop_iteration756.2.7stop_trace756.3模特807结论817.1今后的工作.827.2结束语85何塞·玛丽亚·摘要散热限制导致了芯片计算能力如何扩展的范式变化，从时钟频率增加到构建具有更多并行性的硬件。计算机应用程序必须适应探索这种并行性，这是留给软件开发人员的一项艰巨任务。为了帮助这个过程，许多优化编译器和框架已经开发出来。为了将变换应用这样做的一种可能的方式是通过确保在转换后的代码中保留相关指令之间的相对执行顺序。如果两个指令都访问同一个存储单元并且至少一个是写指令，则两个指令是相关的。然而，精确的依赖信息是很难检索。包含内存基址指针的代码引用可能重叠的区域，取决于输入值，或包含具有多项式内存访问表达式的语句，限制了静态分析的能力，以确定指令对之间是否存在依赖关系。在这种情况下，许多有效的转换无法被证明是正确的，从而使编译器无法执行良好的优化。动态编译器在程序执行过程中实现代码的分析和转换，可以获得更精确的依赖信息，但却受到内存和时间等资源的限制。混合编译器从程序的预先执行中检索运行时信息，并基于来自运行时和源代码的信息执行优化，但必须处理运行时行为依赖于输入的事实，并且所选择的转换可能对不同的程序输入无效。本文提出了一种新的优化循环嵌套区域的混合编译技术它静态地执行复杂的循环转换，由从源代码和运行时获得的指令依赖信息指导对于可能依赖的所有指令对，运行时测试验证是否实际存在依赖，以及所应用的转换是否改变原始程序的两个指令如果至少有一个依赖被违反，则必须执行循环的原始版本，否则使用优化代码是安全的，也就是说，它们表达了转换无效的必要和然而，这样的测试是非常昂贵的，如果循环执行O（n）迭代，测试必须执行O（n2）评估。这种复杂的测试被转换成更简单的测试，具有常数数量的表达式被评估，这些表达式表示转换无效的所需条件此简化过程使用基于傅立叶-莫茨金消除的量词消除发达国家的技术删除，尽可能多的，不精确，由于使用实数代数整数系统。建议的量词消除技术产生较少的不精确简化的整数系统，比其他现有的工具。该框架的合理性证明了26个内核使用循环与多项式内存访问表达式和指针在五月别名。执行复杂的循环转换，我们的框架生成的测试，正确地允许执行有效的transformation和块无效的，在所有执行的测试。7关键词代码优化，编译器，数据依赖，混合分析，May-alias，May-dependence，剖析，多面体编译，量词消除，符号计算9图目录2.1通过函数25执行时间采样2.2perf时间采样由源代码252.3叮当抽象树252.4动态依赖图（DDG）的部分视图262.5从DDG29生成的行为树（AST）2.6简化表示的图形视图...............................................................................................................302.7小行星指令31中描述的FW-tri程序转换2.8域空间图322.9附表空间2.10 图332.11 建议的量词消除图395.1对象投影图像635.2松散约束示例。.......................................................................................................................646.1用作性能调试工具776.2不使用夹紧786.3使用夹紧时的DDG示例796.4用于组合距离向量的807.1参数多面体831112图的列表表的列表2.1在参数表达式的规范化过程中添加的约束。. .424.1实施的FME和QEPCAD-B604.2表与应用的转换和加速611314表格清单第1介绍许多编译器工具已经被开发出来，允许并行性和局部性的展示，以便更好地利用现代计算机资源。然而，当试图在遗留代码中使用这些技术时面临许多困难，其中不可能静态地获得准确的指令依赖性信息。每当应用代码转换时，编译器必须证明原始程序语义被保留。为此，它依赖于指令之间依赖关系的准确信息，以证明改变其原始执行顺序（调度）不会违反依赖依赖性表示生产者消费者关系，其中两个指令之间的依赖性的存在意味着一个指令产生被另一个指令消费或覆盖的信息。在依赖关系中的两个指令之间的原始执行顺序不能为了保留语义而改变。当静态依赖分析不准确时，编译器大多采取保守的行为，并假设依赖关系的存在，而不存在依赖关系则无法证明，这极大地限制了可能的代码转换。这项工作依赖于运行时的信息，以克服这种限制时，优化循环。它提出了一个新的编译器工具包，静态应用复杂的循环转换使用依赖关系的信息从运行时。为了确保语义得到保留，轻量级运行时检查保护优化区域，验证所应用的转换是否不违反给定输入的任何依赖关系，相应地在代码的原始版本或优化版本之间进行选择。1.1免费午餐时代几十年来，CPU1的频率，因此处理能力，呈指数级增长。在开发良好的编程方法和编译器优化方面的投资主要局限于学术界研究人员和少数高性能处理中心。至于市场，获得更好的性能，只是等待下一代计算机的问题被称为“免费午餐时代”（Sutter，2005），这种增长在2005年左右停止，当时散热限制了进一步的频率扩展。由于晶体管的扩展并没有停止，为了继续计算能力的增长，芯片制造商并行，在单个芯片中嵌入多个独立的处理单元。这种新趋势的问题在于，它将提高性能的责任从芯片制造商转移到了软件开发商身上。在软件开发行业中，生产力是主要关注的问题，而新的现实要求生产高效和并行的代码。1个中央处理器1516第1章介绍软件开发人员面临着一个非常艰巨的挑战，例如将遗留的、未记录的或语法差的软件转换为高效的并行软件。更糟糕的是，当时现有的编译器几乎没有提供支持。检索好的代码转换对于编译器来说是一项非常艰巨的任务，就像对于开发人员一样。从编译器的角度来看，程序定义了一组由给定sched- ule执行的指令。除此之外，代码转换包括改变所有这些指令的执行调度，以更好地使用硬件并行性。验证转换的正确性需要精确的数据依赖分析，以确保新的调度不会实例化在数据实际可用之前消耗数据或在使用之前覆盖数据的指令。尽管已经被广泛研究，但这种分析远不精确（Hind，2001），也不“适用于现实语言的环境条件（Smaragdakis和Balatsouras，2015），将困难的任务留给了程序员。一旦克服了转换代码以利用并行性的困难，人们可能会发现性能可能会由于IO2带宽限制而受到限制。与CPU计算能力一样，主存带宽也经历了指数级增长，但增长的因素有很大不同如果这种差异占上风，最终所有使用主存的程序都将是内存受限的。也就是说，应用程序的执行时间将仅受进出主存的数据移动的约束。很明显，处理器频率缩放在达到这样的平台之前就停止了。但它是常见的检测内存密集型应用程序（即，许多数据从内存中检索执行几个计算），可以饱和的主内存的可用带宽，而不饱和的并行处理能力Pirk等人。（2014年）。Williams等人（2009）的进一步研究更深入地应用于单个系统，不同的IO带宽和处理限制。1.2动机已经开发了许多不同的方法来处理生成有效代码的困难任务，例如：分发域特定高性能库或域特定语言和专用编译器（例如SDSL（Henretty et al. ，2013年）），具有嵌入式并行结构和操作的新编程语言或扩展（例如X10（Vijay et al. ，2016; Charles等人，2005年）），• 对现有语言的硬件特定扩展（例如，CUDA-C（NVIDIA，2016））丰富当前语言的语法以帮助编译器分析（例如，restrict关键字（ISO，1999，6.7.3.1）），运行时检查和转换，能够使用仅在执行期间可用的信息来推测性地决定良好的转换（例如APOLLO（Sudaran-Rajam et al. ，2014; APOLLO，2016））。每种不同的方法都有其优点和缺点。例如，专注于特定领域或硬件的技术需要开发人员的专业化。丰富代码语法需要在处理遗留代码时进行人工干预。混合编译通常需要大量的时间进行分析，并需要一个迭代编译框架。毕竟，编译器现在不仅必须2个输入/输出····1.2. 动机17了解底层硬件。但是它也必须知道哪种技术更适合正在实现的问题，并且还必须对正在优化的代码有深刻的理解。Polytope模型（Feautrier，1992 a，b; Bondhugula，2008）的基础理论可以追溯到60年代末（Karp et al. ，1967 ）。它是在二十多年的时间里建立起来的（Lamport，1974;Cousot和Halbwachs，1978;Feautrier，1988 a，b;Irigoin和Triolet，1988;Pugh，1991;Feautrier，1992 b）。它包括一个健全的形式主义，允许抽象，在代数的方式，多维循环的迭代空间和时间表，其迭代和指令。在这个框架中，内存访问必须表现为仿射表达式的循环计数器，允许有效地检测它们之间的依赖关系。这些技术的概念证明最初应用于Fortran或受限C代码，在高性能计算的背景下。十多年来，相关的工具已经得到实施和成熟。一些例子是CLooG（Bastoul，2004），PluTo（Bondhugula，2008），ISL（Verdoolaege，2010）和PoCC（Pouchet，2010）。 使用自动化的源到源优化器实现有希望的性能结果，直到在主流编译器中嵌入开发的技术成为下一个自然的步骤：GCC Graphite（Pop et al. ，2006）和LLVM Polly（Grosser et al. ，2012年）率先努力将多面体优化使用扩展到小的科学内核和受控的源到源环境之外。然而，实现这一步骤已被证明是非常困难的。应用多面体模型的障碍来自于编译器中间表示（IR）降低的固有问题，例如数组线性化和类型擦除，来自于使用可能具有多个间接的指针，以及静态分析无法处理的动态部分的存在（Trifunovic et al. ，2010年）。事实上，代码表示越接近二进制，它所持有的语义就越少，因此静态分析的结果就越不精确。已经做了很多工作来克服这些问题，从高层次的语义重建IR（Grosser et al. ，2015 b），使用合适的代码近似（Benabderrahmane et al. ，2008），扩展多核模型（Grösülinger，2009; Venkat et al. ，2014 a）。推测性代码转换（Jimborean，2012; Sudaran-Rajam et al. ，2014）演示了运行时分析如何能够将多面体工具用于在执行期间呈现适合多面体模型而不是静态检索的行为的应用。但是，它使用过程来执行簿记和回滚，从而增加了在线验证开销这个项目的目标是允许优化的应用程序与不精确的数据依赖信息。从形式上讲，它允许使用多面体工具的代码以前认为不可能这样的框架：循环嵌套区域包含内存访问多项式表达式和可能别名的基础指针。它是通过使用混合分析（Rus et al. ，2002）技术，即静态和动态分析的组合。通过执行应用程序的插装版本来检索所观察到的运行时依赖关系，这些依赖关系当验证所应用的变换是否保留原始循环语义时，不能静态地解决的指令依赖性在运行时通过描述变换无效的充分和必需条件的测试来解决。这种测试依赖于循环计数器，其评估成本随着变换循环执行的迭代次数而增长使用基于Fourier-Motzkin消除的量词消除技术，将测试转换为循环不变测试，即具有独立于优化循环执行的迭代次数的这个测试保护转换后的循环区域，根据测试结果选择执行优化的循环或原始循环。18第1章介绍1.3贡献这项工作提出了一种新的方法，使用应用程序执行分析静态生成安全，但复杂的循环优化。其贡献可归纳为：轻量级依赖分析：我们的混合分析使用从运行时捕获的信息来帮助填补静态依赖分析无法解决的空白。它检索运行时的依赖性，通过检测内存访问指令，也就是说，插入到程序中的操作，以监视和转储到跟踪文件中，在执行过程中访问的内存位置。在拥有跟踪文件和源代码的情况下，我们的框架构建动态依赖图（DDG§2.3），在动态指令之间观察到依赖性。在使用DDG时会出现两个问题：首先，跟踪所有指令之间的依赖关系例如，跟踪循环行程计数器变量（也称为归纳变量）的依赖关系将告诉优化器，任何循环的两个连续迭代之间总是存在依赖关系。这些依赖关系将阻止在两个循环迭代之间改变执行顺序的转换。其次，图中节点的数量与分析的程序复杂度成正比，并且在它们上操作既消耗内存又耗时。我们的框架依赖于标量进化（Pop et al. ，2005）分析，以避免使用静态已知回归公式来跟踪变量，该回归公式扩展到归纳变量中的仿射表达式，忽略伪依赖性。为了减少生成的图形大小，我们的框架允许限制跟踪的循环迭代的数量。为了保持重要的依赖关系，本文提出了一种箝位技术，将非跟踪指令合并到一个图节点中.使用不准确的依赖信息优化循环：代码优化器需要精确的依赖信息来检索有益的转换，并验证给定的转换是否符合程序语义。然而，评估依赖关系的存在性可能只能在运行时解决。这样的代码的示例是使用可能别名的基指针3和具有多项式表达式的存储器访问，因为现有分析由于其复杂性而避免处理多项式。在这种情况下，静态依赖分析提供了不准确的信息，将许多语句对分类为可能依赖的，并阻止优化器执行复杂的转换。为了克服检索复杂的循环转换的问题，我们的框架使用观察到的运行时信息作为可能依赖的指令的绝对真理。它要求监控的执行描述应用程序的通常行为，并且在大多数情况下，对该执行的有益优化严格的运行时数据依赖性验证：为了验证转换的正确性，生成一个运行时测试，覆盖所有可能的数据依赖性中断。简单地说，测试的计算是优化循环的二次成本。也就是说，如果原始程序的复杂度为O（n），则生成的测试的复杂度为O（n2）。这种测试表示为量词上的不等式系统，与循环行程计数器（或循环归纳变量）有关。使用下面提到的量词，所有的量词都被删除了，导致一个具有恒定执行复杂度的整体测试，即O（1）。3May-alias指针：如果两个内存指针所引用的区域存在重叠，则它们处于May-alias中。1.3. 捐款.19简化器：允许生成轻量级和紧凑测试的核心元素。该方法基于Fourier-Motzkin消元法的扩展，将一个精确而昂贵的依赖违反检验投影为一个简单的依赖违反检验。实验结果表明，所提出的量词消除算法（QEA）构成了一个现实的和有竞争力的替代现有的最先进的计划的基础上圆柱代数分解（CAD）。这项工作成功地面对和处理了三个困难：1. 不等式的数量可以随着要消除的变量的数量呈指数级增长2. 在处理多元多项式时，变量3. 当处理整数值不等式时，在每个变量消除步骤上传播的累积舍入不精确性可以极大地增加最终投影空间，换句话说，不精确投影可能导致运行时测试保守地选择不分支到优化代码，而实际上这是可能的。为了解决这些问题，提出了Schweighthorn（Schweighthorn，2002）所描述的定理的实现。它包括一个方法，确定一个不等式是否隐含在一个不等式系统中。在所提出的方案中，该方法用于多个不同的目标，如消除冗余的不等式产生的变量消除步骤，消除冗余系统的约束，识别变量系数的迹象，收紧松散的约束，最后，识别和纠正与舍入误差的约束。