多时代码生成器及多目标代码优化

Générateur de code multi-temps et optimization de codemulti-objectifs维克托·洛米勒引用此版本：维克多·洛米勒Générateur de code multi-temps et optimization de code multi-objectifs. Génie logiciel[cs.SE].格勒诺布尔大学，2014年。法语NNT：2014GRENM 050。电话：01551811v2HAL Id：tel-01551811https://theses.hal.science/tel-01551811v22017年7月4日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaireTHAPOSE为了获得等级格勒诺布尔大学博士专业：信息逮捕日期：2006年Présentée par维克托·洛穆勒亨利-皮埃尔·查尔斯的命令基础设施和物流工作室，CEA格勒诺布尔“数学、科学和信息技术、信息技术”博士学校Générateur de code multi-temps etoptimizationdecodemulti-objectifsThèse soutenue publiquement le，devant le jury composé de：M.让-弗朗索瓦·梅奥Joseph Fourier大学校长M.盖尔·托马斯巴黎南部电信公司顾问，特别报告员M.弗朗索瓦·博丹雷恩第一大学讲师，我是卡琳·海德曼皮埃尔和玛丽·居里大学联合会硕士M.阿尔伯特·科恩Directeur de recherche àM.蒂埃里·莱普利英伟达高级研究工程师，考官M.阿亚尔·扎克斯以色列英特尔高级研究工程师，考试官M.亨利-皮埃尔·夏尔Directeur de recherche au CEA LIST，Directeur de thèse索迈尔索迈尔岛图三五.一览表表六回忆录七1介绍11.1Contexte etnouveaux挑战21.2捐款31.3PlanduPunct42Étatde2.1Les tempsde compilations62.2建筑122.3Temps de compilationet optimisations152.4Rétroactionet prediction.302.5结论313代码33的生成方法3.1Contextegénéral343.2在GPU36上的性能和输入3.3代码37动态专业化的收益和成本3.4结论414Outillagesdépés434.1Motivationet approches动机与方法444.2Approche orientée générateur：deGoal464.3Approche orientée fonctionnelle：Kahuna504.4结论655GPU66上的GEMM辅助适配5.1GPU68编程5.2产品matriciel705.3解决方案提案755.4自动调谐77第二次索梅尔会议5.5学徒机795.6Résultats discussion讨论结果815.7Pistes5.8结论886第89号法典产生的影响研究6.1双二阶滤波器916.2Exérimentations实验956.3Résultatsdiscussions讨论结果986.4Conclusionde6.5卡胡纳革命1106.6结论1137结论1157.1Résumédes realisations1167.2讨论1187.3前景119BibliographiePersonnelle122Bibliographie书目124图表1.1申请延期........................................................................................................21.2插图del'avantage de la virtualisation dans le suivi de l'évolution d'unearchitecture. ..................................................................................................32.1编辑的............................................................................................................72.2Cycle de.........................................................................................................82.3最后一个......................................................................................................112.4以无环方向的图形为例..............................................................................122.5Cortex-A8组织............................................................................................132.6费米体系结构中的流多处理器组织。....................................................142.7生态系统LLVM。...................................................................................... 172.8Java和Android程序的统计编译过程182.9Processus de compilationde Spiral......................................................... 192.10 Cyclede vie212.11 解释过程......................................................................................................242.12 在JIT案件中的汇编过程.............................................................................242.13 Speccialisationlégère（sans représentation intermediaire）..............262.14 专业化基础上的l '优化d' une représentation inter-mediaire。...........293.1Analogie du pontde Berkeley3.2背景知识的演变..........................................................................................383.3Vitesse4.1Processus de compilationde deGoal474.2Principede fonctionnement de Kahuna534.3Lesdeux types de spécialisation de Kahuna544.4Flot de compilationde Kahuna554.5联络时间的分析工作量很大......................................................................594.6控制器故障图表示例..................................................................................604.7Processus de génération du sitede production635.1CUDA中的程序层级。..............................................................................685.2利用données par le noyau5.3说明du增益潜力de性能pour la SGEMM735.4适应性藏书楼的建设..................................................................................76IV表DES图5.5Arbre de décision générépour C4.5........................................................ 805.6在执行过程中进行改编的汇编性能关于MAGMA82性能报告的理想案例5.7Balayage des configurations pour3 cas.................................................. 825.8通过与MAGMA 84演出的关系改编的书目演出5.9可能的进化是进化论..................................................................................886.1Lesdifférents processessus de générations utilisés et évalués............946.2Fonctionnement ducouple gem 5/McPAT.............................................966.3SOX98过滤器的性能6.4代码100总经理执行时间6.5Taille des noyaux decalcul générés1036.6由工艺105组成的一般噪音的能量消耗6.7Concommationéenergétique des noyaux générés par étages du cæur.1066.8Instructionsemises par les noyaux générés1076.9通用代码108的能量消耗6.10 Extrait de la sélection6.11 在临时法庭上表演的舞蹈团的演变范例113一览表2.1综合艺术中的被剥夺权利的途径..................................................................323.1Example d'objectifs de compilation et de metriques associéespossibles. ....................................................................................................353.2MAGMA的程序名称是一个乘法矩阵。...........................................................374.1List des intrinsèques Kahuna servant à l'annotation des programmes.......................................................................................................................565.1过程名称与性能指标的比较为了MAGMA和理想。...............................................................................745.2l’ensemble...................................................................................................805.3图5.7中的3个矩阵测试以及相关性能。...................................................835.4决定权的一般规则名称..............................................................................845.5Résumédes performances de la bibliothèque856.1对一般编码能力的定性评估......................................................................926.2Paramètres de notre plate-formde simulation976.3获得不同的生成方法，通过与静态版本的关系，以及通过与性能crête的关系定位。..............................................................................................986.4代码生成（节拍）终止 . 1016.5关于编码102产生办法的备忘录6.6Consommationdynamique de la memoire1046.7Amortissementdu surcoquartts de la génération de code（énergie）108Table des listages2.1Fichier..........................................................................................................202.2菲奇尔角......................................................................................................202.3Fichier C avec le point.............................................................................. 202.4方案C相当于LTO通过后的方案...............................................................203.1Implémentation......................................................................................... 393.2Cortex-A8的通用代码为clang/LLVM 3.4............................................... 403.3Cortex-A15的通用代码为clang/LLVM 3.4............................................. 404.1模板C++45形式的乘法运算4.2有限脉冲响应（FIR）滤波器的一般实现。............................................454.3compilette produisant un code equivalent aulistage 4.1. ...................474.4compilettesimilaire au listage4.3maispermettant，àl'exécution，选择一个加法和一个乘法。......................................................................484.5示例代码机ARM产品par la compilette dulistage4.3pour b= 10504.6示例代码机ARM产品par la compilette dulistage4.3pour b= 2504.7Fonglycahuna équivalente à la fonglycudulistage 4.1. .......................574.84.7列表中的fonglycahuna生产地点的识别。.........................................574.9Illustration de la cractiondans LLVM.....................................................614.10 4.9版本的说明书在一个小盒子里。........................................................ 614.11 4.9级动力学说明书已在后台发布。......................................................... 614.12 Fongly C annotée. KAHUNA_INPUT_I是一个宏，它是一个简化器，可以在内部使用。........................................................................................656.1过滤器底座的安装......................................................................................936.2卡哈纳的实施..............................................................................................95雷默西芒在进入这颗心之前，我在CEA工作了三年我特别感谢亨利-皮埃尔·查尔斯的导演，他接受并培养了我的能力，使我能更好地了解这一点，这是一个医生的形象。耐心、谨慎和耐心是非常重要的，尤其是在怀疑的时候。让·弗朗索瓦·梅奥先生请我感谢盖尔·托马斯先生和弗朗索瓦·博丹先生接受我的感谢卡琳·海德曼女士艾伯特·科恩先生蒂埃里·莱普利和阿亚尔·扎克斯先生接受我的陪审团成员我 很 感 谢 LIALP 的 全 体 成 员 ， 过 去 和 La très bonne ambiance dulaboratoire a rendu ces trois années de thèses prolifique et agréable.塞拉非常喜欢这份充满激情的工作。我特别感谢达米恩·库鲁塞和费尔南多·远藤在我的工作中帮助我。我特别感谢我的同事和朋友在实验室里，感谢你们所有人都能看到我，让我能留下来，让我们一起度过过去的时光我特别感谢伊万·洛帕德为我们的讨论和LLVM的助手，谢谢！我会向贝特朗·勒琼表示感谢，为了他的健康和永不失败的支持，甚至13年前。感谢桑迪·索皮克的帮助，感谢他在这里，在这里，在这里。我感谢我的祖父母对我的爱。我希望能以我的母亲和兄弟为荣。通过对各种选择的分析，我们可以从我的资源中找到语言和动力，以便在怀疑的时刻提前行动。C’est pourquoi jesouhaiterais leur dédier cette감사합니다דותה米绍特拉·贾拉马ありがとう技术工人Дякую谢谢谢谢اركش穆尔古梅斯克迪厄MahaloGrazieGracias奥布里加多第一章介绍索迈尔1.1背景和新挑战。. . . . . . . . .21.2捐款。. . . . . . . . . . . . . . . . . . . . .31.3计划。. . . . . . . . . . . . . . . . . .4汇 编 是 信 息 学基 础 研 究 的 一 部 分 。 Apparu avec les langages de hautniveau，et quasiment dès ses origines，elle a été utilisée pour améliquenciesles performance des applications.随着建筑和新用途的发展，编制工作越来越快，克服了材料能力开发的困难随着信息技术的诞生，我们将一个世界从一个简单的领域（与巨像的密码分析）转向一个世界，这个世界将利用各种各样的和复杂的体系结构这些目标也很重要，以执行任务为中心，主要涉及记忆、能源消耗或便携性问题AutantLes stratégies de génération de code ont progressivement évoluée.在纯静态的基础上，目前采用的战略将具有不同的动态性便携性：材料市场的细分有助于实现应用程序便携式解决方案的这是为了证明申请人没有必要对这一申请进行说明。性能：它是一种快速、反应、能源经济应用的理想工具，也是一种可接受的企业记忆。对于执行vitesse随着智能手机市场的爆炸式增长和物联网（IoT）的迅猛发展，人们对电子消费和存储的需求也日益增加去码第二章1. 介绍贝索安ConcepteurUtilisateur唐内斯语言方案编制印版图1.11.1背景和新挑战图 1.1 显 示 了 一 个 应 用 程 序 的 开 发 周 期 。 Pour répondre à un besoinutilisateur ， leconcepteur va créer une solution en utilisant divers langagespour générer une application pour une plate-form（physique ou virtuelle）.然而，为了获得良好的性能，我们提出了一个问题，即印版的问题和对données的敏感性问题La question de la plate-form peut se poser关于印版性能的问题非常复杂Quand la plate-forme est parfaite- ment connue cela autorise但是，逻辑生命的持续时间比材料更长，而且很可能印版会随着应用生命的变化而变化L'utilisationdetechnologiedevirtualisationpeutalorspermettreauxapplications de suivre les évolutions de la plate-form [20]. 图1.2说明了在一个建筑结构的后续演变的情况下在第一种情况下（图1.2a），一个应用程序是为CPU 1编译的，为了让编译器知道它存在一个扩展，并在检测到漏洞时使用它从CPU 2开始，他就像CPU 1一样，可以提出一个扩展。程序的统计面一般代码不适用于使用者的测量在第二种情况下（图1.2 b），应用Le compilateurjuste-à-temps present sur les deux plates-formes a la pleine connaissance desextensions presentes sur les deux CPU，et est donc en mesure de créer uncode utilisant les extensions presentes sur la machine.然而，虚拟化技术的利用并不能保证性能和材料的充分利用。在GPU（图形处理单元）的基础上，构建了虚拟化平台，以保证但对于材料能力的提高，并不需要对这些性能进行评估。随着多核心架构的到来，某些算法的敏感性也发生了变化。在治疗过程中，细胞对治疗过程的影响.exe文件EXT1CPU 1ext2ext1CPU 2八位码JITJITEXT1CPU 1ext2ext1CPU 21.2. 捐款.3(a) 近似纯静态。（b）采用虚拟化。图1.2-虚拟化在一个建筑的后续发展中的优势的obtenus，les accès memoiresetc.事实上，虚拟化技术并不适用于那些存在于遗传学领域的资源Ces outilsvont prendre une place non négigable dans le système ， consommer de laRAM，des cycles CPU et de在物联网的背景下，这些资源是非常罕见的但即使是对系统的约束，也可能很难利用这些技术来适应算法1.2贡献Cette thèse a été dépée autour de 2 axes：Dans le contexte des multi-cæurs：Nous avons étudié le comportement desprogrammes sur GPU Nvidia，en cherchant à savoir：— S’il— 你对这件事有什么看法— 如何Dans le contexte我们应该研究一下计算对执行力、记忆力和几何学的影响第一章 介绍1.3计划第2章介绍了多时间编译的艺术Nous presésenterons une definition de lacompilation multi-temps et nous problems les différentes technologies decompilation et de génération de code en fonetary de son temps这一部分允许在技术落后的情况下进行大规模平衡，因为这些情况下存在着优势和不便。第三章提出了我们所确定的艺术水平的限度，并指出了贡献的来源Nousverrons le problem de la non prise en compte des données dans我们还关注有关优化算法和书目数据管理的问题。我们也对第二个贡献轴的出发点-代码生成和专门化的多种方法感兴趣第4章介绍了一些有待回答的问题。在这一部分中，他没有提出这样的问题，即他在水中的外观和逻辑都是不正确的。所提出的方案分别来自Goal和Kahuna，其中两个方案提出了一种专门的执行代码生成方法Le premier，deGoal，vise à laisser au programmeur un large control ôle sur le code qu第二，卡胡纳，Vise à faciliter le décampement de généração de code à第5章介绍了Nvidia GPU上的多应用矩阵算法的一项研究成果在这一部分中，我们开始介绍GPU上GEMM的实现以及性能调整方法Nous présenteronsensuite une limitation deIl sera montré la méthodologie dépée pour répondreà cette limitation suivie de son evalua- tion.第6章集中讨论了印版的装载问题，并对专业化的优化进行了研究。我们研究了第4章中存在的问题，因为这些问题是LLVM框架上的基本方法。在这一章中，我们集中讨论了多学科编码的产生方法的优点和缺点。七个礼拜后就这样结束了。我们要感谢对这份报告的贡献，让工作顺利进行。我们也在一个全球性的背景下重新审视这些工作，并在这些工作的发展轨迹上提出这些工作，而这些工作在建筑发展趋势中的作用并不第二章艺术报索迈尔2.1编辑的时间。. . . . . . . . . . . . .62.1.1Introduction à la compilation et transformationde代码62.1.2导言. 82.1.3Introduction auxreprésentations intermediaires102.2建筑122.2.1架构Cortex-A8132.2.2GPU CUDA14架构2.3Temps de compilationet optimisations152.3.1Compilation statique：approche traditionnelle152.3.2Compilation statique：approche sourceà source182.3.3Éditiondes liens202.3.4Pré-déploiementet déploiement212.3.5Chargementet exécution232.4Rétroactionet prediction.302.4.1Rétroaction302.4.2预期312.5结论..............................................................................................31L’évolution 为了应对计算能力的问题，这些问题从一个单一的体系结构转向多个体系结构，通过多个体系结构，从程序员的层面上提出新的问题就像我们在本章中看到的那样，支持并优化了在部分编译器和代码生成效率上所代表的架构上的应用程序在这一章中，我们介绍了多时间代码生成的艺术但这是巴莱尔的6第二章. 艺术之旅Differérentes techniques de compilation et génération de code en fonetary dequand ils interviennent dans la vie de我们开始界定汇编的概念和时间Nousintroduirons aussi les representations intermediaires qui est un pointimportantdanslacompilationetNouspresésenteronsensuitedeuxarchitectures distinctes par leurs objectifs et que nous utiliserons dans la suitede ce pouche. Nous fe- rons ensuite un tour des différentes techniquesutilisées dans2.1编辑时间2.1.1Introduction à la compilation et transformation decodeAho等人[3]definissent de façon générique le compilateur comme étant“unprogrammelisantunprogrammedansunlangage，lelangagesource，etletra-duiten un programme équivalant dans un autre langage，le langage cible”。虽然它很大很简单，但它包含了各种不同的方法。第一个编译器出现在50年，由Grace Hopper为UNIVAC [89]开发了A-0系统。 该编译器无法执行程序组装操作，因此可能会产生费用。在50年的最后一年里，第一位编译者完成了对FORTRAN语言的编写，并对它持乐观态度。近年来，编纂者继续平行于语言发展，提出了新的优化问题，以确保语言偏离最高水平La concept de ces compilateurs a aussi évolué vers une plusmodularité et une architecture plus ou moins commune aujourdLes compilateurs modernes sont le plus souvent architecturés autour de 3étages（illustré dans la figure2.1）：前端部分：负责对语言源的讲解、错误报告、语言的特殊优化以及对后续版本的中间代表（RI）的翻译。我们也可以把这一部分称为中间部分（中端）：负责国际扶轮方案语言独立分析和转换的部门。Partie arrière（后端）：étage chargé des optimisations spécifiques au lang-gage cible et deL’avantage Ainsi lors de第一部分在语言程序中代表入口程序，以确保程序形式良好（语法Une foiscette phase de vérificationseffectuée il peut éventuellement effectuer destransformationspropresaulangageouaudomaine.Enfinunephasedetransduction（72.1. 完成时间源分析翻译由RI的优化优化de la RI的优化Traductionde la RI排放额部中间党架次上党图2.1（LLVM）permet de générer la représentation intermediaire du programmedans celle de la partie intermediaire du compilateur.Partransuction ， ondesigne le passage中间方协调了各个独立的城市优化阶段。Durant ces phases，在实践中，对城市或城市家族的特殊优化也可以使其成为一种新的形式，使其能够成为中间商代表的第三部分。到达的部分负责将节目翻译成自己的语言。这是目的地语言中的代码在语言机器中执行任务的情况下，执行部分实现了指令选择、寄存器分配、Navisphere命令和特定优化，如窥视孔优化、if转换、强度降低等。在一般情况下，现代编纂者应利用多个中间媒介来有效地开展业务（见第2.1.3节）。另一方面，LLVM [51]利用类似于中间件LLVA [2]的表示方法，将SDAG 、 MI （ 机 器 指 令 ） 和 MC （ 机 器 代 码 ） 作 为 中 间 件 。 LegreffonPolly[40] ，whieffectuedestransforma-tionspolyédriquesdansLLVM ， intervient dans la partie intermedédiaire et utilize aussiplusieursautresrepresésentationsduprogrammepourcommuniqueravecCLooG，根据语言来源和来源的性质，可以划分不同的类型8第二章. 艺术之旅Algorithme程序语言汇编迭代继续优化编译菲谢尔·奥贝耶留置权出版社可执行的