Result: Minimizing the stretch when scheduling flows of divisible requests

Title:
Minimizing the stretch when scheduling flows of divisible requests
Authors:
Legrand, Arnaud, Su, Alan, Vivien, Frédéric
Contributors:
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), Middleware efficiently scalable (MESCAL), 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), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Centre Inria de l'Université Grenoble Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon), Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), INRIA, LIP
Source:
[Research Report] RR-6002. :76-76
Publisher Information:
CCSD, 2006.
Publication Year:
2006
Collection:
collection:ENS-LYON
collection:UGA
collection:IMAG
collection:CNRS
collection:INRIA
collection:UNIV-LYON1
collection:INPG
collection:INRIA-RHA
collection:INRIA-RRRT
collection:PRUNEL
collection:LIP
collection:INRIA_TEST
collection:TESTALAIN1
collection:INRIA2
collection:LARA
collection:INRIA-RENGRE
collection:INRIA-300009
collection:UDL
collection:UNIV-LYON
collection:TEST-UGA
Subject Terms:
divisible load, linear programming, stretch, scheduling, heterogeneous computing, Bioinformatics, Ordonnancement, Flot pondéré, Bioinformatique, Plates-formes hétérogènes, Programmation linéaire, Tâches divisibles, 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-BI]Computer Science [cs], Bioinformatics [q-bio.QM], [SDV.BIBS]Life Sciences [q-bio], Quantitative Methods [q-bio.QM], [INFO.INFO-DC]Computer Science [cs], Distributed, Parallel, and Cluster Computing [cs.DC]
Original Identifier:
HAL:
Document Type:
Report report<br />Reports
Language:
English
Access URL:
https://inria.hal.science/inria-00108524
https://inria.hal.science/inria-00108524v3/document
https://inria.hal.science/inria-00108524v3/file/FinalRR.inria.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00108524v3
Database:
HAL

Further Information

In this paper, we consider the problem of scheduling 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, we show how to minimize the max-stretch on unrelated machines either in the divisible load model or with preemption, we derive new lower bounds on the competitive ratio of any on-line algorithm, we present new competitiveness results for existing algorithms, and we develop several new on-line heuristics. We also address the Pareto optimization of max-stretch. 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 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.