论文要获得的等级格勒诺布尔大学博士专业：计算机科学提交人卢卡·斯坦尼希奇博士论文由Jean-François Méhaut指导由Arnaud LEGRAND共同导演在格勒诺布尔计算机科学实验室LIG编制以及一种用于设计和执行基于任务的动态科学模拟的论文于2015年10月30日在评审团面前公开答辩，评审团成员包括：M.马丁·昆森雷恩高等师范学校正教授，校长雪莉·艾克斯夫人。LI劳伦斯伯克利国家实验室高级科学家，报告员M.雷蒙德·纳米斯特波尔多大学/波尔多计算机科学研究实验室正教授，报告员M.格里戈里·富尔辛研究科学家，Inria Saclay，审查员M.让-弗朗索瓦·梅奥特格勒诺布尔大学/格勒诺布尔计算机科学实验室正教授M.阿诺德·勒格朗CNRS/格勒诺布尔计算机实验室研究科学家我确认书首先，我想感谢陪审团成员同意成为这个委员会的一部分。他们为我提供了非常有用的意见、问题和对这项工作未来方向的建议。我想感谢我的家人和朋友，他们支持我，从很远的地方来到论文答辩。我还要感谢我在格勒诺布尔的朋友们，特别是本和纳塔，是他们让我这三年的博士生涯成为我一生中最美好的时光之一。我永远不会忘记令人难以置信的愉快和激励周围，由所有成员和前成员的梅斯卡尔，莫伊斯，纳米西姆/科西嘉队，我的工作。我特别要感谢Brice VIDEAU，他给了我很多技术和研究相关的东西，他经常鼓励我。特别感谢Jean-François Méhaut，他在最需要的时候总是在那里，他的建议帮助我总是走在正确的轨道上。最后但并非最不重要的是，我要感谢Arnaud LEGRAND，他不可思议的精力、性格和知识激励和指导了我从论文开始到结束。我觉得很荣幸能得到他这么多的时间，这些年来一直在他身边工作。ii.iii.摘要在过去的十年里，高性能计算系统的发展发生了急剧的转变。由于现代平台的巨大功耗，处理器的小型化和频率扩展已经达到了极限。能源限制迫使硬件制造商开发替代计算机体系结构解决方案，以满足科学家和社会对性能日益增长的需求。然而，有效地对如此多样的平台进行编程并充分利用它们所提供的大量不同资源的潜力是极其具有挑战性的。以前设计高性能应用程序的主导趋势是基于提供许多优化机会的大型单片代码，这已经变得越来越难以应用，因为实现和维护如此复杂的代码非常困难。因此，应用程序开发人员越来越多地考虑模块化方法和动态应用程序执行。一种流行的方法是在独立于硬件体系结构的高级别上实现应用程序，作为任务的有向非循环图，每个任务对应于每个体系结构的仔细优化的计算内核。然后可以使用运行时系统来动态地调度不同计算资源上的任务。开发这样的解决方案并确保其在各种设置中的良好性能始终是一项挑战。由于硬件的高度复杂性、在机器上执行的操作的持续时间的可变性以及因此，需要系统的和可重复的方法来进行这样的研究，以及可靠的性能评估技术来研究这些复杂系统。在本文中，我们证明了使用仿真对动态HPC应用进行干净、一致、可重复的研究是可能的。我们提出了一个独特的工作流程，基于两个众所周知且广泛使用的工具，Git和Org-mode，用于进行可重复的实验研究。这个简单的工作流程允许务实地解决问题，如来源跟踪和数据分析复制。我们对动态HPC应用程序性能评估的贡献包括设计和验证StarPU的粗粒度混合仿真/仿真，StarPU是一种基于SimGrid的混合架构动态任务运行时，SimGrid是一种用于分布式系统的多功能模拟器。本文介绍了该工具如何在广泛的异构机器上，针对两类不同的程序、密集和稀疏的线性代数应用，实现对本机执行的忠实性能预测，这很好地代表了实际的科学应用。iv.V摘要在过去的十年里，高性能计算被迫以完全不同的方式由于不合理的功耗，处理器的小型化和频率的增加已经达到了极限。这种能量限制导致硬件制造商开发了许多替代的本机体系结构，以满足科学界对计算能力不断增长的需求。然而，对如此多样化的平台进行有效编程并充分利用它们提供的资源是极其困难的。由于难以实现、可移植性和维护，传统的高性能应用程序设计方法依赖于提供大量优化机会的单片代码，这使得应用变得越来越困难。因此，这类应用程序的开发人员越来越普遍地考虑模块化方法和各种组件的动态执行。 一种流行的方法是 在相对较高的级别上实现这些应用，而不考虑硬件体系结构，依赖于基于任务图概念的范例，其中每个任务对应于针对每个目标体系结构仔细优化的计算内核。然后，可以使用运行时系统在可用的各种计算资源上动态地调度这些任务。然而，确保实际上，由于硬件的高度复杂性、计算执行时间的可变性和任务调度的动态性，应用程序的执行是不确定的，并且评估这些系统的性能是非常微妙的。因此，需要一种系统的、严格的和可重复的在本论文中，我们证明了使用模拟以可靠、一致和可重复的方式研究这种动态应用的性能是可能的。首先，我们提出了一种基于我们社区中常用的两种工具Git和Org-mode的原创工作方法，并允许实现可重复的实验研究。这种简单的方法可以实用地解决诸如跟踪实验的来源或复制实验数据的分析之类的问题。第二步，我们通过设计和验证StarPU的大粒度hy-brid仿真/仿真来帮助评估动态应用程序的性能，StarPU是一个使用任务图范例的动态运行时，特别适合混合架构的操作。 执行此模拟使用SimGrid，一种通用的分布式系统模拟器。我们展示了我们的方法如何在各种异构机器上实现可靠的实际运行时性能预测。我们将我们的方法应用于两类不同的程序，密集和空心线性代数应用六七内容物1引言11.1贡献21.1.1开展可重复研究的方法41.1.2模拟动态HPC应用51.2论文组织62 背景72.1HPC应用程序开发人员面临的2.1.1HPC应用程序72.1.2HPC 8中使用的不同体系结构2.1.3利用机器资源92.1.4动态基于任务的运行时92.1.5线性代数的应用12密集线性代数12稀疏线性代数132.2HPC应用程序开发人员面临的2.3结论153 相关工作173.1可重复研究17代码和数据可访问性19平台可访问性18设置环境20进行实验20来源追踪20文档20可扩展性20可复制分析21结论213.2绩效评估和模拟213.2.1不同的模拟方法21仿真21循环精确模拟22粗粒模拟22混合方法233.2.2模拟资源23通信建模CPU建模GPU建模3.2.3模拟应用程序25七模拟MPI应用程序25模拟基于任务的运行时273.2.4SimGrid：模拟大型异构系统的工具包4 方法论314.1基于Git和Org模式的工作流334.1.1Git分支结构344.1.2使用组织模式改进可重复性研究环境捕获35实验室笔记本36使用文字编程进行实验374.1.3Git工作流程在行动38使用Git 38复制实验40修复代码41进行横向分析41第四十一章写作重复4.2发布结果424.2.1使用figshare托管的部分开放方法4.2.2完全开放的方法与公共Git托管4.3结论435在SimGrid 45上移植StarPU5.1为仿真选择候选运行时5.2将StarPU移植到SimGrid 465.3对StarPU运行时47进行5.3.1同步475.3.2内存分配475.3.3数据传输的提交5.3.4计划开销495.3.5运行时操作持续时间5.4通信建模5.4.1PCI总线型号50FatpipeModel 51完整图形模型51TreelikeModel 515.4.2基于校准的模型5.5建模计算52建模参数相关内核54使用复杂代码对内核进行建模55简化机器型号的限制5.6结论556 密集线性代数应用6.1实验设置576.1.1应用程序576.1.258台机器6.2内核可变性建模6.2.1分析内核持续时间分布6.2.2使用直方图近似分布636.3评估方法65七6.4模型需要仔细调整的地方666.4.1GPU内存限制666.4.2GPU/CUDA版本686.4.3复杂机器的复杂通信模型6.5混合动力机器的准确性能预测6.6同时使用CPU和GPU进行计算6.7模型断裂且难以适应的地方：NUM机器726.8通过这种方法启用的典型研究6.8.1学习计划器746.8.2研究假设平台757稀疏线性代数应用7.1qr_mumps，一个基于任务的多前端求解器777.2将qr_mumps移植到SimGrid 79的顶部7.3实验设置1007.4建模qr_mumps内核807.4.1可忽略内核827.4.2参数依赖内核82模拟857.4.3矩阵依赖内核857.4.4内核可变性的计算7.5评估方法867.6质量评估887.6.1蚂蚁机器上的评估7.6.2在Riri机器907.7通过这种方法启用的典型研究927.7.1存储器消耗927.7.2外推938 结论和今后的工作958.1进行可重复研究的方法95当前的局限性和未来的工作8.2模拟动态HPC应用程序978.2.1当前的限制98建模内存距离98建模竞争98次优本机执行的模拟99通用性模型8.2.2未来的工作101扩展到更大的平台101控制模拟质量102打开新视野102参考文献105A.1出版物105A.1.1国际同行评审期刊105A.1.2国际同行审查会议记录105A.1.3会议和讲习班上的简短论文105A.1.4硕士论文105A.2参考书目106七B补充图119内容内容x十一图列表1.1图表说明了我们工作中与方法学和绩效评估相关的贡献（灰色）。在本文中，对于我们工作的模拟方面，我们只考虑应用程序依赖于运行时的情况。我们的工作流程因此，进行可重复研究是完全一般性的2.1DAG的一个例子：5×5矩阵的Tiled Cholesky因式分解的任务图块尺寸960，在StarPU 10中实现2.2比较Amestoy等人在[ADLL01]中所做的MUMPS和SuperLU稀疏线性求解器的不同调度算法。 MUMPS具有非常不规则的模式，这使得它非常适合使用基于任务的动态运行时系统..................................................................................................................................................。3.1理想情况下，实验者将跟踪为进行研究而做出的整个决策集，就像用于进行实验和执行分析的所有代码一样。灵感来自罗杰·D.Peng等人。[............................................................... 18]第十八话4.1ARM Snowball上的再现性问题：4个相同输入参数表现不同的连续实验;检测到每个阵列大小的42次重复Boxplots显示每个单个实验中没有噪声4.2建议的Git分支方案有4种不同的分支类型4.3使用两台机器的不同阶段的典型Git实验工作流4.4从某个提交开始重新启动或重新启动实验4.5处理实验期间发生的源更改415.1实现模拟模式需要对StarPU进行一些代码更改。这个简单的示例说明了SimGrid（第2-14行）和Native（第16-25行）。执行StarPU条件等待的模式......................................................................................................5.2通信和拓扑建模替代方案。在原始建模中，使用单个链路，并且通信不相互干扰。实用的完整图建模允许解释通信的异构性和PCI总线施加的全局带宽限制复杂机器体系结构对更复杂模型的需求..........................................................................................5.3使用类似树模型生成的Idgraf平台描述文件的摘录。此片段结束了GPU6和GPU6之间通信时使用的路由。使用CUDA 52的GPU25.4Idgraf机器的架构，具有12个内核，分布在2个NUM节点、8个GPU及其互连上...............6.1标题Cholesky因式分解586.2对于密集的线性代数应用，大部分处理能力由GPU提供这些图描述了Cholesky应用程序在Mi-rage机器上的性能（见表6.1）。在限制时清楚地了解这些性能到CPU资源（8个内核）如图6.17所示（4+4个内核）59图列表图列表十二6.3Haugen等人在[HKY+ 14]中进行的内核持续时间分布分析正态分布非常精确地近似样本分布。 然而，我们认为这仅适用于单核CPU.....................606.4GEMM内核在GPU上的持续时间为单个72，000×72，000Cholesky因式分解，以时间序列表示。大多数值约为2.84微秒，但有一个有意义的更高持续时间的数字，如井61。6.5单72，000×72，000Cholesky因式分解下GPU上GEMM内核持续时间的分布上图显示了为所有观测构建的分布，而下图则为两个单独的观测组重新构建，具体取决于ING在其持续时间值上626.6用两种直方图近似GEMM持续时间6.7StarPU对简化用例的模拟的初步结果已经非常准确。 需要更复杂的场景更复杂的模型.6.8说明建模运行时的影响运行时的粗心建模可能在某些情况下是完全无害的，在其他情况下则会导致领导不善。6.9使用cudaMemcpy2D传输3，600 KB的时间取决于矩阵的音高686.10 使用不同建模假设的汉尼拔（QuadroFX5800 GPU）LU应用的...........................................性能686.11 模拟像Idgraf这样具有复杂架构的机器（见图5.4）需要更复杂的模型。..........................6.12 验证模拟器在各种设置下的预测能力6.13 将Cholesky应用程序的执行跟踪（顶部的本机执行与底部的模拟执行）与Conan机器上的72，000×72，000阵列进行比较，但仅使用GPU资源来处理应用.................................... 程序716.14 使用不同资源说明Cholesky应用程序的仿真准确性幻影机器716.15 比较Cholesky应用程序与Mirage机器上使用8个内核和3个GPU作为工作线程的72，000×72，000阵列的运行时添加8个内核，与2015年获得的性能相比，性能提高了约20%。图6.13716.16 比较Cholesky应用程序与Mirage机器上使用8个内核和3个GPU作为工作线程的48，000×48，000阵列的运行时由于未使用英特尔MKL库，因此在CPUs上运行内核需要很长时间，尽管存在仿真预测仍然非常精确726.17 说明在两个NUMA节点上使用8个内核时部署的影响幻影机736.18 Cholesky 在 大 型 NUMA Idchire 机 器 上 使 用 32 ， 000×32 ， 000 矩 阵 （ 块 大 小320×320）的模拟预测对于少量的内核是准确的，但规模很差。原因是内存是共享的，而模型是不考虑各种影响NUMA736.19 Cholesky on Attila：研究不同调度程序的影响7.1[ABGL14]的顺序版本（左）和相应的STF版本（右）多面QR因式分解与前78矩阵的1D分割7.2典型消除树：每个节点对应于前端和结果树它是从底部到顶部的。为了通过管理大量的前端来减少曲面开销，对子树进行了修剪和聚合以进行优化以灰色78表示的顺序任务（Do_subtree）7.3处理前端需要一系列复杂的面板和更新任务，这些任务由楼梯间结构引起。这些操作之间的依赖关系表示为STF代码导致由运行时系统动态调度的细粒度DAG78图列表图列表十三7.4分解e18矩阵时qr_mumps内核持续时间的分布（见表7.2）。其他矩阵的分布形状大多数内核具有（难以建模）多模态分布817.5面板内核的持续时间作为e18矩阵的时间序列。这些模式表明，这种持续时间取决于贯穿整个过程的特定参数。执行申请817.6面板内核84的线性模型分析7.7自动生成的代码，用于计算面板和更新内核的持续时间。85.7.8Makespans在8个CPU内核的蚂蚁机上运行，适用于10个不同的阵列。 由于因式分解超过了Fourmi机器的RAM内存容量，因此未显示3个最大矩阵的本机结果，因为它们太长7.98个CPU内核Fourmi88的甘特图比较7.10 比较8个CPU内核上的内核分布持续时间7.11 比较面板作为8个CPU内核蚂蚁机上的时间序列。 颜色与任务ID.........................................907.12 在使用10或40个CPU内核的Riri机器上的结果。 使用单个节点时 (10由于更复杂和打包的处理器架构，结果匹配得相对较好，但与Fourmi机器的匹配情况较差。当使用4个节点（40个内核）时，结果仍在合理的限制范围内，尽管NUMA影响917.13 记忆 消耗 进化。The 蓝色 和 红色 零件 对应 至 TheDo_subtree和激活贡献927.14 在100和400个CPU内核上外推e18矩阵的结果8. 1EIIN TIONTREFORCA T_EARS_4MATRIX，ROTTDOR90D G REE该图的平衡性非常差，具有类似comb的结构，具有大量的Do_subtree内核，显示为灰色节点................................................................................................................................................100B.1运行实验和自动捕获元数据的脚本B.2包含元数据和实验结果的执行输出B.3实验室笔记本的文档部分B.4关于存储在实验室笔记本中的所有实验结果的注释B.5直接从实验室笔记本进行实验B.6组织模式文章包含文本和分析代码125图列表图列表十四十五表列表2.1在TOP500排行榜中排名第一，说明了用于构建现代HPC平台的体系结构的多样性5.1运行时操作的典型持续时间6.1用于密集线性代数实验的机器597.1稀疏线性代数实验中7.2稀疏线性代数实验中7.3面板内核83的线性回归7.4更新内核85的线性回归7.5基于e18矩阵的每个内核在Fourmi上的建模总结（参见第 7.3 更多详情....................... 86.十六1第一章简介计算机已经成为许多科学领域不可或缺的研究工具，如物理学、医学、工程学等。这些机器每秒可以执行数万亿次运算，因此执行的计算远远超出了人类手动所能完成的。然而，即使是如此巨大的计算能力也不足以解决一些计算难题。在粒子物理学、地震或天文学中执行模拟的程序都研究非常大的系统，并对大量数据进行大量计算。高性能计算（HPC）是一门计算机科学学科，它关注这些应用程序组以及运行它们所需的平台。在过去的50年里，高功率机器，通常被称为超级计算机，经历了极其快速的发展由于微芯片的小型化和频率缩放，计算机的性能大约每18个月翻一番。然而，由于技术限制，即能源消耗和热量，这一趋势在十年前就停止了。 为了追求性能增长，制造商开始生产每个处理器具有多个内核的计算机，并开始增加加速器单元。这允许将问题分解为可以并行执行的较小问题。因此，现代HPC机器由数千到数百万个内核组成，通过快速网络互连HPC社区维护了世界上最快的500台计算机的列表：TOP500。此列表根据使用LINPACK基准测试[Don88]测量的已完成的最大FLOPS（每秒浮点运算数）对计算机进行排名。迄今为止最快的超级计算机是中国的"欧共体-2"，拥有3，120，000个处理器内核，峰值性能约为33PetaFlops（每秒10，16次浮点如果之前的趋势继续下去，预计到2020年将达到1个ExaFlops（每秒10个18个浮点实现如此高性能的主要挑战是能量限制。超级计算机和数据中心已经像一个小城市一样消耗了大量的电力，为它们供电几年的价格与组成它们的硬件的初始价格相同。据估计，未来最快的计算机的功率预算不应超过20兆瓦。这需要50 GFLOPS/W的性能效率，远远高于L-CSC计算机[Greb]实现的5.2 GFLOPS/W的最大电流。 Hence，HPC中有一个巨大的节能计算运动，它建立了一个新的超级计算机排名。 绿色500强的组织结构与TOP500相似，但计算机除外。 根据其能源效率进行排名。TOP500和Green500榜单上硬件体系结构的广泛多样性及其各自的复杂性清楚地表明，在体系结构方面尚未达成共识。未来的超级计算机。例如，绿色500强中排名前三的机器都使用了不同供应商生产的不同设计的加速器[Greb]。技术发展非常快，很难预测应用程序开发人员可以使用什么样的资源。实现可跨各种复杂平台移植性能的
我的内容管理
展开
