论文标题
与依赖关系图安排COFLOWS
Scheduling Coflows with Dependency Graph
论文作者
论文摘要
数据并行计算中的应用程序通常由多个阶段组成。在每个阶段，产生一组中间并行数据流（Coflow）并在服务器之间传递，以使下一阶段开始。尽管已经对安排孤立的Coflows进行了很多研究，但多阶段作业中的Coflows之间的依赖性在很大程度上被忽略了。在本文中，我们考虑计划在共享数据中心网络中以通用DAG（有指示的无环图）表示多阶段作业的Coflows，以最大程度地减少工作的总加权完成时间。这个问题比传统的Coflow计划更具挑战性，因为即使是单个多阶段的工作来最大程度地减少其完成时间也被证明是NP-HARD。 在本文中，我们提出了一种多项式时间算法，其近似值率为$ O（μ\ log（m）/\ log（\ log（m）））$，其中$μ$是作业中的最大coflows，$ m $是服务器的数量。对于工作的基础依赖图是根树的特殊情况，我们修改算法并改善其近似比。为了验证我们的算法的性能，我们使用实际流量轨迹提出了模拟结果，而实际流量轨迹最高为$ 53 \％$ $ $改善了先前的方法。我们通过提供有关将Coflows用一般DAG调度的最佳差距提供的结果来结束论文。
Applications in data-parallel computing typically consist of multiple stages. In each stage, a set of intermediate parallel data flows (Coflow) is produced and transferred between servers to enable starting of next stage. While there has been much research on scheduling isolated coflows, the dependency between coflows in multi-stage jobs has been largely ignored. In this paper, we consider scheduling coflows of multi-stage jobs represented by general DAGs (Directed Acyclic Graphs) in a shared data center network, so as to minimize the total weighted completion time of jobs. This problem is significantly more challenging than the traditional coflow scheduling, as scheduling even a single multi-stage job to minimize its completion time is shown to be NP-hard. In this paper, we propose a polynomial-time algorithm with approximation ratio of $O(μ\log(m)/\log(\log(m)))$, where $μ$ is the maximum number of coflows in a job and $m$ is the number of servers. For the special case that the jobs' underlying dependency graphs are rooted trees, we modify the algorithm and improve its approximation ratio. To verify the performance of our algorithms, we present simulation results using real traffic traces that show up to $53 \%$ improvement over the prior approach. We conclude the paper by providing a result concerning an optimality gap for scheduling coflows with general DAGs.
