Ecole d'ingénieur et centre de recherche en Sciences du numérique

Simple algorithms for scheduling moldable tasks

Wu, Xiaohu; Loiseau, Patrick

Submitted on ArXiV, October 22nd, 2016

We study the theoretical problem of scheduling a set of n independent moldable tasks on m processors, which arises in multiprocessor scheduling from large scale parallel computations. It is assumed that the speedup of executing a task is linear when it is assigned a small set of no more than h processors; its workload increases with the number of assigned processor but its execution time decreases in a linear or nonlinear way when this number is greater than h. The special case where h=1 has been extensively studied to minimize the makespan and the case where h>1 is recently verified by many applications. In this paper, a general procedure is proposed to address the problem in the general case. In particular, we propose an r(h)-approximation algorithm with a complexity of O(n) for the objective of maximizing the sum of values of tasks completed by a deadline, and an (1+\epsilon)/r(h)-approximation algorithm with a complexity of O(nlog(n/\epsilon)) for the objective of minimizing the makespan. For example, r(10)=4/5-max{k-1, 11}/m, and r(27)=7/8-max{k-1, 32.125}/m, where k is the upper bound on parallelized execution (in large scale parallel computations such as cluster computing, m >> k and k/m approaches 0).

Arxiv Bibtex

Titre:Simple algorithms for scheduling moldable tasks
Mots Clés:Parallel Scheduling, Approximation Algorithms, Malleable
Département:Data Science
Eurecom ref:5045
Copyright: © EURECOM. Personal use of this material is permitted. The definitive version of this paper was published in Submitted on ArXiV, October 22nd, 2016 and is available at :
Bibtex: @techreport{EURECOM+5045, year = {2016}, title = {{S}imple algorithms for scheduling moldable tasks}, author = {{W}u, {X}iaohu and {L}oiseau, {P}atrick}, number = {EURECOM+5045}, month = {10}, institution = {Eurecom}, url = {},, }
Voir aussi: