Energy-Efficient Real-Time Scheduling of DAG Tasks
Energy-Efficient Real-Time Scheduling of DAG Tasks
复制标题
DOI：
10.1145/3241049
复制
发表时间：
2018-11-01
影响因子：
2
通讯作者：
Xiong, Haoyi
中科院分区：
文献类型：
--
作者：
Bhuiyan, Ashikahmed;Guo, Zhishan;Xiong, Haoyi
研究了一组具有隐式截止期的偶发有向无环图（DAG）任务的能量感知实时调度问题。在满足所有实时约束的同时，我们试图确定最佳的任务分配和执行模式，使整个平台的平均功耗最小化。据我们所知，这是第一个工作，解决了多核调度多个DAG任务的功耗问题，并允许任务内处理器共享。首先，我们采用基于分解的框架，联邦调度，并提出了一个能源次优调度。然后，我们推导出一个近似算法，以确定处理器合并在一起，以进一步提高能源效率。所提出的方法的有效性进行评估，理论上通过近似比的界限，也通过仿真研究实验。随机生成的工作负载上的实验结果表明，我们的算法实现了60%至68%的节能相比，现有的DAG任务调度器。
This work studies energy-aware real-time scheduling of a set of sporadic Directed Acyclic Graph (DAG) tasks with implicit deadlines. While meeting all real-time constraints, we try to identify the best task allocation and execution pattern such that the average power consumption of the whole platform is minimized. To our knowledge, this is the first work that addresses the power consumption issue in scheduling multiple DAG tasks on multi-cores and allows intra-task processor sharing. First, we adapt the decomposition-based frame-work for federated scheduling and propose an energy-sub-optimal scheduler. Then, we derive an approximation algorithm to identify processors to be merged together for further improvements in energy-efficiency. The effectiveness of the proposed approach is evaluated both theoretically via approximation ratio bounds and also experimentally through simulation study. Experimental results on randomly generated workloads show that our algorithms achieve an energy saving of 60% to 68% compared to existing DAG task schedulers.