Minimizing the Stretch When Scheduling Flows of Biological Requests

Arnaud Legrand 1 Alan Su 2 Frédéric Vivien 3, 4
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
3 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. distributed biological sequence comparison applications. This problem lies in the divisible load framework with negligible communication costs. Thus far, very few results have been proposed in this model. We discuss and select relevant metrics for this framework: namely max-stretch and sum-stretch. We explain the relationship between our model and the preemptive uni-processor case, and we show how to extend algorithms that have been proposed in the literature for the uni-processor model to the divisible multi-processor problem domain. We recall known results on closely related problems, derive new lower bounds on the competitive ratio of any on-line algorithm, present new competitiveness results for existing algorithms, and develop several new on-line heuristics. Then, we extensively study the performance of these algorithms and heuristics in realistic scenarios. Our study shows that all previously proposed guaranteed heuristics for max-stretch for the uni-processor model prove to be particularly inefficient in practice. In contrast, we show our on-line algorithms based on linear programming to be near-optimal solutions for max-stretch. Our study also clearly suggests heuristics that are efficient for both metrics, although a combined optimization is in theory not possible in the general case.
Type de document :
Communication dans un congrès
Symposium on Parallelism in Algorithms and Architectures SPAA\'2006, 2006, Unknown, ACM Press, 2006, <10.1145/1148109.1148124>
Liste complète des métadonnées

https://hal.inria.fr/hal-00789441
Contributeur : Arnaud Legrand <>
Soumis le : lundi 18 février 2013 - 11:51:33
Dernière modification le : mercredi 14 décembre 2016 - 01:09:20

Identifiants

Collections

Citation

Arnaud Legrand, Alan Su, Frédéric Vivien. Minimizing the Stretch When Scheduling Flows of Biological Requests. Symposium on Parallelism in Algorithms and Architectures SPAA\'2006, 2006, Unknown, ACM Press, 2006, <10.1145/1148109.1148124>. <hal-00789441>

Partager

Métriques

Consultations de la notice

135