高性能计算中数值线性代数的自动代码生成方法引用此版本：伊恩·马斯里亚高性能计算中数值线性代数的代码自动生成方法硬件架构[cs.AR]。Université ParisSaclay（COmUE），2016.英语NNT：2016SACLS285。电话：01395496HAL Id：tel-01395496https://theses.hal.science/tel-013954962016年11月10日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaireNNT：2016SACLS285Thèse deDOCTOR aTde预备UnIVERSITÉ 南帕里斯Ecole Doctorale N1580Sciences et technologies deparM. 伊恩·马斯里亚高级性能计算中代数线性数值代码自动生成方法Thèse présentée et soutenue à Gif-Sur-Yvette，le 26 Septembre2016.评审团组成：M.埃马纽埃尔·沙尤Professeur(Pr陪审团成员）皮埃尔与玛丽·居里大学M.保罗·比蒂内西Professeur（特别报告员）亚琛工业大学M.大卫·希尔Professeur（特别报告员）布莱斯·帕斯卡大学M.弗雷德里克·马古莱斯Professeur（审查员）巴黎中央学校M.马克·巴布兰Professeur（Directeur de thèse）南巴黎大学M.乔尔·法尔科梅尔特雷德孔费埃（Co-Directeur dethèse）南巴黎大学标题：Méthodes de génération automatique de code appliquées à关键词：programmation générique，DSEL，programmation générative，C++，algèbre linéaire，GPU简历：在所有的信息系统中，都有类似的架构，智能手机Programmer efficacement cesarchitectures en fonetrium des applications requiert un ef- fort pluridiculinaire portant surles langages dedies（Domain Specific Languages-DSL），les techniques de génération decode et在此基础上，我们提出了一种新的编程方法，该方法考虑了混合体系结构的特点和矩阵的 特 性 ， 从 而 产 生 了 一 个 稠 密 代 数 线 性 方 程 组 的 通 用 求 解 器 Notre modèle deprogrammation transferts explicites et implicites entre un processeur （ CPU ） et unprocesseur graphique qui peut être généraliste（GPU）ou intégré（IGP）.在测试GPU的时候，它对计算的高性能非常重要，它在计算平台上的使用非常重要 Une architecture récentetelle que l'IGP requiert des connaissances supplémentaires pouvoir être programméeefficacement. Notre métho-dologie a pour but de quertifier le déception sur ces architecturesparallèles en utilisant des outils de programmation haut niveau. 首先，我们要根据实际书目中不存在的半正规方程，提出一种混合精确的数学求解方法Nous avons par la suite étendu nos travaux à un modèle de programmation multi-étape（“multi-stage”）pour résoudre les problèmes Nous utilisons cette technique pourgénérer automatiquement du code pour accélérateur à partir d'un code effectuant desopérations point par point ou utilisant des squelettes algorithmiques.我们使用多个磁带确保通用代码的类型正确。 我们相信我们的方法适用于其他架构和算法。在一个名为NT2的计算书中，这些被忽略的例程是完整的。最后，我们的montrons评论la programmation haut niveau peut être appliquée à descalculs groupés et des contractions de tenseurs。在C++现代（C++-14）的基础上，我们解释了一种利用编程技术的容器模型。此外，我们还利用SIMD指令实现了一个最优化的矩阵产品，用于小尾巴黎萨克雷大学Espace Technologique / Immeuble DiscoveryRoute de题目：自动代码生成方法在高性能计算关键词：泛型编程，DSEL，生成式编程，C++，线性代数，GPU翻译后摘要：在今天的计算机体系结构中的并行性是无处不在的，无论是在超级计算机，工作站或便携式设备，如智能手机。有效地利用这些系统的特定应用需要多学科的努力，涉及领域特定的语言（DSL），代码生成和优化技术和应用程序特定的数值算法。在这篇博士论文中，我们提出了一种高级编程的方法，考虑到异构体系结构的特点和矩阵的属性，建立一个通用的稠密线性代数求解器。我们的编程模型支持通用图形处理单元（GPGPU）和集成图形处理器（IGP）之间的隐式或显式由于GPU已成为高性能计算的资产，因此将其用于通用求解器是一个重要问题。最近的架构，如IGP，也需要进一步的知识，以有效地编程。 我们的方法的目的是通过使用高层次的编程技术，在并行架构上简化开发。作为一个例子，我们开发了一个最小二乘求解器的基础上半正规方程的混合精度，不能在目前的图书馆。该求解器实现了与其他混合精度算法类似的性能我们将我们的方法扩展到一个新的多级编程模型，该模型描述了CPU和GPU编程模型之间的互操作性问题我们的多级ap-proach是用来自动生成GPU代码的基于CPU的元素明智的表达式和并行骨架，同时允许类型安全的程序生成。我们说明，这项工作可以应用到最近的架构和算法。产生的代码已被并入一个名为NT2的C++库最后，我们研究如何将高级编程技术应用于批量计算和张量收缩。我们首先解释如何使用现代C++-14编程技术设计一个简单的数据容器然后，我们研究了批处理计算，内存局部性和代码向量化的问题，实现了高度优化的矩阵矩阵产品的小尺寸使用SIMD指令。通过结合高层次的编程approach和先进的并行编程技术，我们表明，我们可以超越国家的最先进的数值库。巴黎萨克雷大学Espace Technologique / Immeuble DiscoveryRoute de目录介绍21使数值库适应并行体系结构的问题61.1科学计算的高级编程。. . . . . . . . . - 是的71.2求解稠密线性系统- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的81.2.1 LU分解 . - 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的91.2.2 QR分解。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的111.2.3 LAPACK和MAGMA中的求解器。- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的121.2.3.1通用求解器。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的131.2.3.2迭代细化。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的141.2.3.3混合精度算法. - 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的141.3架构：设计与进化- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的151.3.1 SIMD扩展。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的151.3.2多核系统。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的161.3.3图形处理单元（GPU）。 . . . . . . . . . . . . . - 是的171.3.4加速处理单元。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的191.4编程工具和技术。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的201.4.1低级编程工具。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的211.4.1.1 SIMD支持。 . . . . . . . . . . . . . . . . . . . .211.4.1.2多核支持- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的231.4.1.3加速器支持。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的241.4.2领域特定语言。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的241.4.3特定领域嵌入式语言。 . . . . . . . . . . - 是的251.4.4多阶段规划。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的261.5考虑语言和库。 . . . . . . . . . . . . . . . . . .26- 是的1.5.1 C++语言和编程技巧。- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的261.5.2 NT2库。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的271.6结论。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的292稠密线性代数302.1相关工作- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的312.2用于设计数值库的生成式编程。- 是的- 是的- 是的- 是的- 是的332.2.1基于配置空间的优化方法。. - 是的332.2.2软件开发中的生成式编程。- 是的- 是的- 是的- 是的- 是的- 是的342.2.3主动库的领域工程方法。- 是的- 是的- 是的- 是的- 是的- 是的- 是的342.3构建CPU/GPU编程模型。 . . . . . . . . . . . . -是的362.3.1GPU容器概念。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的362.3.2在NT中的集成2. - 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的362.4线性代数求解器的应用。 . . . . . . . . . . . . . . . .- 是的392.4.1线性系统解算器。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的39目录2.4.2混合计算...............................................................................................的存储器管理422.4.3应用：最小二乘求解器.......................................................................432.5结论........................................................................................................................3在C++中为GPGPU进行523.1相关工作............................................................................................................533.2C++....................................................................................................................56中的多阶段编程3.2.1设计多阶段软件...................................................................................563.2.2C++.......................................................................................................57中的多阶段编程3.2.3NT2...............................................................................................................................................58多阶段编程工具3.3NT2................................................................................................................................................................ 的软件实现593.4实验....................................................................................................................643.4.1布莱克-斯科尔斯核..............................................................................653.4.2Linsolve内核........................................................................................683.5结论....................................................................................................................694应用于批量计算和张量收缩704.1数字库................................................................................................................中的张量714.2应用和挑战........................................................................................................4.3集装箱概念........................................................................................................734.3.1 C++11/14特性.........................................................................................744.3.2开发张量接口............................................................................................794.4优化小矩阵矩阵产品........................................................................................814.4.1业绩计量...............................................................................................4.4.2数据访问优化和循环转换技术........................................................... 824.4.3寄存器数据重用和位置.......................................................................834.4.4军事进步......................................................................................................844.4.5多线程................................................................................................... 的影响864.4.6NUMA插槽和内存位置......................................................................的影响874.4.7ARM处理器..........................................................................................88的应用4.4.8GPU批处理GEMM............................................................................. 88的高效包装器4.5结论....................................................................................................................90结论与展望92Bibliography参考书目94图目录1.1SIMD概念......................................................................................................... 151.2多核概念............................................................................................................161.3NUMA概念...................................................................................................... 171.4基于GPU Kepler的架构.................................................................................. 181.5GPU................................................................................................................... 的工作流程191.6IGP架构.............................................................................................................201.7零拷贝IGP.........................................................................................................21的工作流程1.8英特尔................................................................................................................1.9NT2................................................................................................................................................................中的表达式模板282.1语言...........................................................................................................................的抽象/效率权衡322.2基于NT2骨架的生成过程.................................................................................概述352.3对称系统............................................................................................................41的生成处理的示例2.4LAPACK/MAGMA例程与通过NT2生成的一般稠密线性系统解.............43的代码2.5CPU................................................................................................................... 47上生成的代码的性能结果2.6GPU................................................................................................................... 50上生成的代码的性能结果2.7Tegra X1GPU................................................................................................... 50上的性能结果3.1NT2和类似库.....................................................................................................553.2设备代码生成....................................................................................................的两阶段编译583.3三元核变换AST................................................................................................603.4布莱克和斯科尔斯的表现比较（毫秒）........................................................663.5Tegra X1与NT2的性能比较（时间单位：ms）............................................673.6NT2线性求解的性能比较（以Gflop/s为单位）.......................................... 694.1加载指令............................................................................................................数量834.2存储指令............................................................................................................数834.3CPU指令总数................................................................................................... 844.4CPU核心........................................................................................................... 数量的影响854.5NUMA内存管理.............................................................................................. 的影响874.6在........................................................................................................................88 CPU上实现矩阵-矩阵乘法的实验结果4.7矩阵-矩阵乘法在Tegra上的实验结果X1.......................................................................................................................894.8K40.....................................................................................................................89上的GPU性能介绍近年来，架构和编程语言经历了重大的变化和多样化。对更多计算能力和更多通用软件的持续需求是这些变化背后的驱动力求解线性方程组Ax=b是导致大量研究的许多计算应用的一部分稠密线性代数的发展与计算机语言和体系结构的发展齐头并进随着多核处理器和加速器的发展，高性能人们可以有把握地预测，这种趋势将继续下去，因为当前的架构正处于十字路口，光刻工艺已达到极限。与此同时，计算机语言已经开始多样化，重点是高级语言概念和函数式编程范式。最近的语言，如Scala，Dotty，Rust或现代C++是这个新方向的主要例子这些语言也开始成为高性能计算（HPC）的标准，以开发可扩展和强大的软件。在这篇博士论文中，我们提出了一种高级编程的方法，考虑到异构体系结构和算法属性的特点，建立数值库。我们在整个工作中考虑的问题与异构体系结构的软件设计和优化有关历史上，软件一直是围绕解决特定体系结构的问题而设计的，这限制了可移植性和重用性.我们提出了一种方法来开发通用接口，支持架构扩展。由于编程模型可以根据硬件的不同而变化很大，因此能够在必要时给出规范，并适当地对硬件进行分类以实现代码重用是必不可少的。这需要高级编程技术，而这些技术在每种语言中都找 不 到 。 领 域 特 定 嵌 入 式 语 言 （ Domain Specific Embedded Languages ，DSEL）的概念依赖于一种通用编程语言，这种语言足够灵活和表达能力，可以开发具有明确语法的这种技术已知用于上述语言中。在我们的工作中，我们采用这样的编程技术来设计一个密集的线性系统的架构感知求解器。生成的代码已被纳入一个名为NT21的C++库。我们还考虑了批量计算和张量收缩的问题。这些工作是在NT2库之外完成的详细说明了如何在不依赖现有软件的情况下开发一个简单的高级存储器容器然后，我们开发了一个优化的矩阵矩阵产品的小尺寸使用的调整方法。在我们的基准测试中，GPU上的计算使用IEEE 754兼容模式[138]进行算术运算，并激活CUDA ECC。1NT2可从http://github.com/jfalcou/nt2获得3这份手稿的结构如下：在第一章中，我们介绍了我们工作的背景。首先，我们考虑一些数字库的演变，并描述架构和编程语言如何其次，我们讨论了求解稠密线性方程组的主要算法，以及如何在最流行的HPC语言中使用它们。然后，我们给出了一个一般性的描述，目前的架构和主要的编程工具和技术。这包括需要专业知识来正确编程硬件的低级架构工具和对此类问题进行抽象的高级编程技术然后，我们介绍了我们在大多数工作中使用的编程语言和库。在第二章中，我们提出了一个高层次程序设计框架的设计方法我们首先给出一个软件上下文，因为有几种方法可以解决这样的问题。然后，我们提出了我们的CPU/GPU编程模型的代码生成技术然后，该模型将能够开发一个密集的线性求解器，可以支持混合架构。我们说明了我们的方法与最小二乘求解器的基础上半正规方程的CPU，GPU和集成图形处理器（IGP），无法找到在国家的最先进的图书馆。在第三章中，我们扩展了第二章中描述的工作，提出了一种多阶段规划方法.我们给出了相关工作的详细背景和可用的C++库，以解决代码的可移植性和支持问题。然后，我们解释了我们在C++中的多阶段方法背后的过程，以及我们如何将其实现到NT2库中。我们测试我们的方法与实验上的GPU和IGP的布莱克斯科尔斯算法，并通过应用我们的多阶段的方法在第2章中描述的工作在第4章中，我们研究了如何将高级编程技术应用于批量计算和张量收缩。我们首先解释如何使用现代C++14编程技术设计一个简单的数据容器然后，我们研究了批处理计算，内存局部性和代码矢量化的问题，实现了高度优化的矩阵矩阵产品的小尺寸使用SIMD指令。通过结合高层次的编程方法和先进的并行编程技术，我们表明，我们可以超越国家的最先进的数值库。这篇博士论文的主要贡献可以概括如下：– 我们提出了一种基于类型标记的NT2和LAPACK/- MAGMA之间的架构感知绑定，以可扩展的方式在不同的架构和运行时后端之间进行调度– 我们提供了一个linsolve的实现（参考Matlab例程）第四章导言它考虑了硬件和算法的特点，在编译时从高级C++代码中选择和生成适当的LAPACK/MAGMA例程，映射超过160个内核。– 我们提出了一个多阶段的方法来减轻主机/设备编程模型的成本模型卸载代码。这提供了自适应的策略，可以直接从包含NT2语句的单个C++– 我们的方法利用现代C++设计的混合计算和接口开发，而不依赖于当前的软件。– 我们描述了一种策略，使用基于硬件特性和计数器的性能分析，以实现特定架构上的高效算法这项工作是基于一个小批量的矩阵矩阵产品，可以执行比最先进的图书馆。第1使数值库适应并行体系结构内容1.1科学计算..............................................................................高级程序设计71.2求解稠密线性系统............................................................................................81.2.1 LU分解。- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的-是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的- 是的 91.2.2QR分解.......................................................................
我的内容管理
展开
