Minimizing the stretch when scheduling flows of biological requests

Arnaud Legrand 1, 2 Alan Su 1, 2 Frédéric Vivien 1, 2
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this paper, we consider the problem of scheduling comparisons of motifs against biological databanks. This problem lies in the divisible load framework with negligible communication costs. Thus far, very few results have been proposed in this model. We first explain the relationship between this model and the preemptive uni-processor one. After having selected a few relevant metrics (max-stretch and sum-stretch), we show how to extend algorithms that have been proposed in the literature for the uni-processor model to our setting. Then we extensively study the performance of these algorithms in realistic scenarios. Our study clearly suggest an efficient heuristic for each of the two metrics, though a combined optimization is in theory not possible in the general case.
Type de document :
Rapport
[Research Report] RR-5724, INRIA. 2005, pp.22
Liste complète des métadonnées


https://hal.inria.fr/inria-00070293
Contributeur : Rapport de Recherche Inria <>
Soumis le : vendredi 19 mai 2006 - 19:57:21
Dernière modification le : samedi 17 septembre 2016 - 01:27:42
Document(s) archivé(s) le : dimanche 4 avril 2010 - 20:51:44

Fichiers

Identifiants

  • HAL Id : inria-00070293, version 1

Collections

Citation

Arnaud Legrand, Alan Su, Frédéric Vivien. Minimizing the stretch when scheduling flows of biological requests. [Research Report] RR-5724, INRIA. 2005, pp.22. <inria-00070293>

Partager

Métriques

Consultations de
la notice

166

Téléchargements du document

126