面向多核平台的缓存感知离线实时调度：算法与实现

年份（2018）论文/雷恩第一大学布列塔尼卢瓦尔大学印章下为的等级雷恩第一大学博士提及：信息学数学博士学校提交人越南英在IRISA研究单位-UMR 6074计算机科学和随机系统研究所编写面向多核平台的缓存感知离线实时调度：算法与实现论文答辩于2018年陪审团由以下人员组成：史蒂文·德里安雷恩大学教授1/校长克里斯汀·罗昌格Paul Sabatier图卢兹大学教授/报告员马修·简工程师-研究员，CEA/报告员达米安·哈迪雷恩大学高级讲师1/考官弗雷德里克·彼得罗ENSIMAG格勒诺布尔教授/考官伊莎贝尔·普奥特雷恩大学教授1/主任 主题确认文件这篇论文在许多人的支持下成为现实我想对他们所有人表示衷心的感谢。首先，我要感谢我的导师，雷恩第一大学的Isabelle PUAUT教授和Damien Hardy副教授，感谢他们的大力支持和指导。我还要感谢我的委员会成员，他们给了我富有成效的反馈，以提高论文的质量此外，我感谢所有长期工作人员和我在PACAP团队的同事的支持你的帮助使我的工作更容易，更愉快。最后，我想感谢我的家人。你总是鼓励和相信我，你帮助我专注于什么是一个甜蜜的奖励。0内容表内容物内容表法语论文摘要FranCaise 31导言71硬实时多核系统：定时可预测性挑战2目标和解决方案概述92.1缓存感知调度算法92.2实现缓存感知时间表103捐款104组织112实时系统和多核平台：背景和最新技术水平2.1背景132.1.1实时系统132.1.2最坏情况执行时间估计142.1.3实时任务调度162.1.4时间可预测的多核硬件182.1.5隐藏记忆202.2多核系统的定时分析：最新技术水平2.2.1WCET多核架构技术分析232.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实际挑战544.3.1由调度程序554.3.2共享总线争用554.3.3由于计划的执行而延迟任务的开始时间ING计时功能554.3.4缺乏硬件实现的数据缓存一致性564.4时间驱动的缓存感知时间表对实际问题的适应4.4.1数据结构584.4.2执行应用程序的限制4.4.3使基本的隐蔽意识时间表适应实际效果4.5代码生成器554.6实验评估694.6.1实验条件704.6.1.1基准测试704.6.1.2常数估计值704.6.1.3WCET和无保留时的缓存丢失估计数.............................................. 714.6.1.4实验环境724.6.2实验结果724.6.2.1在Kalray MPPA上运行时，验证基准测试的功能正确性和定时正确256计算集群724.6.2.2量化不同实践问题对适应性隐藏意识时间表的影响......................4.6.2.3ACILP 74的性能评估4.7相关工作764.8摘要775结论79参考书目89作者的出版物图93表摘要99Fran Caise语言论文摘要实时系统，其响应时间的尊重与功能校正一样重要，现在已经渗透到我们的日常生活。特别是，实时应用可以在汽车、飞机、核电站中找到此外，根据[1]，嵌入式系统市场在未来几年肯定会出现2016年，嵌入式系统市场的价值为845.5亿美元，预计2017年至2023年将以4.05%的复合年增长率增长随着对安全但计算密集型应用的需求不断增长，单核架构不再是部署实时系统的明智选择，这是由于此类架构的技术限制（例如，功率为了克服这一限制，芯片制造巨头们创造了新的处理器，称为多核处理器，其中多个核心集成在同一个芯片上。事实证明，多核处理器在能效方面更高，多核架构的示例包括Kalray MPPA-256 [4]、Tilera Tile CPU [5]或英特尔的将实时系统迁移到多核处理器使用可以满足资源密集型应用程序的性能期望，但也会带来许多时间可预测性问题由于多核处理器的硬件效应，确保关键任务和并行应用程序的时间限制是一项挑战。L’un des challenges les plus importants est d’estimer, avec précision, le Pire Tempsd’Exécution 有多种方法可用于估计单核处理器上的PTE [7]。这些技术同时考虑了程序的执行路径和内核的微体系结构。将这些方法扩展到多核体系结构是困难的，并且由于诸如高速缓存或总线之类的硬件资源在核之间共享，使得任务的PTE估计依赖于在其他核上运行的其他任务的执行此外，在具有本地缓存的体系结构上，任务的最差执行时间不再是唯一的它取决于任务的执行上下文实际上，可以考虑与上下文无关的最坏情况估计值，但得到的值过于悲观。对称地，一个任务的PTE的估计n是确定任务的放置和排序所必需的因此，考虑到多核处理器的调度和PTE估计是相互关联的问题，被称为先有鸡还是先有蛋的情况。由于这种相互依赖性，我们认为需要定义考虑到整个多核硬件的调度策略考虑到环境相关的ETP有助于提高调度本文中的论文工作考虑了由于本地缓存的影响而导致的任务PTE目标和解决方案的介绍缓存感知排序算法。我们提出了两种用于具有本地高速缓存的多核架构的调度技术这两种技术都对由任务图建模的单个并行应用程序进行调度，并生成静态分区、非抢先调度。由于本地缓存的影响，每个任务τj不是由单个PTE值表征，而是由一组PTE值表征。当τj之前运行的任务加载到缓存中的cotnn uc没有重用n时，tach的最悲观PTE（表示为P T E τ j）是obs e r v。 一组表示为P TEτi→τj的PTE值表示当τ j重用τ i的s信息e时，τ j的sPTE，该信息e由在同一内核上紧接在τj之前执行的任务τi加载到指令和数据高速缓存中。这两种技术的目标都是生成长度尽可能短的调度。对StreamIt测试套件[10]中的测试用例的实验评估表明，与忽略私有缓存的等效技术相比，缓存感知技术生成的调度长度显著减少在流媒体应用中观察到的调度大小的平均减小此外，所事实上，启发式调度方法由启发式和最优方法生成的调度的大小之间的差异平均为0.7%实现缓存感知的调度方法。我们为集群多核处理器Kalray MPPA-256实现了时间定向和缓存感知调度。据我们所知，我们是第一个为这台机器创建和实现这样一个调度器的公司在• 由于调度程序的执行而导致的缓存污染和任务启动延迟• 共享总线上的竞争;• l’absence这些实验因素增加了任务的执行时间，从而改变了任务的完成时间，从而改变了后续任务的开始时间，以确保任务之间的优先基于这一观察，我们提出了一个PLNE公式，通过使缓存意识调度适应已识别的实验因素来修改缓存此外，我们还提出了一种策略，用于根据应用程序的调度为目标机器生成预期应用程序的代码使用StreamIT套件对基准测试进行的实验验证显示了我们实现的功能和时间此外，我们还证明了使用我们的PLNE公式可以非常快速地找到缓存感知和适应性强的调度最后，我们量化了实验因素对这些排序持续时间的影响，我们能够观察到对排序长度影响最大的因素：争用。贡献本论文的主要贡献如下：• 我们通过实验论证并验证了在多核架构上进行调度时解决私有缓存对任务PTE的影响的重要性• 我们提出了一种基于PLNE的调度方法，为了减少生成调度的时间，我们还提出了一种基于列表调度的启发式技术• 我们提供的实验结果表明，除其他外，所提出的排序器生成的排序比它们的忽略本地缓存的等价物更短。• 我们确定了在Kalray MPPA-256机器上实施缓存感知和时间定向调度时出现的真正挑战，并确定我们制定了克服这些挑战的战略• 我们探讨了组织本文以英文撰写，分为五章。• 在第一章中，我们介绍了这篇论文的概念。首先，我们提出了促使这项工作的问题。然后，我们提出了目标，并概述了为解决其次，我们简要总结了本文的贡献• 在第2章（介绍性章节）中，我们介绍了多核实时系统社区的先决条件知识和相关工作。我们首先介绍了一些涉及实时系统、PTE分析和任务调度的一般概念。我们还简要描述了多核平台、多核架构中所需的可预测性属性以及高速缓存的特性。然后，我们对实时社区在• 在第3章中，我们描述了私有缓存的有意识调度的生成提出了两种用于生成并行应用程序的静态、非抢先调度的调度方法我们还将对所提出的测序方法• 在第4章中，我们介绍了在我们首先描述了然后，我们确定了在部署上述调度过程中出现的实际挑战，并提出了克服已确定挑战的策略最后，实验评估验证了我们的实现在功能和时间上的正确性。• 在第五章中，我们总结了论文的工作，并提出了未来工作的前景第一章简介1硬实时多核系统：可预测的时间挑战实时嵌入式系统，即那些时间要求比性能要求更重要的人现在在我们的日常生活中广泛传播。特别是，实时应用可以在个人汽车、飞机、航天器、核电站中找到。此外，根据[1]，嵌入式系统市场在未来几年可能会出现高增长。2016年，嵌入式系统市场的价值为845.5亿美元，预计2017年至2023年期间将以4.05%的复合年增长率（CAGR）增长。随着对更安全但计算密集型应用程序的需求不断增加，由于架构的技术限制（通常称为电源墙[2]），单核架构不再是部署实时系统的合适选择为了克服这个问题，领先的芯片制造商一直在提供新的通信平台，称为多核平台，其中多个核心集成在一个芯片中。与单核平台相比，多核平台已被证明具有更高的能效和更高的性能与成本比[3]，因为它们通过利用线程级并行性来提高应用程序性能。多核AR架构的示例将实时系统迁移到多核平台提高了计算密集型应用程序性能的满意度，但也提高了由于多核硬件的影响（即，例如，本地缓存、内核之间的共享资源），保证多核平台上安全关键并行应用程序的实时约束是具有挑战性的。一个主要的挑战是准确估计在多核上运行的代码的最坏情况执行时间过去已经为单核架构设计了许多WCET估计方法[7]。这种技术既考虑程序路径，也考虑核心微体系结构。将其扩展到多核架构7核心1核心1隐藏未命中隐藏命中缓存缓存缓存缓存T2T1T2T3nMBA场景1场景2图1.1：调度策略对任务这是具有挑战性的，因为一些硬件资源（如缓存或总线）在内核之间共享，这使得一个任务的WCET依赖于在另一个内核上运行的任务[8，9]。此外，在具有本地缓存的体系结构上，任务的WCET依赖于任务开始执行时的缓存内容，而缓存内容又依赖于调度策略。一个任务的WCET不再是唯一的。它取决于任务的执行上下文（在其之前执行的任务、并发任务），这些事实上，人们可能会考虑一个任务的上下文无关的WCET，但价值会过于悲观。激励性示例。让我们考虑一个由三个任务（称为T1、T2和T3）组成的过于简化的系统，这些任务在双核处理器上运行，每个内核都配备了包含两行的统一私有高速缓存。T1和T2访问相同的存储器块，命名为m，其中T3与T1和T2都是代码和数据独立的。我们考虑了两个执行场景，以揭示调度策略对WCET任务的影响在第一种情况下，T2放置在与T3相同的内核上，并在T3之后执行（如图1.1左侧所示）。在第二种情况下，T2放置在与T1相同的内核上，并在T1之后立即执行（如图1.1右侧所示）。我们假设缓存的内容在开始时是空的。在第一种情况下，T2对存储器块m的请求是缓存未命中，因为在请求时间，存储器块尚未加载到缓存中。因此，T2必须等待，直到存储器块m从主存储器加载到高速缓存。相反，在第二种情况下，T2对存储器块m的请求是高速缓存命中，因为在T1的执行期间存储器块已经存储在高速缓存中由于对高速缓存的访问比对主存储器的访问快得多，因此第二种情况下T2的最坏情况执行时间低于第一种情况下的最坏情况执行时间。此示例显示了由于私有缓存的影响，任务的映射和执行顺序对其最坏情况执行时间的影响。系统地，需要任务的最坏情况执行时间来调度策略，以确定映射和进入任务T1（分裂）（和）T2（FTD）T3（FTD）T4（FTD）T5（FTD）T6（Com-T7（Com-T8（Com-T9（Com-T10（Com-T11（Com-T12（Com-T13（Com-退出任务T14（退出）图1.2：8输入快速傅立叶变换（FFT）应用程序并行版本的任务图[11]任务的计划因此，多核平台的任务调度和WCET估计是相互关联的问题，称为鸡和蛋的情况。论文声称。由于前面提到的相互依赖的问题，我们相信已经定义了能够感知多核硬件的调度策略。将对上下文敏感的WCET作为一项任务而不是一个单独的上下文无关的WCET有助于提高时间表的质量，即缩短时间表长度（或缩短时间）。在本博士论文1的范围内，我们考虑了由于私有缓存的影响而导致的任务WCET的变化2目标和解决方案概述2.1缓存感知调度算法本文的第一个目标是提出缓存感知调度策略，该策略利用任务之间的缓存重用。每个任务都有不同的WCET值，这取决于在同一核心上执行该任务之前执行了哪些其他任务（WCET是上下文敏感的）。所提出的调度策略将任务映射到核心，并在核心上调度任务;目标是计算缓存重用以获得最短调度。 我们关注单个并行应用程序，建模为任务图，其中节点表示任务1本博士工作是PIA项目CAPACITES（时间和安全关键应用的并行计算）的一部分，参考P3425-146781和边表示它们之间的依赖关系此外，在缓存感知时间表生成中，我们只考虑私有缓存的影响，而其他硬件相关因素则有待实现阶段。我们提出了两种不同的方法来确定一个静态分区的非先发制人的时间表，以最小化时间表长度，为一个并行的应用程序，通过考虑任务的WCET的变化，由于重用代码和数据之间的任务第一种方法基于整数线性规划（ILP）公式，并在所考虑的假设下产生最优方案。第二种方法是启发式方法，基于列表调度。所提出的启发式调度方法非常快地产生调度，并且启发式调度的长度接近于最优为了进一步激发我们的研究，让我们考虑一个例子，一个8输入快速傅里叶变换的实现。他的任务图如图3.2所示。 例如，T2和T3函数代码重用，因为它们调用相同的函数，T2和T6函数数据重用，因为T2的输出是T6的输入。在此示例中，当考虑可能在同一内核上连续运行的任务之间的缓存关联性时，我们观察到任务的WCET平均减少了10.7%。通过使用第3章中介绍的整数线性规划（ILP）技术，与其缓存不可知的等效技术相比，该并行应用程序的时间表长度减少了8%。请注意，WCET对本博士工作中任务的定义与文献中定义的不同在文献中，任务的WCET被定义为孤立执行时任务的执行时间的上限我们对任务的WCET的定义取决于任务的执行时间，同时考虑到任务开始时缓存的内容2.2实现缓存感知时间表一旦我们看到了考虑私有缓存对任务调度的影响的好处，我们的下一个目标是在真正的多核硬件上简单地实现时间驱动的缓存感知调度，在实施阶段，我们首先确定了在机器上部署这些计划时出现的实际挑战，如共享总线争用、时间驱动的计划器本身的影响、缺乏硬件实现的数据缓存一致性。这些实际效果需要修改缓存感知时间表。我们提出了一个ILP公式，以使缓存感知时间表适应所确定的实际因素，从而仍然满足任务的优先关系，并且此外，我们还提出了一种策略，用于根据自适应的缓存感知时间表生成要在机器上执行的应用程序代码。3贡献博士研究的主要贡献如下：• 我们论证并通过实验验证了在调度中解决私有缓存对WCET任务的影响的重要性• 提出了一种基于ILP的调度方法和一种启发式调度方法，用于静态查找建模为有向无循环图的并行应用程序的分区非优先调度• 我们提供的实验结果表明，所提出的调度技术导致比其缓存不可知等效技术更短的调度。• 我们确定了在Kalray MPPA-256机器上实现时间驱动的缓存感知调度时出现的实际挑战，并提出了克服所确定挑战的策略。• 我们研究了不同的实践因素对隐蔽意识时间表的影响4组织本文的其余部分分为三个主要章节。在第2章中，我们介绍了实时多核系统的基本背景和文献综述我们首先介绍了一些处理实时系统、WCET分析和任务调度的一般概念我们还简要描述了多核平台、时间可预测的多核架构的期望属性以及高速缓存存储器的特性。然后，我们对与多核平台的WCET分析和任务调度相关的实时文献中的主要工作进行了分类和简要描述。这使我们能够确定一些尚未深入研究的方面，特别是考虑到私有缓存影响的一旦介绍了这些基础知识，我们就介绍了博士工作的不同贡献。在第3章中，我们描述了缓存感知时间表的生成。提出了两种用于生成并行应用程序的静态分区非优先调度的调度方法，包括最优方法和启发式方法。第4章介绍了在Kalray MPPA-256机器上实现时间驱动的缓存感知调度我们首先描述了机器的体系结构和我们的时间驱动调度程序实现。然后，我们确定了在机器上部署时间驱动的缓存感知调度时出现的实际挑战，并提出了克服已确定问题的策略。最后，在第五章中，我们总结了博士的工作，并提出了未来工作的一些观点。第二章实时系统和多核平台：背景和最新技术水平在本章中，我们介绍了实时多核系统的基本背景和文献综述。我们首先介绍了处理实时系统、最坏情况执行时间（WCET）分析和任务调度的一般概念我们还简要描述了多核平台、时间可预测的多核架构的期望属性以及高速缓存存储器的特性。然后，我们对与多核平台的WCET分析和任务调度相关的实时文献中的主要工作进行了2.1背景2.1.1实时系统实时系统被定义为系统的正确性不仅取决于计算的逻辑结果，而且取决于产生结果的时间。实时系统受时间限制。根据这些定时约束的关键性，实时系统可以分为三类：• 软实时系统：缺少最后期限不会导致系统故障，但会导致性能下降。软实时系统的示例包括互联网协议（IP）通信、视频流。• 硬实时系统：缺少最后期限可能会对这些系统造成灾难性后果。硬实时系统的示例包括发动机控制单元、汽车系统中的巡航控制系统、飞行控制系统和化学/核电站控制系统。13TTJSTJFtJDJCJ时间Tj图2.1：实时任务为了支持硬实时应用，在设计实时系统时需要以下属性。• 时间性。实时系统必须以及时的方式产生正确的结果换句话说，必须满足功能正确性和定时正确性。• 可预测性。必须能够离线估计任务执行时间的上限，并且必须能够在系统开始执行之前检查任务的计时约束的满足情况。• 效率。大多数实时系统都嵌入在小型设备中，在空间、重量、功耗、内存和计算能力方面存在严格限制。因此，有效地管理可用资源是实时系统的一个基本特征。• 公差。实时系统不应因单个硬件和软件故障而受损。一般来说，实时任务可以通过以下参数来表征（如图2.1所示）• 到达时间（ttj）。任务准备好执行的时间，• 开始时间（STj）。任务开始运行的实际时间。• 计算时间（Cj）。隔离执行时任务执行时间的上限，称为最坏情况执行时间（WCET）。• 结束时间（ft j）。任 务 完成其执行的时间，• D线（DJ）。应完成的任务之前的时间。2.1.2最坏情况执行时间估计任务的最坏情况执行时间（WCET）是其在任何输入配置和任何初始硬件状态下的最大执行时间。需要任务的WCET来验证时间限制。因此，WCET评估是硬实时系统开发和验证过程中的重要一步