网格QCD优化和分布式内存的多主题表示

网格QCD优化和分布式内存的多主题表示引用此版本：迈克尔·克鲁斯。网格QCD优化和分布式内存的多主题表示。计算机与社会[cs.CY]南巴黎大学-巴黎第十一大学，2014年。英语。NNT：2014PA112198。电话：01078440HAL ID：电话：01078440https://hal.inria.fr/tel-01078440提交日期：2014年HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaireU大学巴黎-南部ECOLE DOCTORALE d'INFORMATIQUEDEPARIS- SUDINRIASAACALLE-DE-FRANCE/L ABORATOIrEDERECHERCH EEE NINFORMATIqueD.坐骨神经痛：我的格式是T是博士学位2014年9月26日由迈克尔·克鲁斯网格QCD优化和分布式内存的论文主任：克里斯汀·艾森贝斯研究主任（INRIA，LRI，巴黎第十一大学）评审团组成：报告员：M. 菲利普·克劳斯教授（斯特拉斯堡大学）M. Jagannathan Ramanujam教授（路易斯安那州立大学）检查员：M.希德·图阿蒂教授（尼斯索菲亚安提波利斯大学）M.保罗·福特里尔名誉教授（ENS Lyon）M.西尔万·康雄教授（巴黎第十一大学）M.奥利维尔·佩内退休研究总监（CNRS，LPT Orsay）客人：M. 吉尔伯特·格罗斯迪埃退休研究总监（CNRS、ALL Orsay）摘要受现代物理学的启发，除了实验之外，现代物理学还试图通过使用大型计算机模拟最先进的物理模型来验证和解释自然规律，本文探索了通过改进运行的模拟程序来加速这种模拟的方法。主要的焦点是晶格量子色动力学（QCD），量子场理论的一个分支，运行在IBM的新超级计算机Blue Gene/Q上。在第一种方法中，tmLQCD的源代码（一个Lattice QCD程序）被改进为在BlueGene机器上运行得更快。它最具性能相关性的操作是四维空间中的8点模板。两种不同的优化策略被追求：一种是空间和时间局部性的优先级化，另一种是利用硬件的数据在Blue Gene/Q上，第一个策略达到了该机器峰值理论浮点运算性能的20%峰值为54%的第二种策略要快得多，其代价是使用4倍以上的内存，即按照下一次模板操作中使用数据的顺序存储数据，并在必要时重复数据。使用的其他技术包括消息传递硬件的直接编程（IBM称为MUSPI）、线程的低开销工作分配机制、数据的显式数据预取（使用dcbt指令）和手动矢量化（使用QPX;宽度-4 PID指令）。基于硬件的列表预取和事务内存第二种方法是新编写的LLVM编译器扩展，称为Molly，它优化了程序本身，特别是数据和工作在集群机器（如BlueGene/Q）节点之间的分布Molly使用整数多面体表示数组，并使用另一个已经存在的编译器扩展Polly，它使用多面体表示语句和循环。当Molly知道数据如何在节点之间分布以及语句在何处执行时，它会添加管理节点之间数据流的代码。莫莉也可以交换内存中数据的顺序Molly的主要任务是将发送到同一目标的数据集中。由于单次传输涉及大量开销，因此相同的缓冲器。我们提出了一种算法，使用反链数据流最小化非参数化循环的传输次数。此外，我们只是一个启发式，它考虑程序员如何编写代码。异步通信基元分别在数据可用之后和使用之前插入。运行时库使用MPI实现这些基元。Molly设法分发任何可由多面体模型表示的代码，但对于像Lattice QCD这样的模板代码也做得很好。使用Molly编译，Lattice QCD模板达到理论峰值性能的2.5%。性能差距主要是因为缺少所有其他优化，如矢量化。Molly的未来版本还可以有效地处理非模板代码，并使用使手动优化的Lattice QCD模板如此快速。摘要除了实验之外，现代物理学还试图通过在大型计算机上模拟物理模型来验证和推导自然定律本文探讨了如何通过改进运行这些模拟的程序来加速这些模拟。L’applicationde作为第一步，我们改进了tmLQCD的源代码，这是一个LQCD程序，其性能的关键操作是4维8点模板。研究了两种不同的优化策略：第一种优先考虑空间和时间局部性的改善;第二种使用数据流的硬件预加载。在Blue Gene/Q上，第一种策略允许达到理论峰值性能的20%。第二种样式的其他被利用的技术包括直接通信系统编程列表预加载和事务内存--Blue Gene/Q的两个新机制--并没有改善 不是表演。在第二步中，我们介绍了LLVM编译器的Molly扩展的实现，以自动优化程序，更具体地说，优化数据和计算在集群（如Blue Gene/Q）Molly用整数多面体表示数组，并使用从数据分布和计算位置的规范开始，Molly添加了管理计算节点之间数据流的代码。Molly还可以交换Molly的主要任务是将数据聚合成数据集，这些数据集在同一个缓冲区中发送到同一个接收者，以避免太小的传输开销。我们提出了一种基于数据流反链的非参数化循环的最小化传输次数的算法。此外，我们实现了一个启发式，它考虑了程序员编写代码的方式。异步通信基元在数据可用后立即插入--分别在使用数据之前立即插入。运行时库使用MPI实现这些基元。Molly处理任何可以在多面体模型中表示的代码的分发，但最适合像LQCD这样的模板代码。使用Molly编译时，LQCD代码达到峰值性能的2.5%。性能差异主要是由于未进行其他优化（例如矢量化）。Molly的未来版本还可以有效地处理非模板代码，并利用其他优化，使手动优化的LQCD代码如此之快。祖萨门法松Zusätzlich zur Experimentalphysik verssucht die moderne Naturwissenschaft auch Naturgesetzedurch Computersimulationen auf Großrechnern herzuleiten und zu verifizieren.这是一个很大的问题，也是一个很大的问题，也是一个很大的问题。Der Schwerpunkt致力于优化Anwendungen的Gitter-Quantenchromodynamik（QCD晶格），用于IBMs neuestemGroßrechner，Blue Gene/Q。第一个Ansatz是关于tmLQCD的Anpassen，一个用于晶格QCD模拟的程序，一个蓝色的基因研究所。塞纳河为Geschwindigkeit wichtigste运营是一个8-朋克风格的四维。Dabeiwerden zwei verschiedene Optimierungstrategien verfolgt ： Eine zur Verbesserung derzeitlichen und örtlichen Nähe und eine Zweite um der Hardware das Vorausladen derDatenströme zu ermöglichen. Auf dem Blue Gene/Q erreicht die erste Strategie bis zu 20%的运动理论为Geschwindigkeit für Gleitkommaoperationen. 德国的战略是把54%的德国人放在那里 ， 把 Nachteil eines bis zu 4x höherem Speicherverbrauchs durche eine Umsortierung derDaten in Lesereihenfolge inklusive Duplizierung mehrfach gelesener Werte.Weitere genutzte Techniken是由Blue Gene/Q（von IBM auf den Namen MUSPI getauft）的通信指令所吸入的技术，是线程-劳动力垂直化的机制，是kürze benötigter Daten和manueller Vektorisierung mittels 256 位 SID 指 令 集 （ QPX genant ） 中 的 前 向 数 据 集 。Transaktionaler Speicher sowie硬件列表预取-Der zweite Ansatz是一个为LLVM编译器命名的Erweitung，它把Molly Welche程序命名为selbstätig parallelisier，它把系统命名为speicher wie dem Blue Gene/Q。Molly stellt数组将Hilfe von Polyedern dar und benutzz放置在存在于Polly welche Anweisungen und Schleifen和Polyeder darstellt的建筑物中。数据收集者数据收集者莫莉·坎恩在《我的演讲》中写道："我的演讲者是一个普通人。"Mollys Hauptaufgabe est das Zusammenstellen von Daten zum selben Ziel zu einer Nach-我们的共同点是，我们的共同点是。Wir stellen einen Algorithmus mittles Antiketten vorwelcher die Anzahl der Übertragungen minimiert wenn die Schleifen unparometrisiert sind.Eine Heuristik，死在莫莉只是，定向sich stattdessen and der Quelltextstruktur.异步数据通信的未来是一个恒星的未来，一个dem zu übertragenen Daten verfügbar sind，sowie kurzbevor sie auf dem Ziel benötigt werden.Eine Laufzeitbibliothek übersetzt diese Anweisungen在MPI-Aufrufe。Molly kann prinzipiell jeden das Polytopmodell darstellbare Quelltext parallelisieren ，funktioniert aber am besten für Stencilcodes wie Lattice QCD. Mittels Molly Kompiliert的误差率为 2.5% 。Der Unterschied zur manuelle optimierten 版本 kommt hauptsächlich durch dasFehlen anderer Optimierungen wie der Vektorisierung zustande.《明史》（卷131）：“王之乱，其人之乱，其人之乱。7内容物图9列表表列表10算法列表11列表121导言131.1动机141.2本文贡献151.3论文结构16I蓝色基因的QCD晶格优化172 晶格量子色动力学192.1量子色动力学192.2晶格QCD212.3迭代求解器252.4Wilson-Dirac运算符模板262.5域分解302.6tmLQCD313 蓝色基因/Q超级计算机3.1蓝色基因/Q架构3.2处理器343.3记忆373.4网络404 手动优化434.1偶数和奇数元素4.2浮点指令矢量化444.3加载存储矢量化484.4光栅线性化和迭代阶504.5精确度604.6运行时60中的布局选择4.7缓存管理614.8组件级优化644.9对称多处理和同时多线程664.10 基本操作688内容4.11 削减684.12 消息单元系统编程接口695结果715.1全旋布局725.2半旋片布局766讨论816.1摘要816.2结论826.3进一步优化的可能性836.4相关工作86II表示Polyhedral Model89中的内存布局791型多角大楼7.1Polyhedra917.2静态控制部件987.32D Jacobi105的示例8分布式内存并行性与多面体模型1118.1数据分发1118.2工作分配1138.3数据传输1148.4块1158.52D雅可比1269莫莉1319.1C++语言扩展1319.2工具链1349.3莫莉山口1399.4MollyRT14810 结果15110.1 雅可比2D15110.2 晶格QCD15510.3 生命的游戏16011 讨论16311.1 摘要16311.2 结论16411.3 未来工作16511.4 相关工作167原始跳跃矩阵源169B 符号摘要175B.1集合、关系和函数175B.2典型占位符和常量名称1779图列表2.1离散时空222.24D邻居232.3Dirac操作员模板数据流272.4带投影的狄拉克模板中的流动292.5域分解313.1 A2处理器流水线354.1组合两个复数值4.2物理站点的数据排序504.3物理站点坐标514.4在不同阵列中存储坐标为偶数和奇数的站点4.5元素在迭代field时重用534.6多线程波阵面544.7物理站点的替代形状544.8身体、表面和光晕554.9物理体和表面564.10 均匀站点的半旋布局574.11 模板和反向模板584.12 减少方案695.1T表5.1的可视化735.2T表的可视化5.3 755.3T表5.5和5.6的可视化5.4T表的可视化5.8 788.1块化函数（8.1）1168.2反例1219.1Molly工具链内部1359.2莫莉通行证实习生1409.3现场访问隔离1419.4独立块之后1429.5用于本地存储初始化的简化转换/调用序列10.1 T表10.1153的可视化10.2 T表10.2的可视化15410.3 T表10.3的可视化15410.4 T表的可视化10.4 15610表列表2.1单个模板的计算复杂性302.2字段元素大小302.3每个模板执行的内存访问字节数3.1Small Blue Gene/Q工作尺寸403.2QCDOC和Blue基因家族比较424.1元素占用的615.1特色全旋图布局结果725.2线程数变化745.3变化的地方卷745.4弱标度755.5特色半旋片布局结果765.6单个节点结果765.7线程数变化775.8变化的地方卷785.9弱标度799.1数据流类别1439.2通信基元概述1449.3精选的内在及其替代品14610.1 Jacobi 2D按节点执行次数排名15210.2 雅可比2D变化子卷15310.3 Jacobi 2D弱缩放15410.4 Lattice QCD特色结果15610.5 LatticeQCD结果，每个节点的排名不同15710.6 具有变化子体积的15710.7 Lattice QCD弱缩放结果15810.8 康威11算法列表共轭梯度（CG）迭代求解器254.1显式预取648.1反链组块1188.2时间表相关块启发式12012列表4.1跳变矩阵的第一阶段：乘法和发送4.2跳变矩阵的第二阶段：接收和重建4.3主/工作者算法（C类伪代码）4.4被称为68的工人7.1静态控制示例第98部分7.2具有结构参数N99的SCoP示例7.3雅可比示例代码1068.1用于说明无效块的程序1168.2显示块化启发式120的未完成结果的示例程序9.1清除数组的13210.1 Molly159的Lattice QCD程序10.2 康威13113简介1974年，物理学家肯尼思·格迪斯·威尔逊（Kenneth Geddes Wilson）发表了一个关于如何使用有限数量的代表性测量点来近似连续时空中四种基本力中的一种的理论。 这些点排列在等距网格中，也称为网格。他这样描述的力是把夸克拉到一起的强力。关于这种强力的理论也被称为量子色动力学（QCD），而离散化理论被称为晶格量子色动力学（Lattice QCD，或简称LQCD）。场论与其他物理学理论的不同之处在于，它们不是关于在空间或时空中相互作用和运动的显式物体，如牛顿引力。相反，时空被理解为在空间和时间中的每个坐标处都有值。最常见的值是标量（一个像开尔文温度一样的数字）或矢量（像重力一样;矢量的方向是有质量物体被拉向的方向，它的长度是拉的强度），但Lattice QCD使用的是称为自旋的数学对象。由于空间和时间是连续的，因此存在无限多个这样的坐标，因此无法进行数值计算，但威尔逊引入的离散近似可以。1972年的计算机还没有强大到足以进行这样的计算，但随着时间的推移变得更强大。随着每一代高密度计算机的出现，网格变得越来越可行，因此，近似值有望越来越接近现实。这些模拟用于推导可观测的物理常数。这些常数也可以通过实验测量，但使用第二种方法来确认它们，第二种方法是从描述它们的物理模型中单独推导出来的，这增加了对模型正确性的信心如果模拟与观察到的现实不匹配，则模拟必须进行微调或当前物理学不正确。可证伪性是理论的一种性质。在这种情况下，从模拟中推导出的新理论可以通过提供新的见解来推进物理学。此外，知道同样的物理常数可以从其他常数中推导出来（如真空中的电学渗透率0来自光速和磁敏感度），减少了理论的任意性，从而简化了理论。今天，晶格模拟运行在一些最快的计算机上，通过增加时空离散化产生的网格密度来追求更好的近似。它增加了测量点的数量，从而增加了计算工作量。原理很简单：模拟的晶格点越多，预期的结果就越准确。在相对较小的晶格尺寸上的模拟可以在任何个人计算机上完成，我们不能期望在这种规模上有新的发现。大规模计算机是集群计算机--它们之间具有快速连接的许多单个计算节点。这意味着每个节点都有自己的内存，不能直接从其他节点访问，因此这种机器也被称为分布式内存机（DMM）。单个全局内存无法扩展到这些计算机的大小。14第一章。简介不幸的是，要实现如此高的计算速度，以高效的方式对如此高的计算机进行编程就更加复杂了。仅仅购买一台更快的计算机是不够的，它上运行的程序必须适应特定的机器以获得最大的速度。1.1动机程序套件tmLQCD[3]是一个可用于这种晶格QCD模拟的软件。它是由ETMC，一个高能物理研究合作组织编写的。与几乎任何软件一样，某些部分的执行频率高于其他部分;执行频率最高的代码称为热点、关键部分或内核。tmLQCD已经包含了IBM BlueGene/Q的优化Blue Gene/P的继任者于2012年底推出，命名为Blue Gene/Q。当然，随着一些计算中心用新一代机器替换他们的Blue Gene/P机器，人们也希望支持这种架构为了继续快速光栅QCD模拟，内核必须针对新机器进行优化。普通的C版本也可以工作，但相对较慢，因为它没有使用许多使Blue Gene/Q快速的硬件功能。与Blue Gene/P相比，新机器具有一些需要考虑的不同特性，以及上一代产品中不存在的新特性。将优化的内核直接转换到新的体系结构不会产生最佳性能。为了获得最佳性能，即使数据存储在内存中的方式也需要更改。不幸的是，tmLQCD中的许多代码采用了特定的数据存储方式。更改它，要求重写这些部分，即使它们不属于热点。一些优化是矛盾的。一个可以优化接入模式或减少所需带宽，但通常不能同时进行。人们也可以尝试在优化目标之间找到一个权衡，但在最快的程序中选择哪个结果是很难预测的。通常只有一种方法可以找到答案：实现优化并测量其执行时间。哪个版本更快也可能取决于程序的输入。在Lattice QCD的情况下，网格的大小对瓶颈（速度限制因素）的大小有很大的影响，因此为特定情况找到优化的最佳选择是一项涉及试错的大任务，这是本文所要解决的问题。对于每个实验，必须编写一些代码并重新编写。通常，在软件工程中，不同的优化方面将被抽象到不同的层中，以便它们中的每一个都可以被独立地修改。对于速度优化，这是不可行的，因为任何这样的抽象都会减慢应用程序的速度。如果幸运的话，编译器可以删除编译程序中的抽象，例如通过内联函数。这适用于相对简单的情况，但通常编译器会让抽象远离破坏一些特殊情况和/或限制编译时间的恐惧。 在极端的情况下，一个人甚至必须手动编写汇编代码，因为编译器没有找到他心目中的机器代码。Hence，必须编写优化的热点 以密切反映机器代码的输出这意味着在尝试不同的优化时需要大量重复的工作。是否要更改迭代顺序？您必须重写所有热点循环。 这是不幸的，因为存在一个数学模型，可以与许多类这样的重新排序。它的研究团体称之为多面体模型。一些编译器使用此模型进行循环转换，但它们的实现通常缺乏成熟度，并且对程序员来说，编译器正在做什么或为什么不做是不可见的。专用的源代码到源代码转换工具看起来更成功，部分原因是用户拥有更多的控制权，并且平均更好地理解工具的预期用途。多面体模型背后的数学也可以应用于元素排序1.2. 本文贡献15内存，这是主流编译器还没有做的事情。在进行这种速度优化时，两者的组合可能会占用程序员的大量资源。相同内核的不同版本变得不必要，取而代之的是编译器不知道平台的最佳重新排序，或者由程序员选择的每个平台的注释。它降低了现有代码的维护成本，因为需要维护的代码更少。其他编译器优化已经发生了这样的演变。例如，在C语言的早期，避免函数调用开销的唯一方法是将函数声明为宏预处理器。如果用内联关键字注释，或者如果编译器认为这样做是有利的，今天的编译器可以内联函数。一般建议将此决定留给编译器，以避免过早的优化。实际上，假设在没有测量的情况下进行特定的重新排序是过早的优化，特别是如果这需要重写非热点部件。能够应用重新排序的编译器鼓励尝试不同的程序转换。1.2本论文本文探讨了并行化的两种主要方法和不涉及硬件更改的通用程序速度2：手动优化源代码和编译器优化。任何优化都可以在源代码中实现-如果需要的话，可以向下到程序但是编译器中的新转换必须适用于一般情况，确保任何完善的源代码都不会改变其意义，并且尽可能地不会比没有这种更改的情况慢。这样做的好处是，转换可以自动应用于任何程序使用案例是Blue Gene/Q超级计算机上的Lattice QCD。首先，我们更改了tmLQCD程序套件的源代码，以寻找此架构的最佳转换。利用这个实验，我们修改了一个编译器，使其能够自动应用其中的一些优化。以下列表描述了论文第一部分的工作。• 将蓝色基因/Q优化版本的内核添加到tmLQCD• 尝试使用不同的内存布局• 优化由IBM的IBM XL编译器[5]（XLC）编译器生成的程序集代码，特别• 减少多线程开销• 使用低级硬件命令实现节点间通信（消息单元系统编程接口（MUSPI）代替消息传递接口（MPI））在第二部分中，贡献了以下项目。• 内存中和分布式内存节点• 实现一个名为Mollyto theClang的扩展[6]编译器，执行这样的转换毫无疑问，效率的圣杯会导致滥用。程序员浪费了大量的时间来思考或担心他们程序中非关键部分的速度，这些对效率的攻击实际上对调试和维护有很大的负面影响。我们应该忘记小效率，97%的时间都在说：过早的优化是万恶之源。然而，我们不应该在这关键的3%中浪费我们的机会。本文中的优化是在提高程序执行速度的意义上使用的。 这不是指找到可能的最快（最优）程序16第一章。简介• Molly所做转换的评估蓝基因/Q 优化版本 的tmLQCD 不是在蓝 基因/Q 上实现晶 格QCD 的最快可 能（optimal）版本。此外，莫莉是原型与这个单一的目的在心中。它不是任何程序的现成实现，但可以通过这种方式进行扩展。1.3论文结构遵循两种不同的优化方法，本文由两部分组成。第一部分从第19页开始，涉及BlueGene/Q计算机的tmLQCD手动优化第二部分在第91页及以后是关于Molly的实现，Molly是使用多面体模型进行数据布局转换的编译器扩展。第一部分从第二章中对晶格QCD背后的理论物理学的简要概述开始。第3章解释了Blue Gene/Q平台及其对程序优化很重要的硬件细节，第4章介绍了应用于tmLQCD的各种优化使用不同优化组合的实验结果在第5章中给出。本部分在第6章中以摘要、更多优化想法和相关工作结束。第二部分从第7章介绍多面体模型开始。下面的章节介绍了如何将相同的理论应用于分布式内存计算机的本地内存中和节点之间的数据重新排序。第9章介绍了它是如何实现的Molly，Clang编译器的扩展。Molly优化程序性能如何的实验结果将在第10章中展示。论文最后总结了这一部分，其他研究人员的类似工作，以及在第11章改进莫莉的想法。17第一部分针对Blue Gene/Q的