Result: Scheduling moldable {BSP} tasks

Title:
Scheduling moldable {BSP} tasks
Authors:
Dutot, Pierre-François, Goldman, Alfredo, Kon, Fabio, Netto, Marco
Contributors:
Parallel algorithms and load sharing (APACHE), Informatique et Distribution (ID-IMAG), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Centre Inria de l'Université Grenoble Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Université Joseph Fourier - Grenoble 1 (UJF), Department of Computer Science (USP), Universidade de São Paulo = University of São Paulo (USP)
Source:
11th Workshop on Job Scheduling Strategies for Parallel Processing. :157-172
Publisher Information:
CCSD; Springer Verlag, 2005.
Publication Year:
2005
Collection:
collection:UGA
collection:IMAG
collection:CNRS
collection:INRIA
collection:UNIV-GRENOBLE1
collection:INPG
collection:INRIA-RHA
collection:INRIA_TEST
collection:TESTALAIN1
collection:INRIA2
collection:INRIA-RENGRE
collection:TEST-UGA
Subject Terms:
Scheduling, BSP, Moldable, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.2: Nonnumerical Algorithms and Problems, F.2.2.5: Sequencing and scheduling, [INFO.INFO-DC]Computer Science [cs], Distributed, Parallel, and Cluster Computing [cs.DC]
Original Identifier:
HAL:
Document Type:
Conference conferenceObject<br />Conference papers
Language:
English
Access URL:
https://inria.hal.science/inria-00001078
https://inria.hal.science/inria-00001078v1/document
https://inria.hal.science/inria-00001078v1/file/dgkn_jsspp05.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00001078v1
Database:
HAL

Further Information

Our main goal in this paper is to study the scheduling of parallel BSP tasks on clusters of computers. We focus our attention on special characteristics of BSP tasks, which can use less processors than the original required, but with a particular cost model. We discuss the problem of scheduling a batch of BSP tasks on a fixed number of computers. The objective is to minimize the completion time of the last task (makespan). We show that the problem is difficult and present approximation algorithms and heuristics. We finish the paper presenting the results of extensive simulations under different workloads.