In the paper, the problem of scheduling a set of n malleable tasks on m parallel computers is considered. The tasks may be executed by several processors simultaneously and the processing speed of a task is a function of the number of processors alloted. The problem is motivated by real-life applications of parallel computer systems in scientific computing of highly parallelizable tasks. Starting from the continuous version of the problem (i. e. where the tasks may require a fractional part of the resources), we propose a general approximation algorithm with a performance guarantee equal to 2. Then, some improvements are derived that lead to a very good average behavior of the scheduling algorithm.
Jul 29, 2014
May 22, 2014
|Suboptimal Approaches to Scheduling Malleable Tasks
|Jul 29, 2014
Błażewicz Jacek Cysewska-Sobusiak Anna, Lerczak Agata, Kasprzak Marta, Markiewicz Wojciech T.
Błażewicz Jacek Gwóźdź Łukasz, Kasprzak Marta, Przysucha Marcin
Błażewicz Jacek Kaczmarek Janusz, Marta Kasprzak, Jan Węglarz
Błażewicz Jacek Dill Ken, Łukasiak Piotr, Miłostan Maciej
Błażewicz Jacek Hammer P., Łukasiak P.