Large scale execution of a bioinformatic application on a volunteer grid

Abstract : Scheduling problems are already difficult on traditional parallel machines. They becomeextremely challenging on heterogeneous clusters, even when embarrassingly parallel applications are considered. In this paper we deal with the problem of scheduling multiple applications, made of collections of independent and identical tasks, on a heterogeneous master-worker platform. The applications are submitted online, whichmeans that there is no a priori (static) knowledge of the workload distribution at thebeginning of the execution. The objective is to minimize the maximum stretch, i.e. the maximum ratio between the actual time an application has spent in the system and the time this application would have spent if executed alone. On the theoretical side, we design an optimal algorithm for the offline version of the problem (when all release dates and application characteristics are known beforehand). We also introduce several heuristics for the general case of online applications. On the practical side, we have conducted extensive simulations and MPI experiments, showing that we are able to deal with very large problem instances in a few seconds. Also, the solution that we compute totally outperforms classical heuristics from theliterature, thereby fully assessing the usefulness of our approach.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02102660
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 3:30:20 PM
Last modification on : Friday, April 19, 2019 - 1:38:15 AM

File

RR2007-49.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102660, version 1

Collections

Citation

Viktors Bertis, Raphaël Bolze, Frédéric Desprez, Kevin Reed. Large scale execution of a bioinformatic application on a volunteer grid. [Research Report] LIP RR-2007-49, Laboratoire de l'informatique du parallélisme. 2007, 2+16p. ⟨hal-02102660⟩

Share

Metrics

Record views

18

Files downloads

49