将多面体技术扩展到平行规范和近似亚历山大·伊索阿尔引用此版本：亚历山大·伊索德。将多面体技术扩展到平行规范和近似。其他[cs.OH]。里昂大学，2016年。英语。NNT：2016年LYSEN011。电话：01369014HAL ID：电话：01369014https://theses.hal.science/tel-01369014提交日期：2016年HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire国家博士论文编号：2016LYSEN011里昂大学博士论文（法语）操作者l’École Normale Supérieure de博士学校512号里昂计算机科学与数学博士学院学科：计算机科学于2016年7月5日公开支持，作者：亚历山大·伊索尔德将多面体技术扩展到平行规范和近似将多面体技术扩展到并行规范和近似在陪审团面前，陪审团由：阿尔伯特J.（拉姆）塞缪尔COHEN报告员RAMANUJAM报告员B艾利斯考官弗朗西斯一世严格审查员UdayREDDY BONDHUGULA审查员AlainDARTE博士生导师谢谢你首先，我要热烈感谢阿兰·达特，他我将特别记住他的正直和他的科学严谨，这使他他的批评者提出了精确而决定性的论点，这些论点在无数场合激发了受欢迎的独创性。如果不是我们在黑板的角落里激烈地讨论，在我的笨拙和微妙的进步之间进行分类，我永远不可能进步得这么快。我相信然后，我要感谢我的报告员，更广泛地说，感谢我的评审团的所有成员：感谢阿尔伯特、拉姆、塞缪尔、弗朗索瓦和乌代同意前往那里，阅读和评判我的工作。我还要感谢Paul Feautrier，他在多面体世界中无与伦比的专业知识是我们不可替代的资源。同样，我与Tomofumi Yuki的讨论也提供了我没有忘记那些间接帮助我的人，但他们对这项工作也是必不可少的，他们是我的两个室友，弗朗索瓦·金德罗和克莱门特·拉吉斯奎特，他们的后勤帮助、膳食质量和共同讨论使我们在一起的几年成为一种享受; Maroua Maalej，我最喜欢的办公室同事，也是我的朋友，她总是在那里激励我，给我建议，让我品尝突尼斯的特色菜，无论是烹饪、语言还是精神; Laure Gonnord对一切都给予了不懈的支持，但最重要的是，与Nicolas Louvet一起，他对教学充满了想法。我还要感谢我们的超级助手，他们总是心情很好，总是提供很我非常喜欢与我在LIP和其他地方的许多同事进行科学互动。我特别想到了许多博士生和实习生，露西·马蒂内、纪尧姆·鲁斯、奥雷利安·卡维兰、奥古兹·卡亚、纪尧姆·奥皮、奥蕾莉·拉古特、朱利安·赫尔曼、贝特朗·西蒙、洛伊克·波蒂尔、扬尼克·利奥、罗曼二世iii.Labolle 。 ... ... 但 也 有 许 多 研 究 人 员 ， 蒂 埃 里 杜 蒙 ， 维 奥 莱 恩 卢 韦 ， 桑 杰Rajopadhye ， P.Sadayappan 、 Sven Verdoolaege 、 Tobias Grosser 、 Louis-NoëlPouchet、Béa- trice Creusillet、Ronan Keryell、Fabrice Rastello、Christophe别名。. .不幸的是，这些名单太长了，无法一一列举!当然，我还要感谢我的家人，他们一直在我身边，在我身边呆了很长一段时间;他们是最温暖的地方。最后，感谢Stephen Neuendor offer摘要在性能和能源双重目标的驱动下，当今的计算基础设施正在向日益复杂的体系结构发展，包括复杂的内存组织和硬件加速器的使用。它们要求本论文的动机是将计算内核自动转移到GPU或FPGA等加速器的实际问题，其主要目标也是在我们的第一个结果是分析（精确或近似）当内核一个图块一个图块地传输时，要复制到参数化图块加速器和从参数化图块加速器复制的数据集，可能是以流水线的方式，并利用图块之间的数据重用。我们的第二个结果是能够分配由这些数据移动引起的局部数组所必需的我们的第三个结果是，在这个分析的基础上，推广了基于格的数组（欧几里得格）的收缩，以前局限于一组冲突的凸元素，如果这个集合被描述为凸集合的联合，这是使用格时常见的我们将所有这些结果结合在一个建议中，利用GPU的不同内存和并行级别，为GPU自动生成代码。我们相信，我们的各种结果也有助于iv.目录导言（法文）1导言（英文）71背景和相关工作121.1处理器架构和计算121.1.1CPU131.1.2GPU161.2多面体技术191.2.1静态和安全控制部件（SCoP）201.2.2约束表示211.2.3SCoP 23的代表性1.2.4关系251.2.5依赖关系251.2.6循环变换271.2.7瓷砖（瓷砖）292参数化图块的图块间重用322.1动机332.2先决条件362.2.1符号和定义362.2.2图块之间的数据372.3未对齐瓷砖的管理402.3.1集合方程的精确方法412.3.2按点列出的功能452.3.3近似值的情况472.4结论523并行规范的寿命分析543.1动机543.1.1生命力、冲突和再利用553.1.2同时存活的583.2对某些特殊情况的593.2.1完全连续的订单603.2.2边界和平行回路的顺序64目录V目录VI3.3部分订单及以上673.3.1概括的必要性683.3.2痕迹与冲突693.3.3部分订单和冲突723.4与以前工作743.5结论754内存分配774.1动机774.2方法的直观演示4.3背景814.3.1所有冲突814.3.2模82的分配4.4贪婪的分配和网络834.4.1分配空间中的碱基选择4.4.2网络空间中的碱基选择4.4.3两种方法的组合944.5评估964.5.1反L区域和优化脚本964.5.2模糊过滤器（4.5.3钻石瓷砖994.5.4我们的分配与其他方法的比较4.6相关工作1014.6.1链接到4.6.2与Bhaskaracharya等人绘画之间的再利用联系.................................. 1024.6.3与通用占用向量（UOV）的链接4.7结论和今后的工作1055计算内核的转移1075.1动机1085.2管道和双缓冲器1105.3记忆冲突的推导1125.4本地存储器的大小和分配1175.5面向GPGPU123的代码生成5.5.1可交换回路带的选择1245.5.2考虑顺序性1255.5.3内核和CPU内存与GPU内存1275.5.4图块层次结构1285.5.5全局存储器和共享存储器之间的块1315.5.6共享内存和寄存器之间的线程1355.6第135章结论137参考书目140摘要在性能和功耗目标的指导下，当今的计算基础架构正在向复杂性不断增加的体系结构发展，包括复杂的内存组织和硬件加速器的使用。它们要求用户或编译器能够执行并行提取、局部优化和显式数据移动。本论文的动机是在GPU或FPGA等加速器上自动扩展计算内核的实际问题，其主要目标也是在解决参数、近似、并行性等问题所需的多个方向上扩展多面体技术（有利于处理环路和基于阵列的内核）。我们的第一个结果是分析（精确或近似）当内核一个块一个块地扩展（可能以流水线方式），并且块之间的数据重用被重用时，参数分层的数据复制进入和复制退出的必要性。我们的第二个结果，需要能够分配由数据移动引起的局部阵列，是将冲突阵列元素的概念和构造推广它可以捕获ICMP或X10等语言的并行结构。我们的第三个结果是，基于这个分析，将基于格的数组收缩（以前限制为冲突元素的凸集）推广到这个集被描述为凸集的联合的情况，这是使用倾斜时的常见情况。我们将所有这些结果结合起来，提出了一个利用GPU的不同内存级别和并行性为GPU自动生成代码的建议。我们相信我们的不同结果也有助于多面体技术的扩展，并行程序的分析，以及面向其他加速器（如FPGA）的编译。七内容物导言（法文）1简介（英文）71背景及相关工作121.1处理器体系结构和处理模型121.1.1CPU131.1.2GPU161.2多面体技术191.2.1静态控制第20部分1.2.2约束表示211.2.3SCoP代表231.2.4关系251.2.5依赖关系251.2.6循环变换271.2.7倾斜29度2用于参数倾斜的瓷砖间重复使用322.1动机332.2请求362.2.1符号和定义362.2.2磁贴间数据重用372.3处理未对齐的瓷砖402.3.1集合方程的精确方法412.3.2点式函数452.3.3近似值的情况472.4结论523并行规范上的生命力分析543.1动机543.1.1生命力、冲突和再利用553.1.2同时实时索引583.2特殊情况扩展593.2.1完全顺序计划60内容物3.2.2时间表和并行循环64八内容IX3.3部分订单及以后673.3.1概括的必要性3.3.2痕迹与冲突693.3.3冲突的局部顺序和结构723.4与以前工作的743.5结论754内存分配774.1动机774.2方法的直觉794.3背景814.3.1冲突集814.3.2模块化映射824.4贪婪映射和网格结构834.4.1制图空间中的基础选择834.4.2晶格空间88中的基选择4.4.3结合两种方法944.5评估964.5.1反向-L形区域和优化脚本4.5.2模糊过滤器984.5.3钻石倾斜994.5.4将我们的映射与其他工作进行994.6相关工作1014.6.1链接到多维调度和倾斜1014.6.2与Bhaskaracharya等人的链接，阵列内重用1024.6.3与通用占用向量的1044.7结论和未来工作1055内核卸载1075.1动机1085.2管道和双流量1105.3派生内存冲突1125.4本地存储器的大小和映射1175.5定位GPGPU1235.5.1可交换环形带的选择1245.5.2处理顺序1255.5.3内核和主机/设备内存传输1275.5.4倾斜层次结构1285.5.5块和全局/共享内存传输1315.5.6线程和共享/寄存器内存传输135内容物5.6第135章结论137参考书目140简介在我们的现代，计算机无处不在。它们在医学、物理学、数学、经济学以及摄影、电影、音乐甚至文学等不同领域都有应用它们始终承诺以更低的功耗提供更高的性能。然而，有效地使用这种计算能力正变得越来越困难。为了理解其中的原因，我们需要目前，并行性和能源效率是我面临的一些挑战。虽然微处理器的制造大致遵循摩尔定律，在同一个芯片上积累了越来越多的晶体管，但这种缩小曾经提供的好处已经变得越来越脆弱。直到大约过去十年，更小的晶体管需要更低的开关能量，同时提供更高的速度和更低的电压。总的来说，这导致了更高的频率和更好的整体性能，而能量密度和冷却要求没有显著增加，从而遵循了Dennard的减少原理[34，69]。但是，正如我们在消费市场上所看到的，时钟频率自2006年以来一直没有增加，当时它似乎在3.5到4 GHz左右达到了峰值在实践中，由于工作电压接近硅的固有阈值电压，并且由于泄漏电流随着晶体管的减小而增加，量子效应已经终止了丹尼德的缩减原理，严重限制了时钟频率的任何显著改善的可能性为了弥补这一损失，微处理器制造商转向了更多的并行性。事实上，由于然而，并行性的代价是，程序实际上必须从应用程序到机器进行设计，同时考虑在一个不同但同样重要的方面，记忆变得越来越重要。1引言2更有问题。虽然处理器和内存已经朝着更高的吞吐量共同发展，但它们并没有以相同的速度发展。众所周知，处理器和内存之间的性能差距越来越大，前者的吞吐量比后者的吞吐量和延迟提高得更快。值得注意的是，内存越大，距离处理器越远，访问所需的时间就越长。其内容。这促使人们使用内存层次结构，其中芯片上的小内存"缓存"较大的外部内存，依此类推。以这种方式，通常必须从全局存储器读取的数据可以更快地从本地存储器检索，只要它已经在那里。因此，缓存也是有代价的，这一次的程序设计必须考虑到这就引出了我们现在的问题：如何对这些机器进行有效的编程？这是因为并行性通常存在于在存储器访问方面尽可能单独工作的算法中另一方面，局部性是由以尽可能紧凑的方式处理其数据的算法提供的，其中两个不同的操作操作尽可能接近地处理数据。为了调和这两个看似矛盾的目标，我们需要更仔细地研究架构但这也意味着算法越来越依赖于底层架构，而此时语言正在远离底层架构，以提供更大的灵活性、可移植性和易用性这意味着最"静态"部分的编译器（以及实际上，理想的编译器将把用高级编程语言编写的一段便携式代码转换成一个适合于体系结构的二进制文件，主要考虑算法的正确性，从而以全自动的方式处理局部性和并行性等问题在这方面，尽管这种编译器的开发是困难的，因为它们有一个很强的约束：无论源程序有多复杂，生成的代码都必须计算与原始代码相同的结果为了简化任务，编译器集中引言3在局部属性保证校正的小规模优化中从转换。然而，针对并行性和局部性进行优化需要更大范围的代码分析和转换，可能会混合多个循环或函数，而编译器很少会冒险进行这些转换。在这个方向上，一个重要的研究框架，提供了通过多面体分析和优化提供了数学严谨性和表达性。这个程序和转换的"模型"是建立在有限不等式算术的基础上的，它然而，中心多面体模型有很大的局限性。在其最简单的形式中，它需要对计算和数据访问的精确描述，计算的顺序（总）排序，并且本质上只需要分析和优化，这些分析和优化可以用关于程序变量、参数、存储器访问或排序规范的严格不等式来描述。这篇论文的目的和范围是扩大（即发展）新技术），并将在介绍这篇论文的安排之前，让我们先谈谈导致这份手稿中描述的作品的隐藏历史。我们的出发点是扩展Alexandru Plesco的论文我们的目标是在一个更具概念性和通用性的框架中更好地理解与内核传输相关的片间数据重用和数据移动，因为这些似乎越来越重要，不仅针对FPGA，而且针对多核和GPU进行优化。C’est,par exemple, la motivation première d’OpenAcc 类似地，PPCG[75]（一种用于GPU的多面体编译器）中的数据传输非常相似，特别是从全局内存到共享内存的移动然而，在PPCG中，以及在A. Plesco，图块大小必须在编译前固定，这使得建模变得困难引言4静态性能和块大小选择的影响。就FPGA而言，这项工作甚至更加困难，因为所使用的技术在高级合成工具（HLS）之前为了评估不同大小的图块的性能，有必要手动对每个大小的图块进行所有这些更改因此，我们我们还考虑了事实证明，当瓷砖（可能包含并行性）按顺序（沿着定义它们的轴）运行时，即以局部并行但全局顺序（LPGS）的方式，尽管问题本质上是二次的，但它可以完全参数化地然后，我们希望应用标准的内存收缩技术来定义本地内存中传输数据的分配。这些技术需要对数组元素的生存期进行分析（即，知道元素何时"失效"及其可重用的位置），更具体地说，一种干扰分析，描述数组中可以共享相同内存位置的元素。然而，为了覆盖通信和计算，我们使用了一个流水线规范来表达然后，我们发现，即使在这种有限形式的并行性下，某些直觉性质，对于完全有序的计算是正确的，也不再适用。这导致我们修改和扩展了用于寿命分析和并行调度情况下的干涉构造的标准多面体技术最后，使用这种分析，仍然需要应用标准的数组收缩技术来分配本地存储器中传输的数据。对于许多然而，在IM- PACT'14会议间隙的讨论中G. Bhaskaracharya向我们展示了一些基于格（欧几里得网络）的内存分配理论然后我们独立于他们工作引言5在干涉由多面体的非凸并描述的情况下扩展基于格的存储器分配的问题这导致了一个不同的解决方案，有一些共同的发现，如寻找分配方向这篇论文讲述了这个故事的细节。它的组织方式如下：背景和相关工作，其中我们概述了当前的硬件体系结构，并概述了它们的功能、限制和相关考虑因素。我们还简要地回顾了什么参数化图块的跨图块重用，我们使用参数化图块大小和重用来激励、描述和处理图块 图块间数据，并行规范的生命周期分析，我们在其中描述如何处理并行程序，这些并行程序的底层调度自由度（可能对应于偏序）由happens- before关系捕获。我们展示了如何表示经典形式的并行性，以及如何在这样的描述上重建多面体分析，如内存分配，其中我们通过选择重用方向的相同机制来扩展结合引言6转移计算内核，我们将前面的所有章节结合起来，以生成针对CPU和GPU优化的代码，并可能同样适用于FPGA。我们展示了参数分析的好处我们在结束这份手稿时总结了我们的工作和一些观点。简介在我们的现代生活中，计算机无处不在。它们在医学、物理学、数学、经济学以及摄影、电影、音乐甚至文学等不同领域都有应用。他们承诺以更低的能耗进一步提高性能。但要有效地使用这种处理能力正变得越来越困难。为了理解为什么，我们需要一点背景知识。今天，一些主要的挑战是平行性和能源效率。虽然微处理器制造大致遵循摩尔定律，在同一个芯片上封装越来越多的晶体管，但与收缩相关的好处却越来越大。直到最后十年，更小的晶体管意味着更小的能量来开关它们，更高的开关速度和更低的电压。总的来说，这提供了更高的频率和更好的整体性能，而没有显著增加能量密度或冷却要求，遵循被称为Dennard缩放的缩放原则[34，69]。但正如在消费市场上所看到的，时钟频率直到2006年左右才增加，当时它似乎停留在3.5到4 GHz左右。实际上，当工作电压接近硅的固有阈值电压，并且较小的晶体管尺寸意味着更大的漏电流时，量子效应使Dennard放大器保持严重限制了时钟频率的进一步显著增加。为了弥补这一损失，微处理器制造商专注于并行性。然而，即使在恒定的时钟速率下，每个周期的并行操作数量的增加也将潜在地提高性能，并且越来越多的晶体管的可用性使其可行。然而，并行性是有代价的，这就是为什么程序的设计必须始终考虑到并行性和竞争性。在一个不同但重要的方面，记忆变得越来越有问题。虽然处理器和内存共同朝着更高的吞吐量发展，但它们并没有以同样的速度实现这一目标。存在所谓的处理器-内存性能差距，其中前一个的吞吐量比后一个的吞吐量和延迟更快。 最大的是内存，最大的是处理器。访问其内容所需的时间。这激发了内存层次结构的使用，其中小的片上内存隐藏了更大的片上内存，因此。这样，7引言8通常从全局内存读取的数据可以从本地内存快速且廉价地读取，前提是它已经存在。 把它藏起来这是一个成本，也是一个程序在设计时必须始终考虑到数据本地化和管道化的成本。这就引出了我们当前的问题：如何高效地对这些机器进行编程？尽管如此，并行性通常是由在数据访问方面以尽可能可分离的方式工作的算法提供的，其中两个操作尽可能地操纵数据。 另一方面，局部性由算法提供，该算法以尽可能打包的方式处理数据，其中两个操作尽可能关闭的数据。为了调和这两个看似相反的目标，需要更仔细地研究架构，其中诸如缓存线和共享内存等概念有助于产生并行性和位置感知程序。但这也意味着，在语言为了更大的灵活性、可移植性和易用性而进一步发展的时候，算法需要越来越多地依赖于底层架构。这意味着大多数"静态"部分的编译器（以及大多数"动态"部分的运行时/操作系统）现在是拼图的中心部分Indeed是一个理想的编译器，它将把用户用高级编程语言编写的一段可移植代码转换成一种二进制形式，并以自动化的方式考虑到体系结构、处理、其他、局部性和并行性。在这方面，尽管编译器在实践中并不完美，但在处理自动并行化和矢量化所带来的各种问题时，编译器正在缓慢但肯定地变得更好开发这样的编译器是困难的，因为它们有一个强有力的约束：无论输入程序多么复杂，生成的代码都应该计算相同的内容。 结果与原件相同。为了简化任务，编译器专注于小规模优化，其中局部属性保证代码转换的正确性。 但是并行性和局部性优化需要对代码进行广泛的分析和操作，可能需要 最初混合多个循环或函数，编译器很少冒自己进入的风险。在这个方向上，一个既提供数学的健全性又提供相当广泛的表现力的重要工具是多面体代码分析和优化框架。这个程序和转换的"模型"建立在精确不等式的算术之上，能够以足够的精度描述代码片段，以确保正确的转换，并具有足够的灵活性，以允许在同一框架中完全描述最常见的程序转换无，中心的"多面体模型"有很大的局限性。在其最简单的形式中，它需要对计算和数据访问的精确描述，
我的内容管理
展开
