Offloading Dependent Tasks with Communication Delay and Deadline Constraint
Offloading Dependent Tasks with Communication Delay and Deadline Constraint
复制标题
DOI：
10.1109/infocom.2018.8486305
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
S. Sundar;B. Liang
中科院分区：
文献类型：
--
作者：
S. Sundar;B. Liang
在一个由异构本地处理器和远程云服务器组成的通用云计算系统中，我们研究了由依赖任务组成的应用程序的调度决策。我们制定了一个优化问题，以找到卸载决策，使总体应用程序执行成本最小化，并受应用程序完成截止日期的约束。由于这个问题是np困难的，我们提出了一种启发式算法，称为个体时间分配与贪婪调度（ITAGS），以获得有效的解决方案。ITAGS首先使用原始问题的二进制放宽版本为每个单独的任务分配完成期限，然后在允许的时间范围内贪婪地优化每个任务的调度。通过真实应用的跟踪仿真，以及各种随机生成的任务树，我们研究了ITAGS的性能，突出了应用截止日期、通信延迟、处理器数量和任务数量的影响。我们进一步证明了ITAGS相对于现有替代品的巨大性能优势。
We study the scheduling decision for an application consisting of dependent tasks, in a generic cloud computing system comprising a network of heterogeneous local processors and a remote cloud server. We formulate an optimization problem to find the offloading decision that minimizes the overall application execution cost, subject to an application completion deadline. Since this problem is NP-hard, we propose a heuristic algorithm termed Individual Time Allocation with Greedy Scheduling (ITAGS) to obtain an efficient solution. ITAGS first uses a binary-relaxed version of the original problem to allocate a completion deadline to each individual task, and then greedily optimizes the scheduling of each task subject to its time allowance. Through trace-based simulation using real applications, as well as various randomly generated task trees, we study the performance of ITAGS, highlighting the effect of the application deadline, communication delay, number of processors, and number of tasks. We further demonstrate the substantial performance advantage of ITAGS over existing alternatives.