Efficient Algorithms for Scheduling Moldable Tasks

Abstract

We study the problem of scheduling $n$ independent moldable tasks on $m$ processors that arises in large-scale parallel computations. When tasks are monotonic, the best known result is a $(\frac{3}{2}+\epsilon )$-approximation algorithm for makespan minimization with a complexity linear in $n$ and polynomial in $\log m$ and $\frac{1}{\epsilon }$ where $\epsilon$ is arbitrarily small. We propose a new perspective of the existing speedup models: the speedup of a task $T_j$ is linear when the number $p$ of assigned processors is small (up to a threshold ${\delta }_j$) while it presents monotonicity when $p$ ranges in $[{\delta }_j,k_j]$; the bound $k_j$ indicates an unacceptable overhead when parallelizing on too many processors. The generality of this model is proved to be between the classic monotonic and linear-speedup models. For any given integer $\delta \ge 5$, let $u=\lceil \sqrt[2]{\delta }\rceil -1\ge 2$. In this paper, we propose a $\frac{1}{\theta (\delta )}(1+\epsilon )$-approximation algorithm for makespan minimization where $\theta (\delta )=\frac{u+1}{u+2}\left(1-\frac{k}{m}\right)$ ($m\gg k$). As a by-product, we also propose a $\theta (\delta )$-approximation algorithm for throughput maximization with a common deadline.

arXiv commentAccepted by European Journal of Operational Research