高级循环优化：拆分切片的新策略与专业化分离

皮埃尔和玛丽·居里INRIA计算机、电信和电子博士学院，高等师范学校/PARKASA D E C O U P L D A P R O A C HT O H I G H-L E V E L O O P O P T我在I O N-由Tobias Christian Grosser计算机科学博士论文由阿尔伯特·科恩和斯文·韦尔杜莱格共同导演于2014年10月21日发表并公开支持在陪审团面前，陪审团由：报告员：犹他州玛丽霍尔弗朗兹·弗兰凯蒂卡内基梅隆大学考官：Stef Graillat皮埃尔和玛丽居里大学Jean-Luc Lamotte皮埃尔和玛丽居里大学Franz Franchetti卡内基梅隆大学Ponnuswamy Sadayappan俄亥俄州立大学阿尔伯特·科恩因里亚Sven Verdoolaege高等师范学校Tobias Grosser：高级循环优化、磁贴形状、多面体构建块和低级编译器的分离方法，Novem- ber19，2014R S M尽管对高级循环优化进行了几十年的研究，并成功地将其集成到C/C++和FORTRAN编译器中，但大多数循环转换系统只能部分地解决当今硬件日益复杂和多样性所带来的挑战。利用专门的知识来获得用于复杂目标（如加速器或多核中处理器）的最佳代码，对现有的形式化和循环优化工具提出了挑战。因此，独立地开发利用专用于一个领域的知识的新的优化方案，而不利用现有的技术。现有的循环优化技术。这导致了优化失败的可能性，以及这些优化方案在不同编译器之间的低可移植性。我们认为需要在这项工作中，我们提出了专用优化的新策略，允许与大多数现有编译器的实现方式不同，我们将高级优化策略与低级优化和实现最佳性能所需的专业化分离作为一种高级优化方案通过"拆分切片"，我们将演示如何将专用优化集成到通用的源到源C到CUDA转换器中，这种方法允许我们重用现有的非专用优化。然后，我们介绍了我们的技术，称为"为了结束我们关于"环形倾斜"的工作，我们研究了"金刚石倾斜"和"六边形倾斜"之间的关系。基于V在通用优化器（如"Pluto"）中使用二维（时间、空间）的问题。最后，我们使用这个公式来评估在本工作的第二部分中，我们将讨论我们对我们首先介绍新的pet一般使用Presburger算术来扩展支持的C代码片段，并特别注意即使在整数容量溢出的情况下，也可以对语言的语义建模。在下一步中，我们将介绍一种新的多面体代码生成方法，它通过允许生成用户提供的表达式，将代码生成扩展到传统的控制流生成之外。通过详细的选项机制为了简化多面体变换的实现，我们提出了一种新的表示形式，即"调度树"，它显式地表示多面体调度中本书的最后一部分介绍了我们对低级编译器的贡献。L’objectifprincipal de cette partie est notre六A B S T R A CT尽管对高级循环优化及其在生产C/C++/FORTRAN编译器中的成功集成进行了数十年的研究，但大多数编译器内部循环转换系统只能通过解决当今硬件日益复杂和多样性所带来的挑战。特别是当利用域特定知识来获得诸如加速器或多核处理器之类的复杂目标的最佳代码时，许多现有的循环优化框架在利用这种硬件时具有困难。因此，在不利用现有环路优化技术的情况下，独立地开发了新的域特定优化方案。这两者都导致错过了优化机会，并且这些优化方案对不同编译器的可移植性很低我们认为需要更好优化的一个领域是迭代模板计算，这是一个重要的计算问题，通常由专门的域特定编译器进行优化，但生成高效的代码是困难的。在这项工作中，我们提出了新的领域特定优化策略，使生成高性能GPU代码的模板计算。与大多数现有的域特定编译器的实现方式不同，我们将高级别优化策略与低级别优化和专业化分离，以获得最佳性能。作为一个高层次优化方案，我们提出了一个新的公式分裂切片，一个切片技术，肯定会重复使用沿时间维度以及平衡粗糙颗粒平行，而不需要冗余计算。使用Split Tilling，我们展示了如何将域特定优化集成到通用C-to-CUDA转换器中，这种方法允许我们重用现有的非域特定优化。然后，我们将拆分成一个混合的六边形/并行图倾斜方案，使我们能够生成更好地解决GPU特定问题的代码。在结束我们的工作时，我们研究了金刚石和六边形之间的关系。从对菱形倾斜的详细分析开始，包括它对瓦片尺寸和波阵面系数的要求，我们提供了六边形和菱形倾斜的统一公式，使我们能够在冥王星这样的通用优化器的背景下，针对二维问题（一次，一次空间）执行六边形倾斜。最后，我们使用该公式根据计算机与通信和计算机与同步比率来评估六方和菱形倾斜。在本工作的第二部分中，我们讨论了我们对重要基础设施组件的贡献，即我们的构建块，这些组件七使我们能够将我们的高级优化与必要的代码生成优化以及我们将优化应用于的编译器基础结构分开。我们首先介绍了一个新的多面体提取器，它从一段C代码中获取多面体表示，将支持的C代码扩展到可利用的范围。 Presburger算术的完全通用性和特别注意 即使存在有限的teger包装，也无法对语言语义进行建模。作为下一步，我们提出了一种新的多面体AST生成方法，通过允许生成用户提供的映射，将AST通过提供细粒度的选项机制，我们为用户提供了对AST生成器决策的细粒度控制，并增加了对专业化的广泛支持，例如，一种新的广义形式的多面体展开。为了促进多面体变换的实现，我们提出了一种新的时间表表示形式--时间表树，它提出了使时间表的固有树结构显式化的建议，以简化复杂多面体时间表的工作。本工作的最后一部分考察了我们对低级编译器的贡献。本部分的主要重点是我们在优化定义化方面的工作，这是一种为多变量多项式表达式导出多维AR视图的方法，通常通过将数据建模为参数大小的多维数组的代码来生成多维AR视图。八P U B L I C AT I ON S以下是我在攻读博士学位期间撰写或贡献的出版物列表。一些作品的思想、图形、列表和文本已被纳入本文。在[8，3]中发表的工作主要是在我的文凭学位的背景下进行的，并由于与本工作的部分相关而被列出。[4]已提交审查，但尚未发表。我们在AST生成章节中引用的一份新技术报告仍需发表。[1] 托拜厄斯·格罗瑟，阿尔伯特·科恩，贾斯汀·霍尔温斯基，P。Sadayappan和Sven Verdoolaege。GPU的混合六边形/经典倾斜。2014年在美国佛罗里达州奥兰多举行的代码生成和优化（CGO）国际研讨会上。[2] 托拜厄斯·格罗瑟、阿尔伯特·科恩、保罗·H·J·凯利、J·拉马努金、P·萨达亚潘和斯文·韦尔杜莱格。GPU的分割分块：使用梯形分块的自动平行化。在第6次工作坊中，关于使用图形处理单元（GPGPU）的通用处理器，第24ACM，2013年。[3] 托拜厄斯·格罗瑟（Tobias Grosser）、阿明·格罗斯林格（Armin Größlinger）和克里斯蒂安·伦戈尔（Christian Lengauer）。波莉- 在低级并行处理信函（PPL），22（04），2012年。[4] 托 拜 厄 斯 · 格 罗 瑟 、 斯 文 · 维 尔 杜 莱 格 和 阿 尔 伯 特 · 科 恩 。Polyhedra最后一代不仅仅是扫描Polyhedra。ACM编程语言和系统学报（TOPLAS）。（已提交审阅）。[5] 托 拜 厄 斯 · 格 罗 瑟 、 斯 文 · 维 尔 杜 莱 格 、 阿 尔 伯 特 · 科 恩 和P.Sadayap pan。金刚石和六边形之间的关系。第一届高性能模板计算国际研讨会（HiStencils）[6] 托 拜 厄 斯 · 格 罗 瑟 、 斯 文 · 维 尔 杜 莱 格 、 阿 尔 伯 特 · 科 恩 和P.Sadayap pan。GPU混合六边形/经典倾斜的前景。研究报告RR-8339，INRIA，2013年7月。[7] 托拜厄斯·格罗瑟、斯文·维尔杜莱格和萨达亚潘·P。科恩，艾尔-伯特。金刚石和六边形之间的关系。并行处理信函（PPL），2014年3月24日。[8] 托 拜 厄 斯 · 格 罗 瑟 （ Tobias Grosser ） 、 郑 洪 斌 （ HongbinZheng）、拉盖什·阿洛尔（Ragesh Aloor）、安德烈亚斯·西姆-伯 格 （ Andreas Sim- bürger ） 、 阿 明 · 格 罗 斯 林 格 （ ArminGrößlinger）和路易斯-诺埃尔·普切特（Louis-Noël Pouchet）。波莉九LLVM中的多面体优化。在C.别名和C。Bastoul，编辑，第一届多面体编译技术国际研讨会（IMPACT），法国夏蒙尼，2011年[9] 凯文·斯托克、马丁·孔、托拜厄斯·格罗瑟、路易斯-诺埃尔·普切特、法布里斯·拉斯特洛、J·拉马努金和P·萨达亚潘。通过关联重新排序增强数据重用的框架工作。在编程语言设计和实现会议（PLDI）上，2014年[10] 斯文·维尔杜莱热和托拜厄斯·格罗瑟。多面体提取工具。第二届多面体编译技术国际研讨会（IMPACT），法国巴黎，2012年1月。[11] 斯文·维尔杜莱格、塞尔日·圭尔顿、托拜厄斯·格罗瑟和阿尔伯特·科恩。计划树。在Sanjay Rajopadhye和Sven Ver- doolaege，编辑，第四届多面体编译技术国际研讨会（IMPACT），维也纳，奥地利，2014年1月。xA C K N O W L E D G M E NT S在我攻读博士学位期间，许多同事、朋友和家人都支持我，但在我攻读博士学位的几年里，他们也支持我。这些影响在塑造这部作品和塑造我个人方面都很重要。我想向所有和我一起走过这条路的人表达我深深的感激之情，那些我会亲自说出名字的人，但特别是那些我不可避免地忘记说出名字的人。首先，也是最重要的一点，我想感谢你，阿尔伯特，斯文和萨迪，是你引导我度过了这三年的博士研究。我还记得在一家加拿大酒吧里你告诉我我应该给你写封电子邮件以防万一我想和你一起做博士研究的那一刻。从那一刻起，在我真正开始的几年前，你们一直非常支持我，让我自由地选择我想遵循的方向，但仍然在我需要指导或帮助的任何时候支持我。Sven和你一起工作很有经验我不得不承认，很难阅读你的第一封电子邮件，你总是非常直接和开放的反馈，但我很快就了解到你的深入反馈是多么有价值，现在真的很享受与你的工作和讨论。萨迪，谢谢你的监督和支持，无论是在我在俄亥俄州的时间，但特别是在许多电话和访问巴黎在过去三年。你不仅帮助我确定了我的研究方向，而且还以许多其他方式提供了有益的建议。我想向帕绍和卢波团队表示衷心的感谢，特别是马丁·格里布尔、克里斯蒂安·伦戈尔、阿明·格罗斯林格和安德烈亚斯·辛布尔格，以及德克·拜尔和斯文·阿佩尔。所有这些都支持我从第一年的研究。在我的博士学位期间，我认识了许多有趣的再研究者。我想特别感谢路易斯-诺埃尔·普切特，我在俄亥俄州与他共事过，乌代·邦杜古拉，我拜访过他。在班加罗尔和拉姆（Ramanujam），我也经常见到在许多不同的地方。我要感谢Aart Bik、Beate List和Stephen Hines，感谢他们的支持和我在Google的美好时光。在我的谷歌博士奖学金的背景下，Anton Lokmotov在ARM度过了一段美好的时光，就像SebastianPop一样，自从我在AMD的第一次实习以来，我就经常与他互动。Parkas 团 队 ， 包 括 Mark ， Francesco ， Louis ， Tim ， Jean ，Boubacar，Serge，Michael，Jun，Antoine，Feng，Guillaume，Riyadh，Adrien，Nhat，Robin，Cédric和Chandan，进行了许多有趣的讨论，很好的咖啡休息，以及联合旅行。Assia和Joelle以及所有其他行政人员，他们在支持方面做得很好十一我的旅行和会议组织。我还要感谢Arnaud、Sylvestre和Duncan在组织LLVM会议和我们定期的巴黎社交活动时度过的美好时光。就像LLVM和Polly开源社区有很多非常好的人一样，开始给他们命名不可避免地会让我忘记一些重要的人。最后，有我的论文评审员玛丽·霍尔和弗朗茨·弗兰凯蒂，以及我的论文委员会与斯特夫·格拉亚特和让-吕克·拉莫特，我想对他们的努力和评论表示感谢。我也有很多好朋友的支持，包括Yulia，她帮我办理了入住手续，Amalia，她帮我办理了英语和室友的手续，Mathieu，Gælle，Caro和Kristin，他们支持我疯狂的工作时间，总是为我准备美味的食物。我还要感谢我的父母和兄弟姐妹，罗尔夫、沃尔特劳德、坦尼娅和迈克尔，他们在很多方面都被我忽视了，就像我身边的女人卡西亚一样，我把他们放在了我学习的开始，他们有无限的耐心支持我写这篇论文。十二C O N T E N T S图17列表表十八列表列表xviii首字母缩写列表xixi1号对流1第三章第三章1.1大纲6iiBACKGROU第9区2POLYHEDRALCOMPILATION112.1数学基础112.1.1整数集112.1.2整数映射132.1.3命名的联合集/命名的联合映射。152.1.4整数集/映射的2.2建模和转换势在必行的计划2.2.1说明性实施例162.2.2可以模拟哪些程序？............................................192.2.3多面体表示192.2.4转型20iii这是一个新的操作定时器NS foR sTE ncI ls253第27章第一次见面3.1什么是模板计算？............................................................ 273.2模板计算的倾斜3.3相关工作323.4我们在模板计算方面的工作354第37章第一次见面4.1概述374.2预处理394.3分割倾斜时间表404.3.1核心算法404.3.2瓷砖形状简化424.3.3多语句循环嵌套424.4CUDA代码第44代4.4.1共享内存使用情况454.4.2指令级平行性464.4.3完全/部分瓷砖分隔464.5摘要465混合动力车他x老 nA l/pARA llE loGRAMTI lI nG495.1概述49十三xiv与TE NTS5. 混合六边形/平行线时间表。525. 2. 1 六边形瓷砖. . . . . . . . . . . . . . ...525. 2. 2 平行线图块时间表。 . . . . ...575. 2. 3个图块内时间表。 . . . . . . . . . . . . ...575. 2. 4 混合瓷砖。 . . . . . . . . . . . . . . . ...585. 2. 5 瓷砖尺寸选择。 . . . . . . . . . . . . . ...595. 3CUDA代码生成。 . . . . . . . . . . . . . ...595. 3. 1 生成CUDA代码 . . . . . . . . . . ...595. 3. 2 共享内存。 . . . . . . . . . . . . . . ...605. 3. 3 交错计算和复制。615. 3. 4模板特定代码生成启发式。615. 4摘要。 . . . . . . . . . . . . . . . . . . . . . . ...636你的钻石和你的钻石. . . . . . . ...656. 1菱形倾斜 . . . . . . . . . . . . . . . . . . . ...666. 1.冥王星优化器 . . . . . . . . . . . . ...666. 1.第二章钻石倾斜延伸 . . . . . . ...686. 1. 图块大小与波阵面之间的686. 1. 4 具有默认波阵面的最佳切片。 . . ...736. 2统一菱形和六边形倾斜。 . . . . ...746.最大化计算/通信的3种磁贴尺寸776. 4摘要。 . . . . . . . . . . . . . . . . . . . . . . ...827EXPERIME NTA LRE SU LTS. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...837. 1分幅 . . . . . . . . . . . . . . . . . . . . . . ...837. 2混合六边形 . . . . . . . . . . . . . . . . . ...837. 2. 1 与最先进的工具进行比较。...837. 2. 2 混合tiling和共享内存。 . . . ...877. 3摘要。 . . . . . . . . . . . . . . . . . . . . . . ...89iv.POLYHEDRALBUILDINGBLOCKS. ... ... ...... ... ... ... ... ... ... ...918国家石油公司EPT.... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...939POLYHEDRALXTRACTOR. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...979. 1概述。 . . . . . . . . . . . . . . . . . . . . . . ...999. 2构造多面体表示。 . . . ...1009. 2. 1 访问关系。 . . . . . . . . . . . . . . ...1019. 2. 2 条件。 . . . . . . . . . . . . . . . . . ...1029. 2. 3个 循环。 . . . . . . . . . . . . . . . . . . . . ...1029. 2. 4 时间表。 . . . . . . . . . . . . . . . . . . ...1039. 3附加功能。 . . . . . . . . . . . . . . . . ...1039. 3. 1 CLOOG规格功能 . . . . . . . . . . ...1049. 3. 2 支持无符号积分器. . . . . . ...1049. 4相关工作。 . . . . . . . . . . . . . . . . . . . ...1069. 5限制和未来的工作 . . . . . . . . . . . ...1099. 6总结。 . . . . . . . . . . . . . . . . . . . . . . ...10910 STGNE比率 N. . . . . . . . . . . . . . . . . . . . ... 11110. 1AST生成的新方法。 . . . . . . ...11310. 2输入 . . . . . . . . . . . . . . . . . . . . . . . . . ...117第十五章10.3 抽象语法树11810.4 新一代AST功能11810.4.1细粒度期权机制11910.4.2隔离12110.4.3多面体展开12210.4.4部分解除滚动12510.4.5生成AST表达式12710.5 实验结果12810.5.1存在量化变量12810.5.2AST生成策略的性能13210.5.3世代时间13310.6 相关作品13410.7 摘要13511 SCHEDU LE树 S13711.1 计划使用13911.1.1第139号原始执行11.1.2转换14011.1.3AST第141代11.2 时间表表示14111.2.1属性14211.2.2比较14311.3 日历树表示14711.3.1节点14711.3.2操作14911.4 混合六边形-平行四边形瓷砖15111.5 摘要153V低-LEVE L COM PI LER S...........................................15512 ConTRIBUTIOnsTOlvM/pollY15712.1 计算15712.2 AST第157代12.3 GPolly -加载的自动GPU12.4 代表平行性15913 第161章：第一次见面13.1 激励示例16313.2 问题陈述16413.3 单参数大小的数组视图13.3.1多个数组引用16913.3.2子脚本表达式中的数组大小13.3.3大小为A[*][β1P1][β2P2]的数组13.4 大小为"参数+常数"的数组...................................................13.5 执行情况17913.6 实验评价18013.7 相关工作18113.8 摘要182xvi与TE NTSvi第185章第一次见面14 第187章第一次见面14.1 个人贡献18714.2 未来的工作188viiA页ENDI X191BBBlIOGRApHY193L I S T O F I G U R E S1二维整数集（密集）122二维整数集（稀疏）133二维整数映射144迭代空间5迭代空间6运行模板后的热分布见列表1287数据-列表1中模板的流动2881个D空间模板的迭代空间91个D空间模板的矩形瓷砖30101D空间模板的迭代空间3111简单示例中的拆分切片（切片大小8×3）。3812分裂标题jacobi-2d内核4313两个声明内核44141-D六角切片-由1-D分割切片创建15雅可比2D模板5116生成的PTZ（CUDA字节码）5117相反的依赖锥5318六边形瓷砖5319六边形瓷砖图案5520n维图块时间表（±1个距离）5821对称相关性平方倾斜（原始/变换）6922对称依赖关系非平方分块（原始/变换）6923不对称依赖方倾斜（原始/转换）7124多个时间步骤。方形瓷砖可减少瘫痪。（原始/转换）7125多个时间步骤。非正方形分笔成交点最大化（原文/翻译）7226钻石瓷砖（原始/转换）7227六边形倾斜（原始/转换）7228变形空间中的拉伸（未拉伸/拉伸）76291D六边形瓷砖（T=6，B=4）78301D六边形倾斜的第一个两步（T=6，B=4）7931计算与读取比率-六边形与钻石瓷砖8032计算与同步比率-六边形与钻石瓷砖8133分块性能（桌面GPU）8434分割分块性能（移动GPU）8435从混合六边形/平行四边形倾斜（单圈）复制代码114十七36混合六边形/平行四边形倾斜的复制代码（未滚动）11637程序示例11738不带代码生成选项的交错计划11939具有代码生成选项的交错计划12140模条件（ClooG不支持的示例）12941存在性量化变量（ClooG/codegen+不支持的示例）13042示例时间表树表示13843图42146中计划的森林带表示44保险丝带B1和B215045根据过滤器F1和F2将活动语句实例排序到B15046混合动力牵引车的输入模式47混合动力牵引152的输出模式48常量大小16149参数大小为162的50不同参数值的子列访问168L I T O F TA B L E S1NVIDIA GTX470的性能：GStencils/秒&加速852NVS5200上的性能：GStencils/秒加速853模板的特征864优化步骤：GFLOPS Speedup885个绩效计数器（10个单位，9个事件）896不同多面体萃取器的特性108基于性能的AST生成策略（GFLOPS）1328比较一些通用时间表表示144我是T O F L我是I N G S1实现5点、2个D空间、James风格的热模板272拆分标题代码393一个简单的程序100十八4托马斯测试用例104的ClooG输出部分5循环绑定中的无符号操作1056列表5中的程序合并无效1057使用无符号迭代器105的8平凡的展开示例1239123在紧张的存在下展开10绑定情况下的解卷，非常量迭代数12411以两个较低的边界解锁12512部分展开-原始循环巢12513部分解锁-Tiled12614部分解锁-已滚动+未滚动12615部分解卷-分层+解卷+隔离核心计算16使用LLVM元数据159标记为并行的单循环17使用LLVM元数据159并行标记嵌套循环18使用可变长度数组用C99编写的gem内核19使用手动实现的多维数组编写的gem内核16420子脚本中使用的阵列尺寸16921用C++编写的gem内核使用boosts：：ublas18022用Julia180编写的宝石内核L I S T O F A C R O N Y M SAST抽象语法树ClooGChunky循环生成器clangLLVM C/C++编译器CPU 中央处理单元NVIDIA的CUDADSL域特定语言DRAM动态随机存取存储器FPGA现场可编程Gate阵列gccgnu编译器集合GPU图形处理单元图形处理单元上的GPGPU十九xxACROnYM sILP整数线性规划IP知识产权IR中间表示isl整数集库LLVMLLVM编译器基础结构LLVM-IRLLVM中间表示OpenCL开放计算语言ICMP开放式多处理PPCG Polyhedral并行代码生成器PTZ并行线程执行（NVIDIA IR）SCC强连接组件SCEV 尺度演化SCoP静态控制部分/程序SIMD单指令多数据APU 流处理单元