多时间代码生成器和多目标代码优化

多时间代码生成器与多目标代码优化维克多·洛米勒引用此版本：维克多·洛米勒。多时间代码生成器和多目标代码优化。软件工程[cs.SE]。格勒诺布尔大学，2014年。法语。NNT：2014GRENM050。电话：01551811v2HAL ID：电话：01551811https://theses.hal.science/tel-01551811v2提交日期：2017年HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire论文要获得的等级格勒诺布尔大学博士专业：计算机科学部长令：2006年提交人维克多·洛姆勒论文由亨利-皮埃尔·查尔斯指导在CEA格勒诺布尔芯片室内编写和多时间代码生成器和多目标代码优化论文公开答辩，评审团成员包括：M.让-弗朗索瓦·梅豪约瑟夫·傅立叶大学教授M.盖尔·托马斯巴黎南部电信教授，报告员M.弗朗索瓦·博丹雷恩第一大学教授卡琳·海德曼女士皮埃尔和玛丽·居里大学讲师M.艾伯特·科恩INRIA研究总监M.蒂埃里·莱普利Nvidia高级研究工程师，审查员M.阿亚尔·扎克斯英特尔以色列公司高级研究工程师，审查员M.亨利-皮埃尔·查尔斯CEA LIST研究主任，论文主任总结总结I图三表表五列表列表表VI感谢VII1引言11.1背景和新挑战21.2贡献31.3手稿大纲42最新技术水平2.1编译时间62.2架构122.3编译和优化152.4反馈和预期302.5结论313代码生成的锁333.1一般背景343.2GPU上的数据和性能之间的关系363.3动态代码373.4结论414开发的工具434.1动机和方法444.2面向生成器的方法：deGoal464.3功能导向方法：Kahuna504.4结论655将GEMM应用于GPU66上的数据5.1GPU编程685.2矩阵乘积705.3建议的解决方案755.4自动调谐77II摘要5.5机器学习795.6讨论结果815.7发展和改进的可能性5.8结论886研究6.1双四滤波器916.2实验956.3讨论结果986.4实验结果6.5Kahuna110的演变6.6结论1137结论1157.1成就摘要1167.2讨论1187.3前景119个人参考书目122参考书目124图表1.1应用程序的开发............................................................................................21.2说明虚拟化在跟踪体系结构演变方面的优势。..........................................32.1编译器的阶段................................................................................................72.2应用程序的通用"生命周期.......................................................................... 82.3AST示例...................................................................................................... 112.4有向无循环图示例......................................................................................122.5Cortex-A8的组织........................................................................................132.6费米架构中流多处理器（SM）的组织。................................................142.7LLVM生态系统.......................................................................................... 172.8Java和Android程序的静态编译过程十八2.9螺旋编译过程..............................................................................................192.10 Android 4.4平台上的应用生命周期212.11 解释的过程..................................................................................................242.12 JIT情况下的编译过程.................................................................................242.13 轻度专业化（无中级代表..........................................................................262.14 基于中间表示的优化的专业化。..............................................................293.1伯克利大桥的类比353.2背景知识的演变..........................................................................................383.33.1内核在不同解卷因子下的执行速度4.1DeGoal47的编译过程4.2Kahuna53的工作原理4.3Kahuna54的两种专业化类型4.4Kahuna55的编译流4.5链接时间分析的工作流..............................................................................594.6控制流图示例..............................................................................................604.7生产场地的生成过程635.1CUDA中的流程层次结构..........................................................................685.2执行内核对数据的使用5.3SGemann73的潜在性能提升示例5.4构建自适应库..............................................................................................76四、图5.5为C4.5生成的决策树..................................................................................805.6编译器性能与运行时适应性与MAGMA82性能相比的理想情况5.7扫描3种情况下的配置。............................................................................825.8运行时自适应库性能与5.9学习过程中可能发生的变化......................................................................886.1使用和评估的不同生成过程......................................................................946.2gem 5/McPAT对的工作原理.................................................................... 966.3来自NOX98的过滤器性能6.4代码生成器100的执行时间6.5生成的计算1036.6每个处理器组件产生的内核功耗1056.7每个堆芯级产生的堆芯能耗。1066.8由生成的内核发出的指令1076.9代码生成器的能耗1086.10 Kahuna 110的指令选择摘录6.11 数据集随时间演变的示例113图片列表2.1现有技术中开发的方法..................................................................................323.1编译目标和可能的相关指标的示例。......................................................353.2MAGMA在矩阵乘法过程中创建的进程数。.................................................. 374.1用于注释程序图的Kahuna固有项列表。................................................565.1过程数量和获得的性能的比较MAGMA和理想情况...................................................................................745.2l’ensemble...................................................................................................805.3图5.7中的3个测试矩阵及其峰值性能。.................................................. 835.4从决策函数生成的规则数..........................................................................845.5库性能摘要856.1对代码生成器的能力进行定性评估..........................................................926.2我们的模拟976.3与静态版本相比，不同生成方法的增益，以及与峰值性能相比的定位。..............................................................................................................986.4代码生成额外成本的摊销（时间） . 1016.5代码生成方法的内存足迹1026.6内存的动态消耗1046.7代码生成额外成本摊销（能源）108列表表2.1文件..............................................................................................................202.2文件C。.......................................................................................................202.3带有程序入口点的C文件...........................................................................202.4通过LTO后的等效C程序...........................................................................203.1向量/向量乘法的实现.................................................................................393.2代码由用于Cortex-A8的............................................................................403.3代码由用于Cortex-A15的..........................................................................404.1C++45模板形式的乘法函数4.2FIR滤波器（有限内隐式响应）的通用实现。........................................454.3生成与列表4.1等效的代码的编译器.........................................................474.4编译器类似于清单4.3，但在运行时允许在加法和乘法之间进行选择......................................................................484.5对于b= 1050，由列表4.34.6由列表4.3编译器生成的用于b= 250的4.7Kahuna函数相当于列表4.1中的函数。...................................................574.8确定表4.7中卡胡纳函数的生产地点。.....................................................574.9LLVM中强制的示例.................................................................................. 614.10 清单4.9中的常数指令进入一个孤岛。.....................................................614.11 清单4.9中的动态指令进入模式。.............................................................614.12 带注释的C函数。KAHUNA_IPT_I是一个宏，旨在简化内部函数的使用。.............................................................................................................. 656.1过滤器的基本实现......................................................................................936.2Kahuna的实施............................................................................................95谢谢你在进入这篇论文的核心之前，这是我在CEA工作3年的成果我特别要感谢我的论文导师亨利-皮埃尔·查尔斯，他接受了我，并相信我有能力完成这篇论文，尽管作为一个博士生，我的情况有些不典型。他的耐心，建议和可用性是宝贵的，特别是在怀疑的时刻，点缀着这篇论文。我要感谢Jean-François Méhaut先生我要感谢Gaël Thomas先生和François Bodin先生我要感谢Karine Heydemann女士、Albert Cohen先生、Thierry Lepley先生和Ayal Zaks先生同意成为我的评审团我感谢非常好的实验室气氛使这三年的论文多产和愉快。能在这个知识渊博、充满激情的团队中工作是一件非常愉快的事情我要特别感谢DamienCouroussé和Fer-nando Endo对我工作的大力帮助我特别要感谢我在这个实验室里遇到的同事和朋友，感谢你们所有人的参与，感谢你们对我的支持，感谢你们在一起度过的所有我特别感谢IvanLlopard花时间与我们讨论，并感谢他对LLVM的帮助。我要感谢Bertrand Lejeune，即使在13年后，他仍然保持着良好的幽默感和坚定不移的支持。感谢Sandy Saupique的帮助，尽管时间、距离和我的性格，他总是在那里。我想感谢我的祖父母对我的关爱。最后，我想感谢我的母亲和兄弟。通过他们对事物的精细分析，他们能够找到语言，并从我身上汲取资源，以便在怀疑的时刻前进。C’est pourquoi jesouhaiterais leur dédier cette감사합니다דותהMisaotraDjaramaありがとう特谢克克勒D谢谢谢谢你اركش多umesc上帝保佑Mahalo感恩格拉西亚奥布里加多第一章简介总结1.1背景和新挑战。... ... ... ... ... ... ... ... ...21.2捐款。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...31.3手稿大纲。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 4编译是计算机科学的基础研究课题之一。它与高级语言一起出现，几乎从一开始就被用来提高应用程序的性能为了跟上不断发展的体系结构和新的用途，编译很快就遇到了充分利用硬件功能的困难自从计算机科学诞生以来，我们已经从一个为特定领域（Colossus密码分析）保留的世界发展到一个使用各种异构架构的目标也发生了变化，以前以执行速度为中心，现在包括内存、能耗或可移植性所有代码生成策略已经逐渐发展。最初纯粹静态的战略，由于不同的需求，现在越来越多地采用动态的战略便携性：硬件市场的细分要求设计人员为其应用提供便携式解决方案其必然结果是，在开发应用程序时，不一定知道该应用程序将在哪个指令集上执行。性能：需要快速、响应迅速、节能或具有可接受内存占用的应用程序。对于执行速度随着代码2第1章。 引言需要设计师用户语言数据程序生成平台图1.11.1背景和新挑战图1.1显示了应用程序的开发周期。为了满足用户需求，设计人员将使用各种语言创建解决方案，以生成平台（物理或虚拟）的应用程序然而，要获得良好的性能，就需要考虑目标平台和数据敏感性问题平台问题可能是从可移植性的角度提出的，可移植性平台的性能问题当平台是完全已知的，它允许但是软件的生命周期比硬件长，因此平台很可能在应用程序的生命周期内发生然后，虚拟化技术的使用可以允许应用程序跟上平台的发展。图1.2说明了在第一种情况下（图1.2a），为CPU 1编译一个应用程序，编译器知道CPU 2与CPU 1属于同一系列，但提供了额外的扩展由于代码是静态生成的，在第二种情况下（图1.2b），两个平台上的即时编译器都完全了解两个CPU上存在的扩展，因此能够使用机器上存在的扩展创建但是，使用这些虚拟化技术并不能保证硬件的性能和充分利用。以GPU（图形处理单元）为例另一方面，所获得的性能不一定与设备的能力相匹配。随着大规模多核架构的出现，一些算法的数据敏感性也发生了变化。由于处理是根据数据划分的，因此数据会影响处理的数量.exeext1CPU 1ext2ext1CPU 2代码到字节JITJIText1CPU 1ext2ext1CPU 21.2. 捐款3(a) 纯静态方法（b）采用虚拟化的方法。图1.2访问、存储器访问等。最后，虚拟化技术仅在存在可用于这些世代目的的资源时才可用这些工具将在系统中占据相当大的位置，消耗RAM、CPU周期和例如，在物联网的背景下，这些资源由于稀缺而变得但是，即使对于不太受约束的系统，也很难1.2贡献本论文围绕两个轴展开：在多核环境中：我们研究了程序在Nvidia GPU上的行为，以了解：— S’il— 我们如何克服这种敏感性？— 如何在受限体系结构的背景下因此，我们试图找出收益和成本对计算内核的执行速度、内存和功耗的影响4第1章. 引言1.3手稿计划第2章将介绍多时间编译的最新技术水平我们将介绍多时间编译的定义，并根据其作用时间对不同的编译和代码生成技术进行分类这一部分将使我们能够对所开发的技术、原因以及在这些时刻进行干预的利弊进行广泛的扫描第3章将介绍我们已经确定的最新技术水平的局限性我们将看到在GPU上的GEMM的性能优化中忽略数据我们还将提出如何优化该算法以及如何管理由此创建的库的大小的问题我们还将关注作为第二个贡献轴起点的指标：代码生成和专业化的第4章将介绍为回答这些问题而开发的工具。在本节中，我们将只介绍这些工具及其构建逻辑。这里介绍的工具是deGoal和Kahuna，这两个工具都提供了在运行时生成代码的特定方法第一个是deGoal，旨在让程序员对他们希望在运行时生成的代码进行广泛的控制第二个是Kahuna，旨在促进运行时代码生成器的开发，这些代码生成器第5章将介绍Nvidia GPU上的矩阵多重复制算法的研究结果在本节中，我们将首先介绍然后，我们将介绍该方法在某些条件下获得的性能的局限性它将显示为解决这一局限性而开发的方法，然后对其进行评估。第6章将重点介绍嵌入式平台和通过专业化进行优化的研究。我们将研究第4章中介绍的工具的行为，以及基于LLVM框架的方法。在本章中，我们将重点介绍基于多个度量的几种代码生成方法最后，第7章将结束这一论点。我们将总结在这份手稿中提出的贡献，还有更多的工作要做。我们还将把第二章最新技术水平总结2.1编译时间。... ... ... ... ... ... ... ... ... ... ... ... ...62.1.1编译和转换简介代码62.1.2编译时间简介82.1.3中间表示法导论102.2架构122.2.1Cortex-A813架构2.2.2CUDA14 GPU架构2.3编译和优化152.3.1静态编译：传统方法152.3.2静态编译：源代码到源代码182.3.3链接编辑202.3.4部署前和部署212.3.5加载和执行232.4反馈和预期302.4.1反馈302.4.2预期312.5结论..............................................................................................31L’évolution 为了满足对计算能力日益增长的需求，芯片已经从单核架构转变为多核架构，甚至大规模多核架构，这在如何对其进行编程方面提出了新的正如我们在本章中，我们将介绍目标是消灭他们6第二章。 最新技术水平不同的编译和代码生成技术，取决于它们在应用程序生命周期中的介入时间我们将从定义编译和编译时间我们还将介绍中间表示，这是编译和优化中的一个重要点然后，我们将介绍两种用途不同的体系结构，我们将在本手稿的其余部分使用这两种体系结构。然后，我们将介绍最先进的技术中用于描述、转换、优化和发展应用程序的不同技术2.1编译时间2.1.1代码编译和转换简介Aho等。[3]一般地将编译器定义为"读取一种语言的程序、源语言和翻译语言"。它被转换成另一种语言的等效程序，即目标语言。"虽然它是广泛和简单的，但它很好地涵盖了各种现有方法的范围。第一个编译器出现在20世纪50年代，由Grace Hopper为UNIVAC开发的A-0系统。 这个编译器只执行它先前加载的例程的汇编操作。在20世纪50年代后期，第一个完整的、优化的FORTRAN编译器出现了，它允许创建可执行的程序，而不需要通过汇编表示。多年来，编译器继续与语言并行发展，随着语言变得越来越高级，提出了新的优化问题这些编译器的设计也朝着更大的模块化和今天或多或少常见的体系结构发展现代编译器通常围绕3个阶段构建（如图2.1所示）：前端：负责读取源语言、报告错误、特定于语言的优化以及翻译到下一级的中间表示（IR）的级。我们也可以将此部分称为中间端：负责IR中程序目标语言的独立分析和转换的后端：负责特定于目标语言的优化和以目标语言发布程序的阶段L’avantage 因此，当添加对新源语言或目标语言的支持时，只前端以接近语言的形式构建输入程序的表示，以确保程序的格式正确（符合语法和语法完成此检查阶段后，它可能会执行特定于语言或域的转换。最后是翻译阶段（72.1. 编译的时间来源分析来自RI的翻译最优化RI的优化最优化国际扶轮的翻译发射正面部分中间部分退出背面部分图2.1LLVM）允许在编译器的中间部分翻译是指从一个中间表征到另一个中间表征的转换中间部分协调独立于目标的优化阶段。在这些阶段中，实际上，也可以在此级别启动特定于目标或目标族的优化，以便可以利用其中间表示。后端将负责将程序翻译成它的语言。此步骤以目标语言执行在以机器语言发布的情况下，后端执行指令选择、寄存器分配、调度和特定于目标的操作，如窥视孔优化、IF转换、强度降低等。一般来说，现代编译器会根据要执行的操作使用几个中间表示（参见2.1.3节）。例如，LLVM [51]在其中间部分使用LLVA [2]作为中间表示，在其后面部分使用SDAG、MI（机器指令）和MC（机器代码）。在LLVM中执行多面体变换的Polly插件[40]介入中间部分，并且还使用程序的其他几个表示来与多面体优化工具ClooG通信根据源语言和目标语言的性质，可以指定不同类型的8第二章。 最新技术水平算法程序语言。迭代编译持续优化编译文件对象链接的编辑可执行的部署加载引导式编译按配置文件执行图2.2编译器可以在它们介入的不同时刻被2.1.2编译时间简介编译时间是应用程序生命周期中的一个时间点，在此期间，对环境的了解变得更加清晰这一新知识为优化应用程序性能（执行速度、内存使用量或能耗）创造了机会例如，当在平台上安装应用程序时，程序可以访问该平台这可以从了解数据高速缓存的大小到了解指令集体系结构据了解，根据应用程序的类型，某些信息或多或少是已知的。123456789静态静态/动态动态92.1. 编译的时间在生命周期中。图2.2概括地显示了应用程序生命周期的不同阶段我们可以将其分为三大类：设计和编写：程序生命周期的初始阶段。它在功能层面上进行了思考，然后在算法层面上进行了思考，最后实现了（时刻1和2）。生成：从程序实现开始对程序进行转换以生成可由机器使用的对象的时刻（时刻3到7）。实现：指令与用户数据一起执行的最后时刻这些组不是从设计到计划执行的时间和步骤的线性序列迭代编译（图2.2中的绿色虚线箭头）重用编译过程中积累的信息来重新编译应用程序编译时使用的启发式（如例如，要部分展开循环，您需要知道循环主体的大小。在第一次编译时，此大小是未知的，因为代码尚未生成。在第二次迭代中，可以重用该信息以更优化地展开该循环。然而，为了以最佳方式展开它，我们需要知道指令缓存的大小配置文件引导编译或持续优化（图2.2中的绿色箭头）是实现和生成之间联系的两个在第一种情况下，在构建应用程序之后分析的结果将允许重新启动编译阶段，并用这些结果替换启发式。这种方法的问题是，结果是一个二进制不变的，也就是说第二种情况ef-在实际条件下执行应用程序时执行分析这些结果被重用以像以前一样优化L’inconvénient majeur de cette approche est celui这些组静态：安装的上游阶段，在此期间进行在此阶段，对数据和最终目标的了解极其有限。动态：应用程序将部署（安装）到系统并运行的阶段我们可以将其分解为3个步骤：部署：10第二章。 最新技术水平加载：运行时：生成阶段要么完全发生在静态阶段，要么发生在动态阶段，要么发生在两者之间的"阶段"。在C程序的情况下在Python中，生成是在运行时完成的最后，在Java的情况下，代码在静态阶段被转换为字节代码，并在运行时被解释或转换2.1.3中间表示法简介为了执行这些优化，编译器将使用一个或多个中间表示（IR）。在现代编译器中，无论编译阶段如何，都使用一种表示法（图2.1）。 RI是优化和代码生成的中心点之一。它们允许对程序进行操作，并确保转换的不同阶段 有很多种表示法，每种表示法都有其优缺点。[82]Stanier等人[82]将IR分为三类：线性：将表示分组为伪代码，其范围可以循环图：将表示分组为循环的图形。非循环图：将表示分组为禁止循环的图。这些RI可以突出显示对数据或控制的依赖关系最后，一些表示并不代表本节的其余部分将介绍为以下章节中介绍和使用的工具操作2.1.3.1线性表示法3地址代码：此表示形式是一系列例如，t1→a+bt2→b+at3→c+dt4→t1×t2t4→t4×t3这种表示法在现代编译器中与图形表示法混合使用。L’avantage de cettereprésentation est sa li- sibilité, mais surtout elle permet la modularité descompilateurs modernes