非结构网格计算的分布式高效算法

非结构网格计算Loic Thebault引用此版本：Loic Thebault.非结构网格计算的可扩展高效算法分布式、并行和集群计算。巴黎萨克雷大学（COmUE），2016年。英语NNT：2016SACLV088。电话：01701925HAL Id：tel-01701925https://theses.hal.science/tel-017019252018年2月6日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire编号：2016SACLV088Thèse deDOCTOR aTde预备一个不同的德韦尔斯山19580年博士学校Sciences et Technologies deparM. Loic ThébaUL t非结构函数法计算的有效性Thèse presentée et soutenue à Versailles，le 14 October 2016.评审团组成：M. 弗洛里安·德·维斯特ENS Cachan(Pr陪审团成员）M. 埃马纽埃尔·让诺Directeur de Recherche，INRIA（特别报告员）M. 戴维·德福梅尔特雷德孔费埃（特别报告员）M. 文森特·莫罗佩皮尼昂大学Chargé de Recherche CNRS，CORIA（审查员）M. 广定研究工程师（审查员）M. 威廉·杰尔比达索航空Versailles大学讲师（Directeur dethèse）邀请函：M. 埃里克·珀蒂M. 维克托·李研究工程师，英特尔研究工程师，英特尔（Encadrant）iiiii雷默西芒这些年来，在我看来，我不允许重新建立一个大规模的人的视野，但我们有一个共同的理解和同情我会感谢所有这些为实现农业和富裕做出贡献的人。我非常感谢我的导演威廉·杰尔比，在LI-PARAD中有着非常好的条件，而且我对这些年的一切都充满信心。J’espère que le pot lui plaira même s’il n’est pas estampillé我希望所有人都能接受我的陪审团的裁决，并接受我非常感谢我的报告员埃马纽埃尔·让诺先生和戴维·德福先生，因为他们能在这么短的时间内注意到我，也因为他们能回来。非常感谢Florian De Vuyst先生Vincent Moureau先生和Victor Lee先生接受了我的考试我向广定表示衷心的感谢，希望您能在这几年里一直对我表示同情，也希望您能接受我的考试我也很感谢达索航空公司（还有你！）为了让我在这方面的工作上有更好的合作。我特别感谢埃里克·珀蒂，我的侍从，但我不确定今天的情况他是我的向导帮我完成了我的第一个年度任务我有很多新奇的想法，也有一个学术评论，他对我进行了规范。非常感谢老师。我也会为索蕾娜做点什么，让她吃点饼干，然后把办公室的事办好！我希望所有的实验室成员都能和我一起工作或讨论，特别是巴勃罗·德奥利维拉，因为他有着良好的人性，而且他的沟通能力很强，可以穿越那些黑暗和黑暗！我非常感谢马克·齐布克吉安的理念和他的帮助。但是，所有这些年来，在所有情况下，没有那些能缓和气氛的办公室，我们都很开心。他很难找到一个平等的办公室氛围。. . 非常感谢CS，帝国时代，塔穆尔，七大奇迹的支持。. . 但伊库拉斯的军队也一样220 B局的未来住户如果您在人造平台上发现了毒药不用问这我很感谢我的教练：JB，CS的教练，还有查迪，他在LOL上很活跃。我知道我不是很好. . 感谢米哈伊尔，因为他是一个分享者，也是一个相对的人，而不是一个与理论相关的人。非常感谢Nathalie（和Sylvain）为我们准备了几次早餐，也为奥尔良和Arcueil的烧烤做了准备。感谢Seijilo，我们的前上帝，为了世界上的伟大理论和未来的力量感谢我对办公室和办公室的访问，克莱芒，还有隔壁的女孩劳拉，为我们即兴表演了一个角落或另一个角落;-）。这几个月的天气很好！最后，我对我的父母充满了感激之情，他们一直都在为我服务，他们也一直在做我今天才来的事情两个人一起去。我不可能在没有普普，也就是贝亚的情况下完成这些回报，他一直在支持我，帮助我，但我的支持者一直在感谢您的光临，我们为您准备了法式长棍面包，同时也为您提供了一个简单的烹饪方法P.S.谢谢你！ 是的，你是在给我演讲的时候用枪的， 也许只是感谢但这是个好的开始ivv佩翁-泰萨尔的一生一个美丽的日vivii××简历信息技术是众多科学领域的核心。科学技术领域的研究主要涉及数值模拟。Ce besoin croissanten simulation a conduit à这些超级计算器需要一个能量转换器和一个重要的加的计算能力。这些新的材料变化一致地增加了计算和计算核心的名称。这一增加继续确定，只是增加了多个百万的计算值，同时也增加了一个百万的核心这些资源并不丰富计算核心的倍增意味着核心记忆的减少，加上données的交通，一个cohérence协议加上cohesteux，需要并行的优势。另外，现在的建筑是非常的。在众多应用和实际模式中，最重要的是适应这些新趋势。特别是，在非结构化邮件的使用方法中，一般都是平行的，而且这是一个最小的同步和均衡工作费用的名称，这是一个特别困难的问题这些基于区域结构和色彩的实际方法，尤其是与多中心建筑的关系，都可以追溯到这个问题。新的探索者必须偏离平行线在对现有建筑的多重平行性进行有效开发后，不同的建筑物接近于组合的平行性。Leparallelisme benefit de données se limite historiellement aux problèmes régulier pouvant êtredécomposés en grilles de calcul. Ces problèmes sont adaptés aux exécutions de typeprogrammeunique，données multiple（SPMD）sur CPU ouflux这一点提出了多方面的贡献，目的是消除这一限制，以处理各种效率的准则和结构。我们将在平行分布、分隔和矢量形式的网格上对结构进行平行混合。此外，一个应用程序的工业pouvant difficilement être intégralement récrite，我们avons exploréle概念的原型应用程序在offrant une représentation profiée。Nous avons décampé Mini-FEM，uneproto-application représentative de l'application DEFMESH décampée par Dassault Aviation. Nousavons ensuite dépé la librairie D C à partir de cette proto-application，puis我们将把AETHER上的DC图书馆作为达索航空公司的另一个流体力学代码。在原型应用中得到的结果是在类似计算方案的应用中得到的。我们对多核Xeon classiques和Xeon Phi型KNC进行了测试。在512颗心的桑迪桥上，有2000颗心，D& C将在3号MPI上进行纯化。47例患者的疗效为77% 在4个KNC中，&DC获得了96%的平行有效性和2个加速率。9比较了MPI社区基础设施对区域结构的影响此外，性能obtenue avecDC est équivalente à 96 coeurs de type Xeon Sandy Bridge. 在&降低代码强度的情况下，DC在4KNC上的并行效率下降了92%，但与MPI增强到6的纯版本相比下降了92%。56倍。Mots-clés：HPC，multitâche，FEM，maillage non structuré，D C，Cilk，vectorisation，PGAS，GASPI×××摘要计算科学是广泛的科学领域的中心目前几乎所有的科学和技术研究活动都依赖于数值模拟来解决新问题或设计新产品。对数值模拟的需求不断增长，导致计算中心更大、更复杂，HPC软件也越来越多。实际HPC系统架构对能效和性能的要求越来越高。硬件设计的最新进展导致节点数量和每个节点的核心在未来的后艾级系统中，可以合理地预见由数千个核心组成的数千个但是，有些资源的规模并不相同。核和并行单元数量的增加意味着每个核的存储器更低，对并发性的要求更高此外，当前的趋势导致异构体系结构的使用越来越多。目前使用的大多数应用程序和运行时都在努力适应当前的趋势。在有限元方法的上下文中，在非结构化网格计算上暴露大规模并行性，并具有有效的负载平衡和最小的同步是具有挑战性的。当前依赖于主任务分解和着色的方法加剧了这些问题，特别是对于并行众核架构。HPC用户必须探索应用程序、运行时和编程模型的新范例为了有效地利用这些体系结构，必须将几种并行化策略结合在一起，以利用多个级别的并行性。暴露大量数据并行性的并行化方法通常局限于常规问题。这些问题可以在计算网格中分解，并且非常适合CPU上的单程序多数据（SPMD）执行或GPU上的单指令多线程（SIMT）执行这位博士论文提出了几个贡献，旨在克服这一限制，解决不规则的代码和数据结构，在一个有效的方式。我们开发了一种混合并行化方法，结合分布式，共享和矢量形式的并行在细粒度的基于任务的方法应用于不规则结构。此外，由于非常大的工业代码不能从头重写，我们在一个真实的工业用例上实验了原型应用程序的概念，作为计算机科学家和应用程序开发人员之间的代理。我们开发了Mini-FEM原型应用程序，代表达索航空的DEFMESH应用程序。然后，我们在原型应用程序之上构建了DC库，并在原始DEFMESH应用程序上对其进行了验证。我们还将DC库移植到另一个流体动力学应用程序AETHER中，AETHER也是由达索航空开发的。结果表明，原型应用程序上验证的加速比可以在其他使用类似计算模式的全规模应用程序上重现我们使用标准的Xeon多核和Xeon Phi KNC多核来实验我们的方法。在512个Sandy Bridge核心上，我们超越了纯MPI方法高达3。47，达到77%的并行效率，每个核心只有2000个顶点 通过在4个Xeon Phi上运行密集计算内核，我们实现了96%的出色并行效率和2. 9的加速比相比，普通的方法只基于MPI域分解。通过将算术强度降低100倍，DC库的并行效率降低到92%，但比纯MPI版本快6.56倍最后，在4个Xeon Phi上运行，D C具有与96个Intel Xeon Sandy Bridge内核相似的性能。关键词：HPC，多线程，FEM，非结构网格，DC，Cilk，矢量化，PGAS，GASPIVIIIixC内容介绍1一、技术水平91异构硬件架构111.1一.导言. 111.280年创新成就多核121.3GPU架构151.4众核架构161.5超级计算机181.6实验环境191.6.1英特尔Sandy Bridge 191.6.2居里201.6.3Anselmand Salomon安瑟伦和所罗门211.6.4MareNostrum 222HPC并行编程模型232.1一.导言. 232.2MPI模型-消息传递接口252.2.1双向沟通262.2.2集体通信272.2.3第28章片面的沟通2.3PGAS模型-分区全局地址空间312.3.1单方面沟通的利弊322.3.2GASPI及其GPI-2实施2.4OpenMPWorksharing Model 362.5任务模型37x2.5.1OpenMP任务382.5.2CilkPlus 402.5.3CilkView用法示例423有限元方法的优化策略3.1导言. 433.2有限元计算单元443.3稀疏矩阵的压缩存储格式453.4区域分解方法473.4.1光环交换483.4.2多级图划分493.5混合动力汽车503.5.1非结构化网格的着色513.5.2分而治之并行算法533.6非结构化网格上的矢量化543.7优化网格计算中的局部性56二、捐款. 594代码现代化简介614.1一、导言. 614.2达索航空4.2.1DEFMESH网格变形器应用程序624.2.2AETHER空气动力学和热力学应用634.2.3用例列表634.3原型应用概念644.4AETHER 65中DC库的集成4.5结论655节点级并行性675.1一、导言. 675.2共享内存在非结构化网格上划分和征服685.2.1使用的符号695.2.2递归二分法695.2.3局部改善705.2.4结果的数值稳定性xi5.2.5DC矩阵存储格式735.2.6D C树的预计算735.2.7CilkPlus实施745.2.8OpenMP实施755.3实验结果775.3.1实验装置775.3.2FEM组件785.3.3求解器835.3.4Cilk Plus和OpenMP3.0任务之间的比较835.4结论876核心级矢量化896.1一、导言. 896.2高效矢量化的着色906.2.1实现矢量化906.2.2基于颜色的矢量化模型916.2.3最长颜色策略926.2.4有限颜色策略936.2.5减少内存消耗和同步需求956.2.6结构化、向量化和局部性6.2.7向量长度敏感性研究976.3实验结果986.3.1单节点实验996.3.2增加算术强度1006.3.3KNC实验1016.4结论1047分布式层次结构1077.1导言. 1077.2沟通优化的潜在收益1087.2.1沟通重叠的好处和局限性1097.3用GASPI 110实现大容量同步通信7.4使用GASPI 111实现异步和多线程通信7.4.1通信级别版本1127.4.2有限通信大小版本114xii7.5实验结果1187.5.1每个节点的进程数量的影响1187.5.2单节点实验上的批量同步比较1197.5.3使用标准算术强度121的Xi7.5.4使用标准算术强度123的7.5.5多功能一体机D C版本1247.6结论127结论与展望131图139参考书目143一、生产13一般上下文计算科学是广泛的科学领域的中心大多数研究项目都依赖于数值模拟来解决新问题和设计新产品。在各个领域都可以找到许多例子。在航空方面，飞机最初是通过绘图板设计并在飞行试验后进行改进，自20世纪70年代初以来，已开始采用计算机辅助设计。今天，它们完全是通过计算机构思的，涉及不同的研究领域，如结构力学，空气动力学和电磁学。2013年底，一个旨在模拟和更好地理解人类大脑的大型人脑数值模拟也有利地取代了法国直到1974年进行的核武器试验最近，HPC系统上的深度学习方法击败了围棋游戏的世界最佳选手如今，仿真无处不在它包括汽车发动机和汽车设计的阐述，新药物的概念，化学反应的模拟，大量数据的分析等等。计算流体力学计算流体动力学（CFD）领域尤其与计算科学密切相关CFD是流体力学的一个分支，它通过求解涉及流体流动的数值方程来流体力学是一个广泛的话题。它有广泛的应用，包括例如机械，化学，地球物理学，航空航天，天体物理学，生物学，生命科学，或数值天气预报。计算流体力学问题的第一步是定义代表初始问题的几何形状。然后，将计算域转换为网格。网格是将空间离散成单元，通常为数百万到数百亿，其可以具有不同的形状，例如2D中的三角形和3D中的四面体。网格可以是规则的，即所有单元格都具有相同的形状和几何形状，也可以不具有相同的形状和几何形状。图1所示的不规则网格主要用于计算流体动力学问题。事实上，计算域的某些部分，例如生成连续性的表面及其相邻区域，比其他部分更重要因此，这些区域的细胞较小，数量较多存在若干离散化方法，例如有限体积法（FVM）、有限元法（FEM）或有限差分法（FDM）。在这篇论文中，我们专注于有限元应用。更多详情见第3.2节。一旦网格被构建，就必须定义要使用的数值方法取决于图1：3D非结构化网格示例。4要解决的问题和所需的近似水平，数值方程可能会有所不同。基本的CFD数值方程是Navier-Stokes方程。它们用于大多数CFD模拟。然而，这些方程可以简化为欧拉方程，再简化为全势方程，或线性化的势方程。在所需解决问题的准确性与分配给它的资源和时间之间存在权衡最后，定义了边界条件和初始值。前者对应于问题边界处的流体性质。一旦完成所有这些预处理步骤，就可以开始数值模拟。高性能计算在计算流体力学应用中遇到的问题的准确性和复杂性的需求，以及解决问题的规模正在增加。这导致对数值模拟性能的需求不断增长，从而导致更大和更复杂的计算中心。在2000年之前，计算机性能的演变主要是由于中央处理器（CPU）和内存总线频率的增加但是这种对更高频率的竞争已经达到了能量消耗和散热的极限。因此，性能演变已经转向增加构成CPU的计算单元的数量，即核心，而不是增加它们的频率。然而，设计这样的新架构和开发能够有效利用它们的应用程序是复杂的。这就是高性能计算（HPC）的本质。硬件架构随着对性能和能效要求的不断提高，硬件架构的发展导致HPC系统越来越复杂硬件设计的最新进展导致分布式计算节点的数量增加，每个节点的核数量增加，以及更大的向量指令单元。在未来的后艾级系统中，人们可以合理地预见数千个节点和数千个核心。但是，有些资源的规模并不相同。并行单元数量的增加意味着每核存储器更低，并发性要求更高，一致性流量更高，一致性协议的成本更高此外，新的并行体系结构的发展探索了不同的方式。一方面，有一种经典的CPU模型，它包含少量功能强大的核心，旨在尽可能快地执行顺序工作负载。另一方面，还有最初为图形目的设计的图形处理单元（GPU）模型它由大量的简单内核组成，并依赖于应用程序中的可用并行性来隐藏计算延迟。然而，虽然CPU正在发展变得越来越并行，但GPU已经变得更加通用和可编程。这两个模型将来可能会形成一个统一的架构模型。英特尔最近推出的至强融核（Xeon Phi）多核处理器处于这两种型号之间的前沿，说明了这一新趋势。并行模型的不同演化导致异构体系结构的使用越来越多。现代超级计算机由许多分布式计算节点组成，这些节点能够同时包含多个多核CPU和多个众核或GPU加速器。并行编程模型为了利用这种多样的计算资源，出现了多种并行编程模型。最近的体系结构及其相关的并行执行模型涉及多个协作进程同时在不同数据上执行相同的程序并行编程方法必须利用分布式和共享内存系统，但也要利用向量运算符。5××进程通常跨分布式计算节点使用它们是独立的计算流，拥有自己的私有内存。进程之间的交互由通过网络演化的消息处理消息传递模型及其消息传递接口（MPI）应用程序接口（API）已成为处理通信和同步的标准[1，2，3]。MPI提供了一个API来执行一对一和集体操作。然而，存在其他方法全局地址空间编程接口（GASPI）API [4，5，6]是当今最先进的实现之一PGAS模型包含一个在分布式进程之间共享的全局内存空间。远程进程可以通过远程直接内存访问（RDMA）直接写入另一个进程内存。另一方面，线程用于在共享内存上下文中生成并行执行流。线程是进程中的实体，它依赖于它的虚拟地址空间和可执行代码。因此，它们比进程轻，并利用共享内存进行通信或同步。存在用于多线程并行性的若干编程接口。最常见的是POSIX线程，也就是pthreads，广泛使用的基于OpenMP pragma的模型[7，8，9，10]，或者是Intel Cilk Plus [11，12，13]和ThreadingBuilding Blocks（TBB）[14]基于任务的模型。多线程方法的低内存消耗和低开销支持混合编程模型。只有一个进程被映射到每个计算节点或最终处理器，而节点内的所有共享资源都由线程处理。分布式内存库（如MPI或GASPI）已经适应于处理多线程通信。除了这些混合进程和线程模型之外，位于核心级的向量资源提倡单指令多数据（SIMD）向量化。此外，GPU通常使用单指令多线程（SIMT）模型，其中大量线程在不同数据上并行执行完全相同的指令流因此，以有效的方式组合所有这些编程模型会导致性能可伸缩性的严峻挑战。问题为了有效地利用最近的异构体系结构，几个并行化策略必须结合在一起，以利用多层次的并行性。由此产生的混合编程模型结合分布式通信和共享内存线程模型是难以实现的。每一层的并行性必须有效地利用相应的体系结构级别，而不同的层必须适当地相互共存消息传递模型（例如MPI）限制了拆分和复制工作和内存，这可能会严重降低代码的效率。除了MPI之外，还通常使用OpenMP循环并行化来减少重复的数量然而，这种循环并行化方法允许代码中有许多顺序部分，这也降低了可伸缩性。例如，根据Amdahl定律，一个应用程序在256个核心上执行97%的并行化，只能达到29。6加速比，并行效率为11%。即使有99.9%的代码并行化，最大加速比为204，只有79%的并行效率。这在图2中示出。因此，目前使用的大多数应用程序和运行时都在努力适应当前的趋势[9]。在有限元方法的背景下，在3D非结构化网格计算上暴露大规模并行性，并具有有效的负载平衡和最小的同步是具有挑战性的。目前依赖于区域分解和网格着色的方法加剧了这些问题，特别是新的众核加速器。特别是，FEM组件最先进的并行化方法[15，16，17，18]，在第3章中详细讨论，显示出固有的限制，阻止他们在未来的众核系统上有效为了从新系统中获益，在设计应用程序时，主要考虑两个方面6250200150100501并行代码比例（%）图2：根据256个核心执行的并行代码比例的加速比concurrency和locality。并发性在于创建足够多的独立计算任务来为所有并发资源（即节点、核心和向量）提供支持。 关键路径上的每一个序列化和共享都是未来的瓶颈。记住Amdahl：系统中的并行度越高，顺序代码的时间比例就越高。我们还需要在核心级别（即缓存）、套接字级别（包括硬件加速器）和网络级别暴露局部性。但是，我们不能仅仅依赖于在核心、套接字和网络层的静态局部性，我们还应该确保数据通信的局部性。内核之间的内存一致性协议是用于数据共享的免费资源的隐含假设不再成立[19，20]。在设计并行算法时，必须考虑到在共享内存中交换数据和同步的通信开销因此，共享内存编程在概念上越来越接近分布式编程。此外，在少量核（例如，计算节点）上性能良好的应用在大量计算节点上不一定高效相反，一个完美的可伸缩应用程序不一定有效地利用底层资源，并且可能远远没有达到计算节点的峰值性能如图3所示，使用性能差的线程模型开发的应用程序和节点性能差的应用程序，与顺序执行相比，可以很容易地扩展，而不会降低并行效率相反，有效利用计算节点的共享资源的良好优化的应用程序将难以在不牺牲并行效率的情况下扩展。事实上，一个在单个线程上运行并使用100%计算和内存资源的非常高效的应用程序，在增加线程数量时，必然会减少每个线程的资源使用因此，当开发新的应用程序时，如果开发人员具有高的可扩展性，但FLOP峰值性能的使用率较低，那么就应该在节点级优化核心性能和线程模型。如果优化后的线程模型不再具有伸缩性，那么就需要重新修改分布式通信模式。节点性能和可扩展性对于有效利用超级计算机资源都是必要的。开发新应用程序时的另一个重要方面一个算法优化最大的照顾，但不可能开发和维护将高度松散的利益。●●●●●加速7●●优化代码未优化代码●●32倍加速●●3倍减速并行效率20个一点150.75100.50501 4 8 1632数量的计算节点0.250.001 4 8 16 32数量的计算节点（a）与最佳顺序性能（b）并行效率图3：典型的加速比和并行效率取决于代码优化的水平贡献在这篇论文中，我们提出了一个混合并行有限元方法。我们的混合方法的目标是在一个超级计算机的并行性的三个主要层次。计算节点之间的分布式内存并行，计算节点内部的共享内存并行，以及计算核心内的向量并行单元。它是基于域分解在分布式内存级使用异步和多线程的单边通信，递归分治（DC）在共享内存级，和微调着色启发式向量化在核心级别。其合理性是在架构的每一层采用最适合的策略，同时对算法进行架构无关设计因此，我们的代码可以适应低入侵和一些架构感知参数的底层硬件特性，如缓存大小或向量长度。第一个贡献涉及共享内存并行。我们取代了僵化的循环为基础的方法，一个通用的和高效的递归方法与架构无关的设计。此方法依赖于分治原则和英特尔Cilk Plus运行时，以生成FEM应用程序中使用的非结构化网格的并发性和局部性DC递归方法自然暴露并行性，并允许在网格计算和相关的稀疏矩阵系统中提高局部性。在这种方法中，我们递归地平分网格和置换的元素，这导致在一个并行和递归的任务树Cilk Plus运行时允许生成大量并行任务，并最大限度地减少它们之间的同步它还通过工作窃取调度器有效地处理动态负载平衡这第一个贡献导致在PARCO研讨会上出版了一份出版物[21]，第二个在HPCC研讨会上出版[22]。第二个贡献的目标矢量化在非常小的数据分区的非结构化网格。为了利用计算核心的向量资源，我们提出了一种方法，有效地暴露每个先前生成的任务中的独立元素这种方法是基于网格着色，并使用Cilk Plus数组表示法来生成矢量指令。这第二个贡献与DC方法一起导致了另一个出版物在PPoPP国际会议上发表[23]。第三个贡献涉及分布式内存并行。在我们的方法中，我们使用标准的我们提出了一个通信模式兼容的DC细粒度任务并行性在共享内存级别多线程的通信和重叠计算。这篇文章即将发表在一本杂志上。●●●●●● 优化的代码未优化代码加速