嵌入式和高性能应用程序的多核并行处理软件贡献

对嵌入式和高性能应用程序的多核并行处理软件的贡献朱利安·哈斯科埃引用此版本：朱利安·哈斯科对应用于嵌入式和高性能应用的多核并行处理软件的贡献。嵌入式系统INSA deRennes，2018.英语NNT：2018ISAR0029。电话：02132613HAL Id：tel-02132613https://theses.hal.science/tel-021326132019年5月17日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire内容致谢11介绍31.1一般情况31.2论文的范围51.3捐款61.4第八篇论文提纲我 背景92嵌入式并行系统112.1嵌入式并行架构。. . . . . . . . . . . . . . . . . . . . . . .122.1.1多层次的竞争。. . . . . . . . . . . . . . . . . . . . .122.1.2异构并行系统。. . . . . . . . . . . . . . . . . . . .132.2计算机存储系统. . . . . . . . . . . . . . . . . . . . . . . . . .142.2.1内存层次结构。. . . . . . . . . . . . . . . . . . . . . . . . . . .142.2.2 内存架构。. . . . . . . . . . . . . . . . . . . . . . . . .152.3 MPPA®众核处理器。. . . . . . . . . . . . . . . . . . . . . . . . .172.3.1 体系结构概述。. . . . . . . . . . . . . . . . . . . . . . . . .172.3.2计算资源。. . . . . . . . . . . . . . . . . . . . . . . . .182.3.3 通信。. . . . . . . . . . . . . . . . . . . . . . . . . . . .192.4从并行架构到软件. . . . . . . . . . . . . . . . . . .204.1操作系统. . . . . . . . . . . . . . . . . . . . . . . . . . .202.4.2 经典软件内存布局。. . . . . . . . . . . . . . . . . .212.4.3 虚拟内存的软件管理。. . . . . . . . . . . .222.4.4 软件并发。. . . . . . . . . . . . . . . . . . . . . . . . .222.4.5MPPA®的。. . . . . . . . . . . . . . . . . .232.5结论。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .253并行编程模型273.1任务规划模型. . . . . . . . . . . . . . . . . . . . . . . . . . .283.1.1处理线程。. . . . . . . . . . . . . . . . . . . . . . . . . .283.1.2 POSIX线程. . . . . . . . . . . . . . . . . . . . . . . . . . . . .29我内容ii3.1.3 OpenMP多线程。. . . . . . . . . . . . . . . . . . . . . . .293.2加速编程模型。. . . . . . . . . . . . . . . . . . . . . .323.2.1 执行模型。. . . . . . . . . . . . . . . . . . . . . . . . . . . .323.2.2 OpenCL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .323.2.3 OpenACC OpenMP 4.0 with Modern Quantifiers.. . . . . . . . .343.3数据流模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .353.3.1 导言。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .353.3.2数据流概述，Kahn过程网络。. . . . . . . . . . .353.3.3数据流过程网络。. . . . . . . . . . . . . . . . . . . . . . .353.3.4 静态数据流模型。. . . . . . . . . . . . . . . . . . . . . . . .363.3.5动态数据流模型。. . . . . . . . . . . . . . . . . . . . . . .403.3.6 参数化的基于接口的同步实时数据流（SDF）。. . . .413.4图调度和内存分配。. . . . . . . . . . . . . . . . . .413.4.1SDF图的调度方法。. . . . . . . . . . . . . . . . .423.4.2 内存分配。. . . . . . . . . . . . . . . . . . . . . . . . . . .433.5快速原型和现有的基于数据流的工具。. . . . . . . . . . .453.5.1 PREESM：一个开源的快速原型框架。. . . . .453.5.2 SPIDER：嵌入式可重构数据流处理器。. . . . .463.5.3基于数据流编程模型或语言的其他工具。493.6结论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .494通信协议内存一致性514.1HPC通信技术的发展现状514.1.1高性能计算（HPC）硬件互连524.1.2HPC软件编程524.1.3“Asynchronous Copy” Primitives of OpenCL4.2双向通信554.2.1伦巴第554.2.2同步-异步发送/接收协议564.2.3严格匹配问题564.3单向通信564.3.1加载/存储574.3.2Put/Get远程直接内存访问（RDMA）574.3.3远程原子操作584.4内存一致性一致性584.4.1定义584.4.2内存一致性模型594.4.3记忆栅栏604.5Kalray VLIW Core61的内存访问管理4.5.1K1的缓存 VLIWCore..................................................................................... 614.5.2流式内存访问624.5.3管理k1V超长指令的内聚一致性操作字（VLIW）核心62内容iii4.5.4原子指令634.6结论65二、捐款.675分布式计算中通信和同步的基本机制5.1挑战705.2分布式通信与同步协议的设计程序员715.2.1记忆片段715.2.2单边725.2.3双面755.2.4重组：数据布局765.3分布式通信和同步的实现5.3.1记忆片段775.3.2单边：异步远程原子操作&远程Di-rect内存访问（RDMA）Put Get算法775.3.3活动完成795.3.4单方面： RDMA和远程原子仲裁器............................................................. 795.3.5通过远程邮件支持Eager消息805.3.6RDMA Put/Get上的数据重组支持815.4使用、资源分配配置825.4.1用于实现单边操作的835.4.2双边业务845.4.3AsynOne-Sided（AOS）in a Com所需的资源pute星团845.5性能，结果：延迟865.5.1记忆力测试865.5.2内存延迟885.5.3片上网络可扩展性885.5.4远程原子性能895.5.5远程队列缓存895.6高级异步单侧支持905.6.1Linux内核91中的支持5.6.2标准的扩展和支持在Kalray OpenCL91中使用coc_work_group_copy（）5.7结论. 926一种高效的多线程处理器956.1控制和启用非相干多核中央处理单元（CPU）的线程966.2新的多线程处理器96的实现6.2.1逻辑线程状态966.2.2处理系统假阳性和屏蔽中断976.2.3线程控制986.3同步原语103内容iv6.4合作伙伴1036.5使用新的多线程编译器（NMTR）启用OpenMP多线程1066.5.1配置架构1066.5.2对GNU编译器集合（GCC）libgomp106的6.6自动线程化：RDMA完成时的自动线程调度 . . . 1076.6.1自动线程：设计和实现1086.7结果、比较和讨论1106.7.1基准1106.8结论1137基于分层静态数据流模型的集群众核处理器1157.1以分层众核处理器116为目标的IBSDF的分层7.1.1分层数据流应用1177.1.2战略：层级之间的权衡1177.2有效地利用两个层次的竞争力1187.2.1高级别层次结构（群组间）1187.2.2低级别层次结构（群集内）1197.2.3自动生成集群之间的显式通信1207.3IBSDF Graph121的自动聚类7.3.1算法：设计与实现1217.3.2聚类规则、启发式和循环建模1227.4实验评价1247.4.1结果与比较1257.4.2与平面IBSDF映射的1267.5结论1288将用于执行可重新配置数据流的嵌入式CPU移植到经移植的众核处理器129上8.1分布式数据流处理器130的体系结构8.1.1全球多源处理器Arr a y（MP PA）®实施的InsightoftheMulti-PurposeProcessorArra y（MPPA）®Implementation1318.1.2原始同步协议1318.1.3分布式同步协议1328.2基于启发式的优化调度1348.2.1禁止的复杂性和足迹1348.2.2轻量级调度，更简单更快1348.3管理分布式内存1358.3.1分布式本地存储器而不是缓存1358.3.2线程安全本地内存分配器1368.4结果与比较1378.4.1LRT137的内存占用8.4.2性能和SPIDER开销1378.5结论1399一种用于多核处理器的分布式OpenVX框架9.1需求和定位142内容v9.1.1OpenVX标准和示例1429.1.2第三方实施优化1449.1.3OpenVX和OpenCL1459.2一种低层分布式O语言加载引擎1459.2.1O加载引擎145的体系结构9.2.2O型装载发动机146的主要特点9.2.3OpenVX框架中的集成和使用1489.3在线优化：vxVerifyGraph1489.3.1优化工作流程1489.3.2自动内核融合优化1499.3.3分布式静态内存分配1519.4基于显式RDMA的通信引擎1519.4.1一个平铺融合RDMA引擎1519.4.2平铺融合优化1539.5复杂分布和内存访问模式1549.5.1处理不规则的内存访问1549.5.2分布式约简和动态列表更新的实现1569.6结果讨论1589.6.1业绩分析1589.6.2异步RDMA预取的好处1589.6.3自动内核融合1599.6.4多集群级别的超线性加速比1609.6.5不规则内存访问性能1619.6.6Harris特征点检测1629.7结论16310 多核并行处理器cessor16510.1用于计算3D模板的宏管道。. . . . . . . . . . . . 16510.1.1格子玻尔兹曼方法（LBM）算法和背景。. . 16610.1.2最新技术水平的。. . . . . . . . . . . . . . . . . . . 16610.1.3在操作系统之上优化3D LBM支架应用程序。. . . . . 16710.1.4结果和讨论。. . . . . . . . . . . . . . . . . . . . . . . . 17110.2低延迟分布式快速傅立叶变换. . . . . . . . . . . . . 17410.2.1快速傅立叶变换. . . . . . . . . . . . . . . . . . . . . . . . . 17410.2.2快速傅立叶变换的计算技术。. . . . . . . . . . 17410.2.3分布式快速傅立叶变换实现。 . . . . . . . . 17610.2.4结果讨论。. . . . . . . . . . . . . . . . . . . . . . . . . 18010.3用于CNN推理的分布式卷积。. . . . . . . . . . . . . . . . . . . 18110.3.1总体架构。. . . . . . . . . . . . . . . . . . . . . . . . . . 18210.3.2 CNN为一个被解雇的Manycore辩护。. . . . . . . . . . . . . . . 18210.3.3结果比较。. . . . . . . . . . . . . . . . . . . . . . . . 18310.4结论。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184内容vi11 结论18711.1 我们的贡献18711.2 今后的工作18911.2.1 多核编程的基本机制：异步单边（AOS）19011.2.2 针对多核的标准优化运行时19111.2.3 电子化技术19211.3 最后结论193内容vii法语摘要195A.1 Systemes parallèles embarqués196A.1.1Le parallelisme et le processeurMPPA® de Kalray196A.1.2Mémoires et protocoles de communication197A.2 Les modèles de programmation parallèleA.2.1Interfaces de programmationA.2.2Modèles de pouchux de données198A.3 EnvironnementA.3.1Environnement distribué pour la communicationA.3.2多点对称执行环境：无A.4 2000年并行建筑学应用软件的执行A.4.1调整和调整欧洲国家模式的战略de données hierarchiques201A.4.2搬运和调整一种用于放置和安排一种用于参数设置的模式的执行禁运的工具et dynamique201A.5 Un administration standard distribué pour la vision et applicationssurarchitectures applications paralleles202A.5.1Environnement embarqué distribué pourA.5.2向主要国家分发的申请和禁运品204A.6 结论204图209表211词汇表213个人出版物220参考书目234内容viii致谢我的家人，我的爱人，我的朋友，我的同事。我衷心感谢我的导师让-弗朗索瓦·内赞、贝诺特·杜邦·德·迪内钦和卡罗尔·德斯诺斯，感谢他们的建议和时间我要感谢Alain Girault和François Irigoin为审查工作所做的辛勤工作， 这份手稿。我感谢所有在软件方面给予我技术支持的同事：Pierre Guironnet de Massas、Benoquitt Dupont de Dinechin、Samuel Jones、Patrice Gerin（特别感谢模拟器，没有它我还在调试我的第一个贡献）、Frederic Blanc、Karol Desnos、Minh Quan Ho、MariusGligor、Julien Villette;在硬件方面：Vincent Ray、Nicolas Brunie和Alexandre Blampey。12致谢第1介绍1.1一般上下文计算机科学是一个广泛的领域，它改变了我们的生活方式。从五十年代晶体管的发明到最新发布的电脑游戏、自动驾驶汽车和智能家居，我们所知道的世界现在依赖于计算机系统。自从计算机科学和计算机体系结构出现以来，对计算的需求一直在增长。随着应用程序提供的服务以各种方式使我们的生活更轻松、更智能、更快速，在这个博士学位中， 重点是嵌入式系统。 一般来说，嵌入式系统是计算机领域中所有非通用计算机的东西。嵌入式系统存在于所有电子系统或电子系统的部分中。这些新的智能系统随处可见。例如，典型的嵌入式系统是智能手机、健身腕带、全球定位系统（GPS）、MP3数字音频播放器、洗碗机、电视（TV）系统以及几乎所有需要智能为人类提供特定服务的电力供电系统今天，由于晶体管的高密度集成（到2020年宣布为5纳米），嵌入式系统可以执行许多复杂的任务，并具有高能效。因此，嵌入式系统现在无处不在，不可避免，它们对我们的生活产生了重大影响。嵌入式系统被发现在几个新的应用领域，如物联网（IoT），大数据，先进的医生辅助系统（ADAS）[MGL+16]和嵌入式视觉和视频。复杂的嵌入式计算系统的最新例子也可以在航空航天领域中找到，其中嵌入式电子设备必须满足关于应用安全的容错性、鲁棒性、冗余性和系统隔离的高期望。像空客这样的公司在投入使用之前，会花费数年的时间来设计、实施和测试嵌入式系统。这是由于应用程序的特殊性，特别是在复杂和约束环境中。正如论文[ Wol02 ]中所述，“嵌入式系统是在较大的机械或电气系统中具有专用功能的计算机系统，通常具有实时约束。因此，嵌入式系统的设计是为了在受限的环境中适应特定的应用。约束通常是硬件和软件。例如，嵌入式系统的约束通常是功耗、时序响应延迟、时间4介绍计算确定性、计算性能、鲁棒性、成本、面积和容错性。所列的一些限制是对立的。实际上，优化应用程序的延迟通常会降低其吞吐量。甚至，提高应用程序的性能会导致最终系统的功耗增加，因为它运行得更快;因此，它消耗更多的能量。最后，提高性能通常意味着增加应用程序的成本。众所周知，嵌入式系统的设计、实现和验证是复杂的，它们满足具有相关约束的所需特征。这就是为什么软件需要利用硬件来使应用程序在约束环境中高效地运行1965年，戈登·摩尔（Gordon Moore）发表了一篇著名的论文，指出在一个密集集成电路中，晶体管的数量每两年就会除了摩尔因此，制造商不断增加集成处理器的操作频率 ， 从 1971 年 以 740kHz 选 通 的 旧 Intel®4004® 处 理 器 到 2004 年 以 4 GHz 选 通 的 高 端Intel®Pentium®-4Dennard缩放在2004年左右破裂，对应于65nm CMOS技术节点。从那时起，半导体制造商已经失去了在不触及电源墙的情况下大幅提高时钟频率的能力。自2004年以来，计算机架构师设计并行架构来提高计算能力，而不会触及这道功率墙。在2004年之前，计算机架构师已经设计了一些并行架构。其中一个例子是德州仪器（TI）的多处理器片上系统（MPSoC），称为C80 [DS95]，它集成了4个数字信号处理器（DSP）内核和一个精简指令集计算机（RISC）内核，旨在针对嵌入式系统的节能计算。但这种MPSoC只能由TI多核软件确实与单核软件非常不同，这是由于并发执行，资源共享和许多其他问题将在本博士论文中讨论论文。增加使用共享内存的内核数量可以在一定程度上提高性能（大约多达数十个内核）。此时，性能受到对单个存储器资源（共享存储器）的并发访问的限制。如今，新一代的体系结构已经被设计出来，称为集群体系结构。这些新的体系结构以分布式存储器为特征，以解决共享存储器的问题。这些新架构的编程更加复杂，涉及巨大的软件开发成本。内存带宽是一个重要的性能因素。大多数时候，主存储器带宽（处理器和外部存储器之间的带宽）是高性能应用程序在并行架构上的瓶颈主存储器带宽低于可用的内部片上存储器带宽[WWP09]。当处理器内部的内核数量增加时，内存带宽往往成为应用程序的瓶颈。在这种情况下，核心没有像它们处理数据那样快地被馈送数据。存储器层次结构的目的是减少平均存储器延迟访问时间，并减少存储器之间的存储器传输避免存储器带宽墙需要时间和空间数据局部性，以有效地使用片上存储器。 在优化阶段的早期处理这样的瓶颈是至关重要的，以在新一代集群多核上获得有竞争力的性能论文的范围5在这种情况下，这个博士。 旨在降低软件开发的复杂性，以减少这些新一代复杂MPSoC的开发时间，同时保持性能。1.2论文的范围本论文是雷恩电子与计算机研究所重点是Kalray公司设计的一系列众核架构。这个多核家族的特点是分布式存储器，让并行程序可以扩展。Kalray的多核架构将核心重新分组为配有多库共享本地存储器的集群;然后，这些集群与片上网络互连。该MPSoC支持使用多达288个实核，自己的执行上下文。MPPA®专为节能计算而设计，使用本地存储器和直接存储器访问（DMA）引擎，通过软件将数据在片上移动到片上。这些特性使MPPA®处理器成为低功耗计算领域的有力竞争者，但它在编程、观察和调试方面具有挑战性在这篇论文中，我们研究了最新一代集群架构的编程模型和应用程序编程接口（API）。编程模型和API都使用高级模型和文档化函数来抽象目标架构。API提供了一组功能，使一个或多个功能可以在处理器上运行。API存在于多个编程级别。低级编程非常接近目标硬件。在底层编程是痛苦的，需要深入了解目标架构。低级程序的可移植性也很差。但当编程正确执行时，它具有无与伦比的性能。高级和中级编程将硬件架构抽象化给程序员。程序员使用高级API，并且程序可以在多个芯片上编译和执行，包括通常的通用处理器和用于嵌入式系统的给定处理器集。然而，高级API也可以在硬件制造商提供和销售的高性能优化库中找到，这些库在大多数情况下为API所解决的用例释放最佳性能。参见例如Intel®Math Kernel Library（MKL）。这些API组件的性能而对于程序员来说损失了术语的通用性。编程模型旨在成为表达计算的一种方式或风格。编程模型通常是语言不可知的，而API则不是。编程模型的一个例子是使用特定API表示的OpenMP。应用程序工程师只在其源代码中编写几个独立的编译指令，如果支持，顺序计算将根据指令自动并行执行在这篇论文中，目的是使用数据流编程模型来描述一个高层次的抽象应用程序。 存在许多数据流模型，它们广泛用于低级或高级的软件编译器中。数据流应用程序用计算块表示，并使用定向通信链路交换数据因此，数据流通常表示为有向图，其中节点表示计算，节点之间的链接表示数据通信。然而，数据流编程模型在细节方面有各种改进。当复杂的应用程序需要高效地移植时，这有时会给应用工程师带来麻烦。但是，数据流编程仍然是快速评估和应用程序移植到复杂并行架构上的一个巨大竞争对手。平行和6介绍实时嵌入式执行调度方法（PREESM）项目，由VAADER团队中的IETRVAADER团队18年来一直专注于并行编程的研究工作。PREESM项目始于2007年，如今，它使在x86架构和多核DSP（如TIKeystone II）上开发和自动并行化数据流应用成为可能。在这篇论文中，我们研究，适应，并提出新的软件运行时和方法的基础上的数据流编程模型，以适应这新一代的集群架构。我们使用计算机视觉，深度学习，数字信号处理和数值模拟应用程序来测试本论文的贡献1.3贡献本节介绍了在论文中介绍的集群众核处理器的软件贡献。 虽然这款处理器是真机，由台积电制造 在28纳米，即MPPA®处理器，所有的贡献旨在被推广和应用到类似的架构，如Epiphany-V芯片[Olo 16]和PULP加速器[CRP+16]。为此，本文介绍了MPPA®处理器的编程有些技术是对现有方法的改编和优化，首次在MPPA®处理器上启用，而其他技术则是新的。本文的主要贡献如下：• 单边通信技术在双边片上网络中的应用。目前，新的通信引擎已部署在生产中，通过高性能和低延迟的单边通信原语以及双边原语来抽象Kalray的片上网络。运行时部分，硬件资源的共享和通信的顺序进行了说明。它是为性能而构建的，它提供了硬件的总体抽象。这一贡献的一个重要特征是，所提供的原语集可以异步运行（在后台运行），这使得这一贡献在实现、调试和验证方面具有挑战性（并行性很复杂）。此外，单边通信彻底改变了使用显式通信对MPPA®处理器进行编程的方式因此，这也是本文所有其他贡献的基础。• 优化的多线程运行时，使细粒度多线程在MPPA®处理器的多核CPU（集群） 运行时在裸金属Kalray的工具链中启用了众所周知的POSIX线程原语和OpenMP多线程。该贡献使用无锁机制来实现高效的多线程。该运行时已经成熟，并且在本论文的几乎所有其他贡献中都使用它作为MPPA®处理器的多核CPU• 基于分层数据流模型，提出并详细描述了一种为MPPA®IETR的VAADER团队提出并设计的层次数据流模型该策略使两个层次的并行性的使用成为可能，并有效地利用。两个并行级别是内部多核CPU级别和内部多核CPU级别。模型的图形层次结构支持微调贡献7在数据流应用程序开发的早期阶段。还介绍了MPPA®处理器的第一个软件合成运行时后端 出色的加速性能 并给出了数据流图编译的大幅度缩减时间。• 本文介绍了IETR嵌入式运行时在嵌入式片上系统（SoC）上执行数据流应用程序的实时调度。在此情况下，重新考虑文件[HPD+14]中提出的原始运行时间，以使其在MPPA®处理器上运行。大部分工作包括在实现有限本地内存的多个多核CPU上分发运行时。调度器和内存分配技术也被重新设计。• 提供了一种用于使OpenVX应用程序图的低延迟执行成为可能的分布式嵌入式框架OpenVX是一个现代计算机视觉和卷积神经网络（CNN）推理标准[G+17]，用于将计算管线从主机扩展到一个或多个加速器。建议的框架是MPPA®处理器的OpenVX标准规范的洁净室实现。该框架在MPPA®处理器的独立模式下运行，使OpenVX应用程序图形的重新配置在运行时成为可能。该框架提出并采用了新技术来自动优化OpenVX用户图的执行，并在运行时（嵌入式）。优化的重点是减少主存带宽，这在大多数情况下是性能瓶颈。因此，在多个多核CPU级别上，通过Kalray的片上网络使用自动内核融合和自动数据预取该框架的目标是低延迟执行（无延迟），以提供一个反应式系统（用于嵌入式决策）。结果显示，在多个多核CPU级别上实现了超线性加速，表明该策略对于MPPA®处理器等集群众核架构是有效的。• 提供了使用本文软件运行时贡献的各种应用程序。这些应用程序是基于模板计算的数值模拟应用程序、数字信号处理应用程序、计算机视觉或CNN推理应用程序的低级实现。在这些贡献中，解释了并行化策略，以及它们的实现如何适应MPPA®处理器。这些用例是众所周知的，也是并行计算的基础。此外，一些实现非常复杂，因为它们以低级别的MPPA®但是，由于本论文先前的贡献，这些应用程序的实现是可能的，更容易实现和调试。突出的贡献要么是IETR这些贡献是在IETR