Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time
Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time
复制标题
在线调度并行 DAG 作业以最小化平均流程时间
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Benjamin Moseley
中科院分区：
文献类型：
--
作者：
Kunal Agrawal;Jing Li;Kefu Lu;Benjamin Moseley
在这项工作中，我们研究了以最小化平均流时间为目标的可并行作业在线调度问题。每个并行作业被建模为一个DAG，其中每个节点是一个顺序任务，每条边代表任务之间的依赖关系。以前的工作集中在一种称为任意加速曲线设置的并行化模型上，在该模型中，已知可伸缩算法。然而，DAG模型更广泛地被从业人员使用，因为许多由并行编程语言和库生成的作业可以在此模型中表示。然而，在有多个工作的在线环境中，这种模式鲜为人知。DAG模型和加速曲线模型是不可比的，其中一个模型的算法结果并不立即意味着另一个模型的结果。以前的工作留下了一个悬而未决的问题，即在DAG设置下，在线算法是否可以是O(1)-与O(1)-速度竞争-平均流时间。在这项工作中，我们肯定地回答了这个问题，给出了一个可伸缩的算法，它对任何e>；0都是(1+e)速度O([方程])竞争的。我们进一步介绍了用于可并行作业调度的第一个贪婪算法-我们的算法是最短作业优先算法的推广。贪婪算法由于简单，在实践中是最有用的算法之一。我们证明了该算法对任意e>；0是(2+e)-速度O([方程])-竞争的。
In this work, we study the problem of scheduling parallelizable jobs online with an objective of minimizing average flow time. Each parallel job is modeled as a DAG where each node is a sequential task and each edge represents dependence between tasks. Previous work has focused on a model of parallelizability known as the arbitrary speed-up curves setting where a scalable algorithm is known. However, the DAG model is more widely used by practitioners, since many jobs generated from parallel programming languages and libraries can be represented in this model. However, little is known for this model in the online setting with multiple jobs. The DAG model and the speed-up curve models are incomparable and algorithmic results from one do not immediately imply results for the other. Previous work has left open the question of whether an online algorithm can be O(1)-competitive with O(1)-speed for average flow time in the DAG setting. In this work, we answer this question positively by giving a scalable algorithm which is (1 + e)-speed O([EQUATION])-competitive for any e > 0. We further introduce the first greedy algorithm for scheduling parallelizable jobs --- our algorithm is a generalization of the shortest jobs first algorithm. Greedy algorithms are among the most useful in practice due to their simplicity. We show that this algorithm is (2 + e)-speed O([EQUATION])-competitive for any e > 0.