• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >Parallel Real-Time Scheduling of DAGs
【24h】

Parallel Real-Time Scheduling of DAGs

机译：DAG的并行实时调度

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 real-time 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 non-preemptive 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 . 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 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.
机译：最近，多核处理器已成为处理器设计的主流。为了充分利用多核处理，计算密集型实时系统必须利用任务内并行性。在本文中，我们解决了确定性并行任务的通用模型的实时调度问题，其中每个任务都表示为有向无环图（DAG），其中节点具有任意执行要求。我们证明了多核处理器上常规DAG任务的抢先式和非抢先式实时调度的处理器速度扩展范围。我们首先将每个DAG分解为具有各自发布时间和截止日期的顺序任务。然后，我们证明可以使用抢占式全局EDF（资源扩展范围为）来调度这些分解的任务。此边界与限制性更强的模型的最著名边界一样好，并且是常规DAG模型的第一个边界。我们还证明，对于非抢先全局EDF调度，分解具有的资源扩充范围加上恒定的非抢先开销。据我们所知，这是并行任务的非抢占式调度的第一个资源扩充范围。最后，我们通过模拟评估我们的分析结果，这些模拟证明所导出的资源扩充范围在实践中是安全的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号