论文标题
并行路径进程DAG调度
Parallel Path Progression DAG Scheduling
论文作者
论文摘要
为了满足现代网络物理系统不断增长的性能需求，越来越多地利用了多处理器体系结构。为了在硬实时系统中有效利用其潜在的并行性，需要适当的任务模型和调度算法，这些算法允许提供定时保证。这种调度算法和相应的最坏情况响应时间分析通常由于基于最坏情况假设的悲观分析而导致资源过度提供。因此，需要以高资源效率进行调度算法和分析。一个突出的并行任务模型是定向 - 环形图纸（DAG）任务模型，其中优先级的副作用表达并行性。 本文研究了零星任意deadline DAG任务的实时调度问题。我们提出了一个仅具有两个不同子任务优先级的路径并行进程调度属性，该属性允许同时跟踪路径集合的执行。这种新颖的方法可显着改善高度平行DAG结构的平行DAG任务的最新响应时间分析。基于此属性设计了两个分层调度算法，扩展了并行路径进程属性，并改善了零星的任意deadline DAG任务集的响应时间分析。
To satisfy the increasing performance needs of modern cyber-physical systems, multiprocessor architectures are increasingly utilized. To efficiently exploit their potential parallelism in hard real-time systems, appropriate task models and scheduling algorithms that allow providing timing guarantees are required. Such scheduling algorithms and the corresponding worst-case response time analyses usually suffer from resource over-provisioning due to pessimistic analyses based on worst-case assumptions. Hence, scheduling algorithms and analysis with high resource efficiency are required. A prominent parallel task model is the directed-acyclic-graph (DAG) task model, where precedence constrained subjobs express parallelism. This paper studies the real-time scheduling problem of sporadic arbitrary-deadline DAG tasks. We propose a path parallel progression scheduling property with only two distinct subtask priorities, which allows to track the execution of a collection of paths simultaneously. This novel approach significantly improves the state-of-the-art response time analyses for parallel DAG tasks for highly parallel DAG structures. Two hierarchical scheduling algorithms are designed based on this property, extending the parallel path progression properties and improving the response time analysis for sporadic arbitrary-deadline DAG task sets.
