异构嵌入式系统的自动并行化分布式、并行和集群计算的博士论文

异构嵌入式系统的自动并行化罗基亚图·迪亚拉引用此版本：罗基亚图·迪亚拉异构嵌入式系统的自动并行化分布式、并行和集群计算。巴黎萨克雷大学（COmUE），2019年。英语NNT：2019SACLS485。电话：02528823HAL Id：tel-02528823https://theses.hal.science/tel-025288232020年4月2日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire异构嵌入式系统的自动并行化Thee`sededoctoratdeEcole doctorale n1580 Sciences et Technologies de通信（STIC）Spe'cialite'dedoctorat：TraitementduSignaletdesImagesThe`sepre′sente′eetsoutenuea`DigiteoLabs，Gif-sur-Yvette，le25/11/2019，parMME ROKIATORY DIARRA评审团组成：多米尼克·霍泽教授，Universite'GrenobleAlpes（GIPSA-Lab）教授穆罕默德·沙基Professeur，Universite′deTechnologiedeCompie`gne（COSTECH）Rapporteur贝特朗·格拉纳多Professeur，SorbonneUniversite'（LIP6）RapporteurMiche`leGOUIFFES南太平洋大学（LIMSI-CNRS）考试官马克·杜兰顿Chercheur，Commissariata`l阿兰·梅里格·奥特教授，Universite'Paris-Sud（SATIE）Directeurdethe`seBastien VINCKEMaitredeConfe′rences，Universite′Paris-Sud（SATIE）Co-encadrantdethee`se医生说NNT：i摘要近年来，将多核CPU与GPU、FPGA和Intel Xeon Phi等加速器相结合的异构架构有所增加。GPU可以为某些类别的应用程序实现显着的性能。尽管如此，使用低级API（例如，CUDA，OpenCL）需要重写顺序代码，对GPU架构有很好另一方面，基于指令的编程模型（例如OpenACC，OpenMP）提供了底层硬件的高级抽象，从而简化了代码维护并提高了 生 产 力 。 它 们 允 许 用 户 通 过 简 单 地 插 入 指 令 来 加 速 GPU 上 的 顺 序 代 码 。OpenACC/OpenMP编译器有一项艰巨的任务，即从用户提供的指令中应用必要的优化，并生成利用GPU架构的高效代码。尽管OpenACC / OpenMP编译器已经成熟，并且能够自动应用一些优化，但生成的代码可能无法实现预期的加速，因为编译器没有整个应用程序的完整视图因此，使用OpenACC/OpenMP加速的代码与使用CUDA/OpenCL手动优化的代码之间通常存在显著的为了帮助程序员在GPU上使用基于指令的模型有效地加速他们的传统顺序代码，我们研究了OpenACC和OpenMP编程模型，并提出了一种有效的基于指令的应用程序并行化方法。我们的应用程序移植经验表明，仅仅插入OpenMP/OpenACC卸载指令来通知编译器必须编译特定代码区域以供GPU执行是不够的。将卸载指令与循环并行化结构相结合是非常必要的。虽然目前的编译器已经很成熟，并执行了几个优化，用户可以提供更多的信息，通过循环并行构造子句，以获得优化的代码。我们还揭示了选择好的循环时间表的挑战。编译器选择的默认循环时间表可能不会产生最佳性能，因此用户必须手动尝试不同的循环时间表以提高性能 演出我们表明，OpenMP和OpenACC编程模型可以实现最佳性能，较少的编程工作，但OpenMP/OpenACC编译器很快达到其极限时，卸载的区域代码计算/内存绑定，并包含几个嵌套循环。在这种情况下，可以使用低级语言。我们还讨论了GPU代码中的指针别名问题，并提出了两个静态分析工具，自动执行源代码级别的类型限定符插入和标量提升，以解决别名问题。博士报告IIRokiatou DIARRAiii简历L’utilisation Les GPU peuvent atteindre des performances significatives pour certaines catégoriesd'applications.此外，为了保证性能，必须使用CUDA和OpenCL等基础API，重新编写séquentiel代码，熟悉GPU架构和优化复合体应用程序，另一方面，基于指令的编程模型（例如OpenACC、OpenMP）提供了对底层材料的高级抽象，有助于代码的维护和提高生产力。Ils permettent aux utilisawareLes compilateurs虽然OpenACC/OpenMP编译器已经成熟，并且能够自动应用某些优化，但代码生成器可能无法实现预加速，因为编译器无法处理完整的视图所有的应用程序。此外，在使用OpenACC/OpenMP加速的代码和使用CUD- A/OpenCL手动优化的代码中，存在一个性能重要的通用代码。Afin d'aider les programmeurs à accélérer efficacement leurs codes séquentiels sur GPU avec lesmodèles basés sur des directives et à élargir l'impact d'OpenMP/OpenACC dans le mondeuniversitaire et industrielle，cette thèse aborde plusieurs problématiques de recherche.我们研究了OpenACC和OpenMP的编程模式，并提出了一种基于指令的编程方法的应用程序并行化方法Notre exérience de portageIl est essentiel de combining les directives de déchargement aveccelles de parallélisation de boucle. 由于编译器实际上非常成熟且有效地进行了多个优化，因此使用者可以通过boucle并行指令的条款来获得更优化的代码我们应根据执行一个球的螺纹名称选择合适的螺纹。编制者所选择的线程名称不能产生最好的性能。L’utilisateur doitdonc essayer manuellement différents Nous démontrons que les modèles de programmationOpenMP et OpenACC peuvent atteindre de meilleures performance avec un博士报告ivRokiatou DIARRA努力的编程，但这些编译器的OpenMP/OpenACC atteignite- ment rapide- ment lorsque lecode de région déchargée a une forte intensité arithmétique，nébritite un nombre très élevé d'accès à la mmoire globale et content plusieurs boucles imbriquées。在这些案例中，这些新的语言被使用了。我们讨论了GPU代码中指针的别名问题，并提出了两种分析统计的方法，这些方法可以自动确定类型和代码源中标量的位置v奉献致我已故的父亲奥马尔·迪亚拉致我亲爱的母亲科罗蒂米·迪亚拉致我亲爱的兄弟姐妹们致敏可罗·丰巴，我最好的另一半如果没有你们的爱和无条件的支持，这项工作是不可能的博士报告viRokiatou DIARRAvii确认我感谢上帝给我勇气、耐心和力量，让我能够面对过去三年中遇到的所有困难这篇论文的顺利完成，离不开许多人的指导、支持和鼓励。借此机会，我向所有为我的论文的成功做出贡献的人表示衷心的感谢和赞赏。我非常感谢我的导师阿兰·梅里戈（Alain MéRIGOT）和我的共同导师巴斯蒂安·温克（Bastien VINCKE），感谢他们坚持不懈的鼓励和激励，感谢他们不断提供创造性的反馈，感谢他们在工作中提出的令人振奋的建议，感谢他们提出的建设性批评。我也感谢他们的耐心和对我能力的信任他们巧妙的建议和发人深省的命题帮助我拓宽了我对这篇论文主题的看法我真诚地感谢Mohamed SHAWKY先生和GRANADO Bertrand先生给我的荣誉，他们接受了我作为这篇论文的报告人，并对我的研究课题感兴趣。我还要衷心感谢DominiqueHOUZET先生和Michèle GOUIFFES女士同意作为评审员对这项工作进行评估。我想真诚地感谢SATIE - ENS Saclay实验室的全体成员，特别是MOSS团队的成员。我要感谢我的家人。特别是我已故的父亲奥马尔·迪亚拉，我亲爱的母亲科罗蒂米·迪亚拉，我的姐妹萨塔拉和娜娜，以及我的兄弟。我感谢他们在我多年学习期间的鼓励和支持我借此机会告诉他们，我是多么感激他们为我所做的一切。最后，但并非最不重要的是，我要感谢我亲爱的爱Minkoro FOMBA。我感谢他的耐心、他的绝对支持、他的建议和他对我所从事的一切的鼓励。博士报告VIIIRokiatou DIARRAIX出版物1. “Exploring Performance Improvement Opportunities in Directive-Based GPUProgramming”，Rokiatou Diarra，Alain Merigot，Bastien Brackke，Conference onDesign and Architectures for Signal and Image Processing（DASIP），October2018，Porto，Portugal2. “RECKA和RPromF：两个用于优化CUDA、OpenACC和OpenMP程序中寄存器使用的Frama-C插件”，Rokiatou Diarra、Alain Merigot、Bastien Brachke，IEEE第18届源代码分析和操作（SCAM）国际工作会议，2018年9月，马德里3. “Towards automatic restriction of CUDA kernel arguments” ， Rokiatou Diarra ，Proceedings of the 33rd ACM/IEEE International Conference on Automated SoftwareEngineering，2018年博士报告XRokiatou DIARRAXi内容图表.十五表格一览表xvii介绍11背景71.1计算机体系结构81.2并行架构91.2.1并行计算111.2.2处理器性能1.3嵌入式系统1.4异构系统141.5目标架构和平台151.5.1图形处理器（GPU）151.5.2NVIDIA GPU161.5.3NVIDIA Quandro M2000M181.5.4NVIDIA Tegra X1191.6GPU编程方法201.6.1基于内核的编程语言201.6.2基于指令的方针1.6.3自动并行代码生成工具271.6.4领域特定语言30博士报告XRokiatou DIARRA1.7摘要312OpenMP OpenACC规范分析332.1OpenMP342.1.1执行模型342.1.2计算卸载指令362.1.3记忆模型412.1.4数据映射指令、子句和数据库语句412.1.5从CPU到加速器的OpenMP..............................................................................2.2OpenACC472.2.1执行模型472.2.2计算卸载指令492.2.3记忆模型532.2.4数据映射指令、子句和数据库语句542.2.5OpenACC2.2.6OpenACC实现562.3OpenMP和OpenACC规范比较582.4适用于GPU编程的622.5摘要653使用OpenACC OpenMP67的应用程序并行化方法3.1OpenACC OpenMP68上以前的工作3.2硬件平台编译器733.2.1性能测试733.3基准.743.4一般并行编程问题743.4.1GPU编程的特定问题773.5使用OpenMP和OpenACC78进行并行化的方法3.6OpenMP和OpenACC构造对性能的823.6.1取得的成绩903.7内存分配方法性能比较963.8通过工作分配进行优化：线程映射98Xi3.9OpenACC和OpenMP的性能改进，使用Open99内容3.10 结论1014GPU105上的指针混叠4.1指针混淆1064.1.1问题陈述1084.2现有解决方案1114.2.1分析1114.2.2语言支持1124.2.3标量替换1134.2.4摘要1154.3工作1164.3.1分析1174.3.2标量替换1184.4Frama-C1194.5标量替换工具RPromF121的设计4.5.1预处理模块1224.5.2分析模块1224.5.3后处理模块1244.6一个自动限制关键词插入工具125的设计4.7工具评估1274.8结论1285用例：基于立体视觉的视觉里程计应用1315.1视觉里程计1325.1.1立体匹配1345.2用例演示1355.3场景流程描述1365.3.1特征检测和描述1365.3.2特征匹配1385.4自我运动估计描述141博士报告XRokiatou DIARRA5.5对原作者的分析和分析版本1435.6基于原始CPU的场景流实现1445.7场景流自适应的并行148博士报告xiii Rokiatou DIARRA5.8在CPU154上的场景流并行化5.8.1取得的成绩1575.9GPU159上的场景流并行化5.9.1使用OpenMP160在GPU上卸载场景流5.9.2使用OpenACC163在GPU上卸载场景流5.9.3用CUDA165实现场景流的可视化5.10 GPU166上的性能结果5.11 结论1696结论173结论173A Résumé Submanciel en Français177A.1Contexte，Problématique et Motivations177A.2目标179A.3OpenMP和OpenACC180标准分析A.3.1AdaptabilitéA.4与OpenMP/OpenACC184并行的方法A.5Proposition de deux outilsA.6ApplicationA.7结论和展望186参考书目189Xi图目录1异构计算的两个主要挑战的说明32Scopus数据库搜索“OpenACC”和“OpenMP卸载”41.1计算机的内存层次结构91.2异构计算系统14的示例1.3第一个基于费米的GPU架构：16个SM，每个32个核心[1]171.4NVIDIA Quadro M2000M框图191.5NVIDIA Tegra X1嵌入式卡（打印自[2]）191.6CUDA线程映射到GPU211.7同一经纱中的纱线发散示例212.1用于加速器的OpenMP执行模型的图示2.2使用目标指令37卸载Sobel 3 × 3滤波器计算2.3使用target和teams指令卸载Sobel3×3过滤器计算。392.4用于加速器编程412.5用于加速器编程的422.6OpenACC执行模型48的图示2.7使用并行结构的Sobel3×3滤波器计算卸载512.8浅拷贝和深拷贝612.9CUDA、OpenACC和OpenMP63中的线程层次结构图示3.1使用OpenMP和OpenACC81并行化方法的主要步骤3.2OpenACC在Quadro M2000 M GPU92上相对于CUDA的速度降低3.3OpenACC在Quadro M2000 M GPU94上相对于CUDA的速度提升3.4在Quadro M2000 M GPU95上，OpenMP相对于CUDA的速度降低博士报告XRokiatou DIARRA3.5在Quadro M2000 M GPU96上相对于CUDA的OpenMP加速图目录博士报告xviRokiatou DIARRA3.6OpenACC内存分配方法在Quadro M2000 M GPU97上的性能3.7OpenMP内存分配方法在Quadro M2000 M GPU。983.8在OpenMP99中设置网格和块大小3.9评估工作负载对Quadro M2000 M GPU101性能的影响4.1简单的表示内存区域的情况下，没有，部分和必须别名。1074.2使用ABxtmp和ABxyy调用gesummv1104.3带有restrict关键字的Gesummv内核执行时间1144.4在源代码中使用标量替换时gesummv内核的执行时间。.......................................1154.5标量替换工具的分析模块125的功能图4.6限制关键词插入工具的分析模块126的功能图4.7关于RECKA1274.8Quadro M2000 M：相对于原始版本的1285.1用例算法概述1365.2斑点和角遮罩1375.3用于计算特征描述符138的Sobel滤波器掩模和布局5.4特征描述符计算1395.5特征检测和描述1395.6用于细化的描述符1415.7基于Intel I7143的原始CPU实现的性能5.8作者基于CPU的实现的并行化版本的工作流程1565.9作者基于CPU的实现的并行化版本的工作流程1575.10 CPU上的场景流性能：相对于作者版本158的加速5.11 作者基于CPU的实现的并行化版本的工作流程1615.12 NVIDIA Quadro M2000 M GPU167上的场景流性能5.13 NVIDIA Tegra X1 GPU167上的场景流性能5.14 最佳的OpenMP、OpenACC和CUDA加速比（相对于最佳CPU性能）-169