改进平铺、减少编译时间并扩展多面体编译的范围

改进平铺、减少编译时间并扩展多面体编译的范围Mohamed Riyadh Baghdadi引用此版本：穆罕默德·利雅得·巴格达迪。改进平铺，减少编译时间，并扩展多面体编译的范围。编程语言[cs.PL].皮埃尔和玛丽·居里大学-巴黎第六大学，2015年。英语NNT：2015PA066368。电话：01270558HAL Id：tel-01270558https://theses.hal.science/tel-012705582016年2月8日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire皮埃尔和玛丽·居里大学博士论文集巴黎信息、电信和电子博士学校改进分块、缩短编译时间并扩展多面体编译由Albert COHEN和Sven VERDOOLAEGE编写2015年9月25日陪审团组成如下：报告员M.塞德里克·巴斯托M.保罗·凯利斯特拉斯堡大学教授伦敦帝国理工学院教授考官M.斯特夫·格拉亚特M.塞德里克·巴斯托M.保罗·凯利M. J. RamanujamM.阿尔伯特·科恩M. Sven Verdoolaege皮埃尔和玛丽·居里大学（巴黎第六大学）教授斯特拉斯堡伦敦帝国理工学院教授，路易斯安那州立大学教授，法国Polly Labs和KU Leuven内容图七表九名词Xi1导言和背景11.1导言。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.2背景和注释 . . . . . . . . . . . . . . . . . . . . . . . . . . .51.2.1地图和集合 . . . . . . . . . . . . . . . . . . . . . . . . . . . .51.2.2附加定义 . . . . . . . . . . . . . . . . . . . . . . . . .71.2.3程序的多面体表示 . . . . . . . . . . . . . . . .81.2.4数据位置131.2.5循环变换141.3概述152基于内存依赖的平铺代码2.1导言和相关工作192.2虚假依赖的来源212.3示例232.4实时范围无干扰242.4.1实弹射击场242.4.2实弹射击场的建造2.4.3有效范围无干扰262.4.4现场范围不干扰和平铺：一个宽松的可置换性标准272.4.5示例292.4.6Chelelism312.53AC对环路可倾性的影响322.6实验评价342.7实验结果362.7.1评估忽略错误依赖对平铺382.7.2Polybench-3AC43的性能评价2.7.3减速的原因2.7.4Polybench-PRE45的性能评价2.8结论和今后的工作3安排大型程序493.1导言.493.2定义513.3语句聚类示例513.4聚类算法533.5使用离线聚类与冥王星仿射调度算法543.5.1聚类后循环变换的正确性563.6聚类启发式563.6.1聚类决策有效性563.6.2SCC群集573.6.3基本块聚类593.7实验603.8相关工作653.9结论和今后的工作4PENCIL语言694.1导言.694.2PENCIL语言704.2.1PENCIL70概述4.2.2作为C99子集的ENCIL定义734.2.3PENCIL扩展到C99774.3详细描述774.3.1stati， onstand restri t774.3.2函数78的存储器访问的描述4.3.3onst函数属性834.3.4Pragma指令834.3.5内置功能884.4PENCIL和非PENCIL代码934.4.1BFS实施例934.4.2图像大小调整示例954.4.3递归数据结构和递归函数调用4.5PENCIL代码97的多面体编译4.6相关工作1005评价PENCIL1035.1导言. 1035.2基准1055.2.1图像处理基准套件1055.2.2Rodinia和SHOC基准套房1095.2.3VOBLA DSL线性代数1105.2.4用于数据流应用的SpearDE DSL1145.3讨论结果1145.4结论和今后的工作6结论与展望1176.1捐款1176.2未来的方向118参考书目121A PENCIL131的EBNF语法B个人出版物135索引136图目录1.1集合的图形表示 . . . . . . . . . . . . . . . . . . . . . . . .61.2地图的图形表示。 . . . . . . . . . . . . . . . . . . . . . .71.3内核的例子 。..............................91.4S1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.1具有防止平铺的假依赖关系的代码202.2Gemm内核222.3应用PRE22后的Gemm2.4三个嵌套循环，循环不变码222.5循环不变代码运动后的三个嵌套循环222.6gemm内核24的平铺版本2.7来自mvt内核的一个循环252.8{S1→S2}和{S3→S4}不干扰的示例262.9{S1→S2}和{S3→S4}干扰的示例262.10 说明邻接概念的示例272.11 t和x1[i]的有效范围（mvt30）2.12 不可能平铺的示例312.13 图2.12中示例的有效范围2.14 比较为支持并行化、平铺或两者而创建的标量和数组的私有副本数量322.15 原始gesummv内核352.16 gesummvin 3AC form352.17 原始gemm内核352.18 应用PRE35后的gem2.19 2 mm-3AC（3AC形式的2 mm）362.20 2 mm-3AC36的扩展版本2.21 应用PRE36后的gesummv2.22 3AC变换对平铺的影响38VIII图目录2.23针对Polybench-3AC的非平铺顺序代码的加速。 . . . . . .392.242 mm-3AC优化，同时忽略错误依赖性。 . . . . . . . . . .402.25优化2 mm-3AC的扩展版本。 . . . . . . . . . . . . . . . .412.26针对Polybench-PRE的非平铺顺序代码的加速。 . . . . . .422.27trmm扩展版本中的最内在并行性。 . . . . . . . . . . . .463.1语句聚类的说明性示例。 . . . . . . . . . . . . . . . . .513.2原始程序依赖图 . . . . . . . . . . . . . . . . . . . . . .523.3聚类后的依赖图 . . . . . . . . . . . . . . . . . . . . . . .523.4流依赖图。 . . . . . . . . . . . . . . . . . . . . . . . . . . . .573.5基本块聚类的说明性示例。 . . . . . . . . . . . . . . . .593.6应用语句聚类后，调度时间得到了加速。 . .633.7启用集群时的执行时间标准化为未启用集群时的执行时间（越低意味着越快）。. . . . . . . . . . . . .654.1我们对使用PENCIL的愿景的高层次概述。 . . . . . . . . . .724.2一般2D卷积。 . . . . . . . . . . . . . . . . . . . . . . . . . . . .914.3代码提取自Dilate（图像处理）。 . . . . . . . . . . . . . . .994.4包含break语句的代码示例。 . . . . . . . . . . . . . . . .99A.1PENCIL语法作为EBNF。. . . . . . . . . . . . . . . . . . . . . . . . . .131A.1作为EBNF的PENCIL语法在后页继续。 . . . . . . . . . . . . . . . .132A.1作为EBNF的PENCIL语法在后页继续。 . . . . . . . . . . . . . . . .133表的列表2.1一个表格显示了哪些3AC内核被平铺372.2一个表格显示了哪些PRE内核被平铺373.1应用语句聚类后语句和依赖项数量减少的因素625.1关于图像处理基准106中的非静态仿射码的模式的统计5.2启用对单个PENCIL特性的支持对生成代码的能力和加速增益的影响1065.3PPCG在OpenCV107上生成的OpenCL代码的加速5.4Rodinia和SHOC1095.5PENCIL对SHOC和Rodinia基准测试有用的功能1095.6PPCG为所选Rodinia生成的OpenCL代码的加速和SHOC基准1105.7在启用对假设内建的在VOBLA1135.8通过高度优化的BLAS库使用PPCG获得的加速113命名法罗马符号3AC三地址码ABF自适应波束形成器的api应用程序接口AST抽象语法树BFS广度优先搜索C11C标准2011C99C标准1999CUDA计算统一设备架构DSL领域特定语言EBNF扩展巴科斯-诺尔形式GCCGNU编译器集合GFLOPS每秒千兆浮点运算GPU图形处理单元HMPP混合多核并行程序设计ISLSet LibraryOpenACC开放加速器OpenCL开放计算语言XII命名法OpenMP开放式多处理宠物多面体提取工具PGI波特兰集团PPCG多面体并行代码生成器预部分冗余消除PTX并行线程执行Sese单入口单出口SHOC可扩展异构计算SSA静态单一赋值VOBLA优化基本线性代数的载体第1导言和背景1.1介绍在从科学计算到游戏和嵌入式系统的许多应用中，对计算能力的需求不断增加这导致硬件制造商设计具有增加的并行度和更复杂的存储器体系结构的体系结构例如，最近的图形卡，如Nvidia GeForce GTX Titan Z，在双精度下具有2707 GFLOPS（每秒千兆浮点运算）的理论峰值性能，这样的图形卡在性能上高于2000年6月的TOP500列表中列出的最强大的超级计算机[71]，其峰值性能为2707 GFLOPS（每秒千兆浮点运算）。2379 GFLOPS，性能比列出的最强大的超级计算机高4倍在1997年6月的TOP500名单上[33]。随着并行度的增加和复杂的存储器层次结构，编写和调试并行程序变得越来越具有挑战性。首先，因为考虑并行线程的执行是不直观的，这使得编写并行程序的过程变得困难并且容易出错。其次，获得良好的性能并不容易，特别是在为具有复杂内存层次结构和严格资源限制的体系结构编写程序第三，可移植性的问题：为特定架构编写和优化的并行程序，通常不能在不修改的情况下利用另一个架构的特性（应为每个目标架构提供程序的不同实现）。这些问题使得并行编程和代码维护在时间和资源上非常昂贵。这些问题的新兴解决方案是使用高级编程语言和使用编译器来有效地将它们编译成并行和高度优化的低级代码。使用高级语言有很多好处。首先，这种语言易于使用，更直观。其次，并行代码是由2导言和背景优化编译器，减少生成的并行代码中的错误数量。第三，高级语言通常是独立于体系结构的，因此它不会受到可移植性问题的困扰。将繁琐的、低级的和特定于体系结构的优化留给编译器，使程序员能够专注于更高级别的优化，从而降低开发成本、缩短上市时间并更好地优化代码。已经提出了许多方法来解决将高级代码降低（编译）为并行且高度优化的低级代码的问题。大多数现有的方法集中在循环（循环嵌套）的优化，因为这些通常是程序中最耗时的部分。这一领域的早期工作集中在数据依赖分析问题上[15，98]，随后引入了许多旨在提高程序性能的循环变换，这些变换的示例包括循环阻塞（也称为平铺），它增强了数据局部性[12，87，108]，向量化，将标量操作转换为向量操作[1，2]，以及自动并行化[16，32，34]。虽然经典的循环转换一般都很好理解，但设计一个允许有效应用大量循环转换的模型并不是一件容易的事情。找到应该应用的正确的转换序列甚至更具挑战性。为了解决这些问题，研究人员已经研究了使用更具表现力的模型的可能性以及使用单个统一的循环变换框架导出经典循环变换的组合的可能性。作为这项研究的结果，多面体框架演变[37，38]。多面体框架是一个代数程序表示和一组分析，转换和代码生成算法，主要致力于循环嵌套的优化和自动并行化。 它使 一个编译器，用于推理高级优化和程序转换，以解决统一循环转换框架中的并行性和局部性增强挑战多面体框架主要依赖于静态分析，尽管正在努力为多面体模型增加对动态分析的支持[5，53，93]。静态分析是在编译时提取关于程序的语义信息的过程，而动态（或运行时）分析在运行时提取信息静态分析的一个经典例子是决定两个指针是否可以别名：如果存在从程序入口到程序点的路径P，则名称a和b可以在程序点处彼此别名，使得a和b在沿着路径P执行后引用相同的位置。在多面体编译中，首先从程序中提取一个抽象的数学表示，然后基于该表示计算数据依赖。可以应用满足这些依赖性的循环变换，并且最后从变换后的多面体表示生成代码。在过去两年中取得了重大进展1.1引言3对于（inti=1;in; i++）S：A[i n=0;<在多面体模型中，依赖分析[36，82]，自动循环转换[40，64，65]和代码生成[11，54最新进展的例子包括用于共享存储器[18]、分布式存储器[17]和复杂架构（如GPGPU（通用图形处理单元）[10，104]）的自动循环转换和代码生成。在多面体框架的优点中：• 它允许精确的数据相关性分析和细粒度调度，即，改变语句的一个或几个执行实例的执行顺序的能力。以下循环嵌套中语句S（标记为S的语句）的执行实例或迭代是在循环的一次迭代中执行语句循环的每次迭代执行语句的一个实例。• 多面体框架提供了一个统一的框架，在这个框架中，可以对大量的转换进行建模，并且编译器可以在这个框架中推理复杂的循环转换。• 程序在多面体模型中的代数表示捕获了程序的语义。循环变换对这种表示进行操作，而不是对程序的语法（代码）进行操作，因此循环变换是鲁棒的，并且将以相同的方式对具有相同语义但编写方式不同的程序进行操作。在多面体框架的局限性中：• 所有静态分析框架的共同局限性– 静态分析框架不能准确地对具有动态控制的程序例如，if（A[i]）这样的条件不能准确地表示，并且不能在编译时分析，因为A[i]的值仅在运行时。为了克服这个限制，开发了许多对经典多面体模型的扩展，其中一些扩展使用退出/控制预测和对迭代域（语句的执行实例集）的过度近似[14，41]，其他扩展将动态控制封装在宏语句中[102]。4导言和背景-（都大量使用指针）。这主要是因为有效的优化需要准确的依赖分析，这反过来又需要准确的别名分析，但别名分析在允许递归数据结构（多级指针间接）的语言中是不可判定的[58，86]，因此依赖分析在这种情况下不准确，这降低了自动优化和并行化的有效性。• 多面体框架特有的局限性– 多面体模型中的许多算法在计算上是昂贵的，因为它们依赖于使用整数线性规划（现有的算法来解决ILP问题在最坏情况下具有指数复杂度）。虽然多面体模型有一些弱点，但它在许多环境中显示出有希望的结果，并逐渐被纳入IBM XL [19]和R-Stream [70]等工业编译器中。 从多面体模型中充分受益的关键是在正确的上下文中使用它。在这篇论文中，我们考虑以下情况：我们不解决优化遗留代码的问题，我们假设优化的代码不使用指针，除了在极少数情况下，我们在第4章中提出。我们不使用多面体模型来优化操作图形、列表或树的代码，而是在主要操作数组的代码中使用它。在这篇论文中，我们的目标是扩大范围，其中多面体循环优化可以有效地使用。我们的工作的动机是在两种情况下使用多面体模型：• 在GCC编译器中使用多面体模型（GRAPHITE多面体框架[81，95]）：我们特别解决了在此上下文中应用平铺的经典技术问题（平铺是一种增强数据局部性的优化）。• 在DSL（领域特定语言）编译器中使用多面体框架：我们特别讨论了在这种情况下出现的两个经典限制（如上所述）。本文的工作就是针对这三个问题进行的尝试。这项工作往往是合作研究、开发和实验的结果。我们将在每个技术章节中感谢关键贡献者及其各自的角色。在1.2背景和注释5本章的其余部分，我们将介绍一些关键概念，然后我们将提供一个大纲的论文和一个高层次的概述，我们解决的三个问题1.2背景和注释现在让我们介绍基本概念和符号使用整个其余的文件。1.2.1映射和集合本论文中使用的集合和映射的符号是ISL（集合库）[101]使用的符号（这些符号也接近Omega项目[109]中使用的符号i.设置ISL中定义的整数集是来自Zd的整数元组的集合，可以使用Presburger公式[89]（稍后介绍）进行描述。d是集合的维数（每个元组中一个n元组在ISL中用[a1，a2，. . . ，an]。假设我们有一组对象β1，β2，. . . ，βn. 我们将此集合表示为：{β1; β2;. . . ; βn}。一组整数元组的一个例子{[1， 1];[ 2， 1];[ 3， 1];[ 1， 2];[ 2， 2];[ 3， 2]}不需要列出集合的所有整数元组，整数元组可以使用Presburger公式（稍后介绍）来描述。二维集合可以写成如下{S[i，j]：1≤i≤ 3< $1≤j≤ 2}i和j是集合的维数。一个集合的元组可以选择有一个公共名称：在示例中为S。图1.1显示了集合的图形表示。一般来说，整数集具有以下形式S={N[→s]|f（→s，→p）}其中→s表示整数集合（→s∈Zd）的整数元组，N是所有元组s→s的公共名称，d是s的维数，→p∈Ze是ep参数s的向量，f（→s， →p）是Presburger公式，当且仅当对于给定参数→p，→s是S的元素，该公式为真.6导言和背景图1.1集合Presburger公式我们使用EBNF（扩展巴科斯-诺尔形式）语法定义Presburger公式[106]。<式>←<公式>计算<公式>|公式<>计算<公式>| 联系<我们|var<>. <式>| var<>. <式>|原子<><原子>←<术语> relop>术语>←<数字>|术语<>+<术语> |− | 数字<术语>|联系<我们←< |≤|为|>> |≥<联系我们 ←X|y |z|. . .<数字>←0|1 |2|. . .term<>不是一个通用的乘法运算符;它是+的快捷方式···+<术语>。使用Presburger算法（其中使用Presburger公式）主要是因为它是一种可判定的算法。 也就是说，存在一种算法，该算法决定任意Presburger公式是否正确（有效）。 最著名的复杂度上界这样一个算法的时间复杂度是O（222pn），其中p是一个正常数，n是公式[80]的长度。分子式的长度是它的原子数原子是一种形式（t1t2），（t1≤t2），（t1=t2），（t1>t2）或（t1≥t2）之一，其中t1和t2是项。<在集合上操作。可 以 在集合上进行的操作的示例包括检查集合是否为空，计算两个集合的并集和交集，以及检查两个集合是否相等。1.2背景和注释7ii.地图映射是两个集合之间的关系。例如M={S1[i，j] → S1[i+ 2，j+ 2]：1≤i≤ 3< $1≤j≤ 2}表示两个集合之间的关系，第一个称为域或源，第二个称为范围或汇。图1.2显示了地图M的图形表示。图1.2地图的图形表示通常，地图具有以下形式M={A[→s]→B[→o]，（→s，→o）∈Zd1×Zd2|f（→s，→o，→p）}其中A[→s]表示域或源，B[→o]表示范围或汇。d1和d2是→s和→o的维数s，→p∈Ze是e参数s的向量，f（→s，→o，→p）是一个Presburger公式，当且仅当对于给定的参数→p，M中存在从→s到→o的关系.在映射和集合上的操作中，存在将映射应用于集合的操作。 映射map1对集合set1的应用被写为map1（set1）。 函数调用Sour e（map1）和Sink（map1）分别返回mapmap1的source和sink。1.2.2另外的定义字典序迭代向量[i1，. . . ，i k，. . . ，i n]在另一迭代向量之前[i′，. . . ，i′，. . . ，i′]的充要条件是n ∈ N使得i1= i′n···n

下载后可阅读完整内容，剩余1页未读，立即下载