Coflow is a recently proposed network abstraction for data-parallel computing applications. This paper considers scheduling coflows with precedence constraints in identical parallel networks, such as to minimize the total weighted completion time of coflows. The identical parallel network is an architecture based on multiple network cores running in parallel. In the divisible coflow scheduling problem, the proposed algorithm achieves $(6-\frac{2}{m})\mu$ and $(5-\frac{2}{m})\mu$ approximate ratios for arbitrary release time and zero release time, respectively, where $m$ is the number of network cores and $\mu$ is the coflow number of the longest path in the precedence graph. In the indivisible coflow scheduling problem, the proposed algorithm achieves $(4m+1)\mu$ and $4m\mu$ approximate ratios for arbitrary release time and zero release time, respectively. In the single network core scheduling problem, we propose a $5\mu$-approximation algorithm with arbitrary release times, and a $4\mu$-approximation without release time. Moreover, the proposed algorithm can be modified to solve the coflows of multi-stage jobs scheduling problem. In multi-stage jobs, coflow is transferred between servers to enable starting of next stage. This means that there are precedence constraints between coflows of job. Our result represents an improvement upon the previous best approximation ratio of $O(\tilde{\mu} \log(N)/ \log(\log(N)))$ where $\tilde{\mu}$ is the maximum number of coflows in a job and $N$ is the number of servers.
翻译: Coflow 是最近为数据平行计算应用程序提议的网络抽象 。 本文考虑在相同的平行网络中, 以优先限制的方式安排 complow 和优先限制, 例如, 以最小化组合的超重完成时间 。 相同的平行网络是一个基于多个网络核心的平行结构 。 在可辨别的共流列表问题中, 拟议的算法在任意发布时间和零发布时间中分别达到$( 6-\ frac{ 2 ⁇ m}\ mu$ 和 $( 5-\\ frac{ 2\\ m} m}\ mu$ mum 。 在任意发布时间和零发布时间中, 分别使用 $( 5\ mu- accolate) 的比例, 网络核心核心核心核心数的数量和 $( $\\\ mudealdeal_ $\\\ moxxxxxxxxxxxx 。 此外, 提议的算算法可以将前阶段工作周期内的工作流量调整为多阶段的工作限制。 。 。 。 。 工作周期内的拟议演算法是多阶段的工作流 。 。 运行 。 。 运行 。 运行 。 运行 。 。 将 将 将工作周期 。 。 将 。 。