Parallel Real-Time Scheduling of DAGs
Parallel Real-Time Scheduling of DAGs
复制标题
DOI：
10.1109/tpds.2013.2297919
复制
发表时间：
2014-12
影响因子：
5.3
通讯作者：
Abusayeed Saifullah;D. Ferry;Jing Li;Kunal Agrawal;Chenyang Lu;C. Gill
中科院分区：
文献类型：
--
作者：
Abusayeed Saifullah;D. Ferry;Jing Li;Kunal Agrawal;Chenyang Lu;C. Gill
最近，多核处理器已成为处理器设计的主流。为了充分利用多核处理，计算密集型实时系统必须利用任务内的并行性。在本文中，我们解决了确定性并行任务的一般模型的实时调度问题，其中每个任务被表示为有向的无环图（DAG），其节点具有任意执行要求。我们证明了用于多核处理器的一般DAG任务的先发制性和非降低实时时间表的处理器速度增强范围。我们首先将每个DAG分解为自己的释放时间和截止日期的顺序任务。然后，我们证明可以使用具有4个资源增强限制的Preementive Global EDF来安排这些已分解的任务。该界限与更限制的模型的最著名界限一样好，并且是第一个通用DAG模型的界限。我们还证明，分解具有4个资源增强限制，以及不断的非抢先率开销，用于非抢先的全球EDF调度。据我们所知，这是针对并行任务的非首次调整的第一个资源增强。最后，我们通过模拟评估我们的分析结果，这些模拟表明派生的资源增强界限在实践中是安全的。
Recently, multi-core processors have become mainstream in processor design. To take full advantage of multi-core processing, computation-intensive real-time systems must exploit intra-task parallelism. In this paper, we address the problem of realtime scheduling for a general model of deterministic parallel tasks, where each task is represented as a directed acyclic graph (DAG) with nodes having arbitrary execution requirements. We prove processor-speed augmentation bounds for both preemptive and nonpreemptive real-time scheduling for general DAG tasks on multi-core processors. We first decompose each DAG into sequential tasks with their own release times and deadlines. Then we prove that these decomposed tasks can be scheduled using preemptive global EDF with a resource augmentation bound of 4. This bound is as good as the best known bound for more restrictive models, and is the first for a general DAG model. We also prove that the decomposition has a resource augmentation bound of 4 plus a constant non-preemption overhead for non-preemptive global EDF scheduling. To our knowledge, this is the first resource augmentation bound for non-preemptive scheduling of parallel tasks. Finally, we evaluate our analytical results through simulations that demonstrate that the derived resource augmentation bounds are safe in practice.