Efficient Algorithms for Scheduling Moldable Tasks

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}+ϵ)$-approximation algorithm for makespan minimization with a complexity linear in $n$ and polynomial in $\log m$ and $\frac{1}{ϵ}$ where $ϵ$ 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=\left\lceil \sqrt[2]{\delta} \right\rceil-1\geq 2$\mathrm{.}Inthispaper,weproposea$\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$)\mathrm{.}Asaby-product,wealsoproposea$\theta(\delta)$-approximation algorithm for throughput maximization with a common deadline.