面向多核平台的Cache敏感离线实时调度算法与实现

安娜·伊芙（2018）THESHISE/UNIVERSITTHED DE RENNES 1布列塔尼卢瓦尔大学校园为了等级雷恩大学博士提及：Informatique数学博士学校par presentée越南编制面向多核平台的Cache敏感离线实时调度算法与实现Thèse soutenue à Rennesle 22 Février 2018陪审团组成后：史蒂文·德伦Rennes 1/校长Christine ROCHANGE图卢兹保罗·萨巴蒂尔大学讲师/特别报告员Mathieu JANIngénieur-chercheur，CEA/特别报告员达米恩·哈迪雷恩第一大学/考试官弗雷德里克·佩特罗Closseur，ENSIMAG格勒诺布尔/检查员Isabelle PUAUTRennes 1 /Directeur 忒塞致谢这篇论文在许多人的支持下成为现实我谨向他们表示衷心的感谢首先，我要感谢我的导师，雷恩第一大学的Isabelle PUAUT教授和Damien HARDY副教授，感谢他们坚定不移的支持和指导。我也要感谢我的委员会成员，他们给了我富有成效的意见，以提高论文的质量。此外，我感谢所有永久工作人员和我的同事在PACAP团队的支持你的帮助使我的工作更轻松、更愉快。最后，我要感谢我的家人。你们总是鼓励我，相信我，帮助我专注于我所做的，这是一个巨大的回报。0目录内容目录0Résumé de la Thèse en langue Francaise 31一、导言. 71硬实时多核系统：时序可预测性挑战2目标和解决方案概述92.1缓存意识调度算法92.2实现高速缓存意识的时间表103捐款104组织112实时系统和多核平台：背景和最新技术2.1背景. 132.1.1实时系统132.1.2最坏情况下的执行时间估计142.1.3实时任务调度2.1.4时间可预测的多核硬件182.1.5高速缓冲存储器202.2多核系统的时序分析：最新技术水平2.2.1多核架构的WCET分析技术2.2.2多核架构的任务调度算法2.3摘要和论文背景253缓存意识调度：算法273.1系统模型和问题表述273.1.1硬件型号273.1.2任务和执行模型283.1.3假设293.1.4调度问题陈述293.2缓存意识任务调度方法303.2.1缓存意识ILP制剂313.2.2缓存意识列表调度方法（CLS）333.3实验评价3512含量3.3.1实验条件353.3.2实验结果403.4相关工作493.5摘要504缓存意识调度：实现514.1KalrayMPPA-256机器的结构514.2我们提出的时间驱动调度器的一般结构4.3实际挑战4.3.1调度程序造成的缓存污染4.3.2共享总线争用554.3.3由于任务的执行而延迟到任务的开始时间设置时间检查功能554.3.4缺乏硬件实现的数据高速缓存一致性564.4时间驱动的高速缓存意识的时间表适应实际问题574.4.1数据结构584.4.2应用程序执行的限制4.4.3根据实际效果调整基本的缓存意识时间表4.5代码生成器654.6实验评价4.6.1实验条件704.6.1.1基准704.6.1.2常数估计704.6.1.3无..........................................................................................................争用时的WCET和缓存未命中数估计714.6.1.4实验环境724.6.2实验结果724.6.2.1在Kalray MPPA上执行时，验证基准测试256计算集群724.6.2.2量化不同实际问题对适应缓存意识调度..........................................的影响734.6.2.3ACILP 74的性能评价4.7相关工作764.8摘要775结论79Bibliographie书目89作者的出版物图表93摘要99法语论文简历在我们的生活中，对时间的尊重也很重要，因为对时间的纠正是必要的。特别是，这些应用程序可能会在汽车、飞机和中央核电站中找到。此外，禁运制度的市场[1]肯定会在今后几年中有一个很强的需求2016年，系统市场价值达到84，55亿美元，预计2017年和2023年的年度增长率为随着对计算应用的需求越来越大，单核心建筑的应用也越来越多，这是一种合理的选择，也是一种建筑类型的技术限制（第二部分，能量限制在突破这一限制后，制造颜料的工匠们创造了新的工艺，称为多芯工艺，在这种多芯工艺中，颜料是同一种颜料的整体。多芯处理器在能量多核心架构迁移临时系统到利用多核心处理器的过程中，将注意力集中在资源中的应用程序的性能上，但也存在许多临时可用的问题。由于多核心处理器对材料的影响，确保应用程序的时间限制和并行性是一个真正的挑战。L’un des challenges les plus importants est d’estimer, avec précision, le Pire Tempsd’Exécution Il existe de nombreuses methodes pour estimer le PTE sur processeur mono-cæur [7]. 这 些 技 术 包 括 方 案 执 行 过 程 和 核 心 微 架 构 。 Étendre ces methodes auxarchitectures multi-cours est difficile，et ce déciliaux resources matérielles，tel que lescaches or les bus，whi sont partagées entre les cours，rendant ainsi此外，在本地缓存的体系结构上，对线程一个动作的执行时间是独一无二的Il dépend du contexte在这些事实中，有可能考虑一个独立于具体情况的估计，但这个估计的结果往往是悲观的。Demani`resymétrique，因此，Navisphere命令和PTE估计考虑到多个进程，这些问题是相互依赖的，涉及到一种人口和人口状况。由于这种相互依赖性，我们认为，Navisphere的顺序战略将考虑到多核心材料的完整性Prendre en compte les PTE dependants ducontexte aideà本文件中的这些工作考虑到本地缓存影响的PTE差异目标和解决方案介绍命令行Navisphere concent du cache。我们提出了两种基于Navisphere命令的技术，用于本地缓存、单元等多核心设备的体系结构，其中包括一种最佳方法，该方法利用了一种名为Entier（PLNE）的Programmation Linéaire公式，以及一种基于Navisphere命令的编程方法这两种技术可以使一个并行的应用程序通过一个tâches图表进行模式化，并生成一个非优先级的命令Navisphere静态分区。除了本地缓存的效果外，它还没有实现PTE的单一价值，而是通过PTE的整体价值实现。 Le PTE le plus pessimiste d'une tâ c he，noté PT E τ j，estobs e r é lorsqu'i l n'y a pas de réutilisatio n de co n t u c hargé dans le cache par la tâche s'exécutantimmédiatementavantτj.UnensembledevaleursdePTEnotéP TEτi→τjreprésentelesPTEd'unetâc heτ j lorsquueτ j réutilisedesinformations deτi，chargées aussi bien dans le cache d'instructions que de données par la tâche τ i s'exécutantimmédiatement avant τ j sur le même cæur. L'objectifde ces deux techniques est degénérer un ordonnNavisphere dont la longeur est aussi courte que possible.Les évaluations expérimentales sur les cas de tests de la suite de tests StreamIt [10]montrent des réductions significatives sur la longeur des ordonnancements générés parles techniques conscientes du cache comparées à leurs équivalentes ignorant les cacheprivés.根据Navisphere对流媒体应用程序的观测，采用最佳方法时减少了11%，采用最佳方法时减少了此外，该公司还提出了一项长期的生产秩序在这些过程中，Navisphere的排序方法是快速生成结果的一般方法，即需要1秒的时间来生成Navisphere的一个图表，该图表包含16个核心的548个La différence entre la taille des ordonnancements générés par0.7%在莫延。执行命令方法Navisphere conscientes du cache。Nous avons réalisé l'implémentationd'un ordonnNavisphere dirigé par le temps et conscient du cache pour le Kalray MPPA-256，un processeur multi-cæur en grappe.为了我们的儿子，我们经常为这台机器制造和安装一个电话号码。为了实现这一目标，我们首先要确定与这一类型的实现共存的挑战，包括• 缓存的污染和命令执行中的一个线程的延迟• 关于公共汽车分离的争论;• l’absence这些事实上的经验有助于提高各接触点的执行时间，但也改变了接触点的结束时间，因为在保证各接触点之间的关系后，需要对接触点的开始时间进行修改根据该常数，我们提出了一种PLNE配方，该配方修改了缓存的排序意识，以适应确定的因素，从而确保满足tâches之间的优先级，并最大限度地减少Navisphere的排序时间此外，我们还提出了一项战略，为Navisphere或Navisphere之后的机器cible生成一个应用程序代码使用StreamIT套件对基准进行实验性验证，以纠正功能和实现时间。此外，我们的montrons qu因此，我们量化了这些因素对这些订单的影响，并观察了对Navisphere订单的持续时间有更大影响的因素：竞争。贡献这些文件的主要工作如下：• Nous defendons et validons experimentalement• 我们提出了一种基于PLNE的命令Navisphere方法，用于解决一个命令Navisphere分区问题，而不是一个与图形dirigé和acyclique并行的应用程序在研究了订单生成的时间后，我们提出了一种基于Navisphere订单的技术• 我们提供了一些实验结果，其中包括命令制定者提出的一般命令和法院，这些命令和法院等同于当地的缓存。• 我们确定了用我们的策略来应对这些挑战。• 我们探讨了组织这本书用英语写分为五章。• 在第一章中，我们介绍了这些工作的概念。首先我们要解决工作的动机问题。除了提出目标，我们还提出了一系列解决方案，以解决问题第二，我们要简要介绍一下这些捐款。• 在第2章（导言）中，我们介绍了多核心系统共同体的明显工作所需的知识。我们将介绍一些隐含在温度相关系统、PTE分析和tâches命令Navisphere中的一般概念。我们还简要介绍了多核平台、多核建筑中的可预测性特征以及记忆缓存的特点。我们对多核平台的PTE和Navisphere命令进行了简单的分类和说明，以便我们能够识别各个方面，并详细说明Navisphere命令的问题，同时考虑到缓存的• 在第3章中，我们将指定Navisphere缓存的Navisphere命令的两种方法是针对一般静态或非并行应用程序而提出的，其中包括最佳方法和非并行方法我们还将对Navisphere建议的手术质量和快速生成方法的性能进行评估• 在第4章中，我们提出了Kalray MPPA-256机器的缓存和控制指令的执行情况我们将继续致力于平台架构的设计，并将继续致力于Navisphere命令的实施Ensuite nousidentifionslesdefisréelsquisurvivennentlorsdudéploiementdesordonnancements sus-mentionnés ， et résentons nos strategies pour dépasser lesdifficésidentifiées.Enfinuneévaluationexérimentalevalidelacorrec-tionfonctionnelle et temporelle de notre implémentation.• 在第5章中，我们总结了这些工作，并提出了未来工作的前景第1介绍1硬实时多核系统：时序可预测性挑战实时嵌入式系统，即，那些定时要求高于性能要求的应用现在在我们的日常生活中很普遍特别是，实时应用可以在个人汽车，飞机，宇宙飞船，核电站中找到此外，根据[1]，嵌入式系统市场在未来几年可能会出现高增长2016年嵌入式系统市场价值为845.5亿美元，预计2017年至2023年的复合年增长率（CAGR）为4.05%。随着对更安全但计算密集型应用的需求不断增长，单核架构由于架构的技术限制（通常称为功率墙[2]）而不再适合部署实时系统为了克服这个问题，领先的芯片制造商已经提供了新的计算平台，称为多核平台，其中多个核心集成在单个芯片内。多核平台已被证明比单核平台具有更高的能效和更好的性能成本比[3]，因为它们通过利用线程级并行来提高应用程序性能多核架构的示例将实时系统迁移到多核平台可以保证计算密集型应用程序的性能，但也带来了系统的时序可由于多核硬件的影响（即，例如本地高速缓存、核之间的共享资源），保证多核平台上的安全关键并行应用的实时约束是具有挑战性的。一个重要的挑战是精确估计在多核上执行的代码的最坏情况执行时间过去，许多WCET估计方法都是针对单核架构设计的[7]。这种技术考虑到程序路径和核心微架构。将它们扩展到多核架构7芯1芯1高速缓存未命中缓存命中缓存缓存缓存缓存T2T1T2T3nMB一场景1场景2图1.1：调度策略对任务WCET的影响是具有挑战性的，因为一些硬件资源，如高速缓存或总线在内核之间共享，这使得任务的WCET依赖于在其他内核上执行的任务此外，在具有本地缓存的架构上，任务的WCET取决于任务开始执行时的缓存内容，这取决于调度策略。因此，一个任务的WCET不再是唯一的。它取决于任务的执行上下文事实上，人们可以考虑一个任务的上下文无关的WCET，但这个值太悲观了。激励的例子。让我们考虑一个过于简化的系统，由三个任务组成，名为T1，T2和T3，在双核处理器上执行，每个核心都配备了一个统一的私有缓存，包含两行。T1和T2访问同一个内存块，命名为m，而T3与T1和T2都是代码和数据独立的。我们考虑了两种执行场景，以揭示调度策略对任务的WCET的影响在第一种情况下，T2与T3位于同一个内核上，并在T3之后执行（如图1.1左侧所示）。在第二种情况下，T2与T1位于同一个内核上，并在T1之后立即执行（如图1.1右侧所示）。我们假设缓存的内容在开始时是空的。 在第一种情况下，对存储器块m的T2请求是高速缓存未命中，因为在请求时间，存储器块尚未被加载到高速缓存中。因此，T2必须等待，直到存储块m从主存储器加载到高速缓存。相反，在第二种情况下，T2对存储器块m的请求是高速缓存命中，因为在T1的执行期间存储器块已经存储在高速缓存由于对高速缓存的访问比对主存储器的访问快得多，因此第二种情况下T2的最坏情况执行时间低于第一种情况下的最坏情况执行时间。这个例子展示了由于私有缓存的影响，任务的映射和执行顺序对其最坏情况执行时间的影响系统地，任务的最坏情况执行时间需要用于调度策略以确定映射，入门任务T1（Splitt-呃）T2（DFT）T3（DFT）T4（DFT）T5（DFT）T6（合并）T7（合并）T8（合并）T9（合并）T10（合并）T11（合并）T12（合并）T13（合并）退出任务T14（外出）图1.2：8输入快速傅里叶变换（FFT）应用程序的并行版本的任务图[11]任务的安排因此，多核平台的任务调度和WCET估计是相互依赖的问题，被称为鸡和蛋的情况。论文声称。由于上述相互依赖的问题，我们认为，调度策略，意识到多核硬件必须被定义。考虑任务的上下文敏感的WCET而不是单个上下文无关的WCET有助于提高调度的质量，即，缩短工期（makespan）。在这个博士工作1的范围内，我们考虑由于私有缓存的影响，一个任务的WCET的变化2目标和解决方案概述2.1缓存敏感调度算法我们在这篇论文中的第一个目标是提出缓存意识的调度策略，利用任务之间的缓存重用。每个任务都有不同的WCET值，这取决于在同一个核心上在它之前执行了哪个其他任务（WCET是上下文敏感的）。所提出的调度策略映射任务的核心和调度任务的核心，其目标是占缓存重用，以获得最短的时间表。 我们专注 在单个并行应用程序上，建模为任务图，其中节点表示任务1这项博士工作是PIA项目CAPACITES（Calcul Calcule pour Applications Critiques en Temps etSoccerreté.）的一部分，参考P3425-146781边表示它们之间的依赖关系此外，在缓存意识的时间表生成，我们只考虑私有缓存的影响，而其他硬件相关的因素留给实现阶段。我们提出了两种不同的方法来确定一个静态分区的非抢占式调度，旨在最大限度地减少时间表的长度，为并行应用程序，考虑到任务的WCET的变化，由于任务之间的代码和数据的第一种方法是基于一个线性规划（ILP）制定和考虑的假设下产生最优的时间表第二种方法是基于列表调度的启发式方法所提出的启发式调度方法产生的时间表非常快，启发式调度的长度接近最优的。为了进一步激发我们的研究，让我们考虑一个例子，8输入快速傅立叶变换应用[11]。其任务图如图3.2所示。 例如，T2和T3特征代码重用，因为它们调用相同的函数，并且T2和T6特征数据重用，因为T2的输出是T6的输入。在该示例中，当考虑可能在同一核心上连续执行的任务对之间的缓存亲和力时，我们观察到通过使用第3章中介绍的并行线性规划（ILP）技术，该并行应用程序的调度长度与其与缓存无关的等效方法相比注意到，在这个博士工作的任务的WCET的定义是不同的文献中定义的。在文献中，任务的WCET被定义为任务在隔离执行时的执行时间我们关于任务的WCET的定义是在任务执行开始时考虑缓存内容时任务执行时间的上限2.2缓存意识调度一旦考虑到私有缓存对任务调度的影响，我们的后续目标是在真正的多核硬件上实现时间驱动的缓存意识调度在实施阶段，我们首先确定的实际挑战时，在机器上部署这些时间表，如共享总线争用，时间驱动的调度本身的影响，硬件实现的数据缓存一致性的情况下。这些实际效果需要修改缓存意识的时间表。因此，我们提出了一个ILP公式，以适应缓存意识的时间表，以确定的实际因素，这样的优先关系的任务仍然得到满足，并适应时间表的时间表长度最小化。此外，我们提出了一种策略，用于生成的应用程序的代码，根据适应缓存意识的时间表在机器3贡献博士工作的主要贡献如下：• 我们认为，并通过实验验证的重要性，解决任务的WCET调度中的私有缓存的影响• 我们提出了一个基于ILP的调度方法和启发式调度方法，静态地找到一个分区的非抢占式调度的并行应用建模为一个有向无环图。• 我们提供的实验结果显示，除其他外，所提出的调度技术的结果在较短的时间比他们的缓存不可知的等价物。• 我们确定的实际挑战时，实现时间驱动的高速缓存意识的时间表上的Kalray MPPA-256机器，并提出我们的战略，克服所确定的挑战。• 我们研究了不同的实际因素对缓存意识的时间表的影响4组织本文的其余部分主要分为三章。在第二章中，我们介绍了实时多核系统的基本背景和文献综述我们首先介绍一些一般概念处理实时系统，WCET分析，任务调度。我们还简要介绍了多核平台，时间可预测的多核架构的理想属性，以及高速缓存存储器的特点。然后，我们分类，并简要介绍了从实时文献相关的WCET分析和任务调度的多核平台的主要工作。这使我们能够确定一些方面还没有得到太多的研究，特别是调度问题，考虑到私人缓存的影响一旦这些基础知识被介绍，我们提出了博士工作的不同贡献。在第3章中，我们描述了缓存意识的时间表生成。提出了两种生成并行应用静态分区非抢占式调度的方法，包括优化方法和启发式方法。第四章介绍了在Kalray MPPA-256机器上实现时间驱动的缓存意识调度我们首先描述了机器的体系结构，以及我们的时间驱动的调度器实现。然后，我们确定的实际挑战时，部署的时间驱动的缓存意识的时间表上的机器，并提出我们的战略，克服所确定的问题。最后，在第五章中，我们总结了本博士论文的工作，并对未来的工作提出了一些展望。第2实时系统和多核平台：背景和state-of-the-art在这一章中，我们介绍了实时多核系统的基本背景和相关的文献综述。我们首先介绍一般概念处理实时系统，最坏情况下的执行时间（WCET）分析，任务调度。我们还简要介绍了多核平台，时间可预测的多核架构的理想属性然后，我们分类，并简要介绍了从实时文献相关的WCET分析和任务调度的多核平台的主要工作2.1背景2.1.1实时系统实时系统被定义为系统的正确性不仅取决于计算的逻辑结果，而且还取决于结果产生的时间。实时系统受到时间约束。根据这些时间约束的关键程度，实时系统可以分为三类[13]：• 软实时系统：错过最后期限不会导致系统失败，但可能会导致性能下降。软实时系统的示例包括互联网协议（IP）通信、视频流。• 硬实时系统：错过最后期限可能会对这些系统造成灾难性的后果。硬实时系统的示例包括发动机控制单元、汽车系统中的巡航控制系统、飞行控制系统和化学/核工厂控制系统。13ttjstj英国广播公司CJ时间TJ图2.1：实时任务为了支持硬实时应用程序，在设计实时系统时需要以下属性[13]。• 很准时。实时系统必须及时产生正确的结果。换句话说，必须同时满足功能正确性和时序正确性• 可预测性。任务执行时间的上限必须能够离线估计，并且在系统开始执行之前必须能够检查• 效率大多数实时系统都嵌入到小型设备中，在空间、重量、能量、存储器和计算能力方面都有严格的限制。因此，有效地管理可用资源是实时系统的基本特征。• 容错能力。实时系统不应该被单个硬件和软件故障损坏。一般来说，实时任务可以通过以下参数来表征（如图2.1所示）• 到达时间（ttj）。任务准备好执行的时间，• 开始时间（stj）。任务开始执行的实际时间，• 计算时间（Cj）。隔离执行时任务执行时间的上限，称为最坏情况执行时间（WCET）。• 完成时间（ft j）。 任务完成执行的时间，• Dea d线（dj）。 任务应完成的时间之前。2.1.2最坏情况执行时间估计任务的最坏情况执行时间（WCET）是在任何输入配置和任何初始硬件状态下的最大执行时间[7]。需要任务的WCET来验证时间约束。因此，在硬实时系统的开发和验证过程中，WCET估计是必不可少的一步