在预加载了共享总线的异构平台上调度任务图应用程序

《ACM Transactions on Design Automation of Electronic Systems》：Scheduling Task Graph Applications on Preloaded Shared-Bus based Heterogeneous Platforms

现代嵌入式控制系统在CPS中的应用常需动态调度新DTG应用至预加载异构平台，解决静态调度无法应对的动态任务加入问题，提出的DSPP算法通过优化任务和消息调度实现makespan平均降低10%。

　　

摘要

在《信息物理系统》（CPSs）中的现代嵌入式控制应用通常具有复杂的功能相互依赖性，因此被表示为有向无环任务图（DTGs）。为了满足复杂的性能要求以及与部署相关的逻辑约束，这些应用可能需要在一个分布式和异构的平台上实现。很多时候，需要在已经运行的平台上动态运行新的应用程序，例如“报警服务例程”，而该平台上已经存在其他应用程序任务及其消息。尽管有大量文献讨论了在不同类型平台上静态调度DTGs的方法，但据我们所知，目前还没有针对在已经占用的平台上动态调度新到达的DTGs应用程序的显著研究成果。这种策略缺失的主要原因可能是与动态插入新DTGs应用程序相关的固有设计和计算复杂性——即需要有效地重新利用现有调度中的空闲时间槽。在为动态到达的应用程序提供快速响应时间的同时，新生成的调度方案还必须确保不会导致已经运行的应用程序错过截止日期。DSPP（即“预加载平台上的DTG调度器”）是一种新颖的、旨在最小化任务完成时间（makespan）的调度算法。DSPP是一种基于列表的启发式策略，用于在通过共享总线互连的预加载异构处理元素上协同调度DTG结构化应用程序的任务及其任务间消息。通过使用基准DTGs进行仿真，仔细检验了DSPP的有效性。实验结果表明，在广泛的测试场景中，DSPP的平均任务完成时间可减少约10%，最佳情况下可减少约13%，其性能优于现有的最先进方法。