Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

Minimizing the stretch when scheduling flows of divisible requests

Abstract : In this paper, we consider the problem of scheduling distributed biological sequencecomparison 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 showhow 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-linealgorithm, 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 thesealgorithms 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-linealgorithms based on linear programming to be near-optimal solutions for maxstretch.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.
Document type :
Complete list of metadata

Cited literature [36 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 3:30:14 PM
Last modification on : Wednesday, March 2, 2022 - 1:28:05 PM


Files produced by the author(s)


  • HAL Id : hal-02102657, version 1



Arnaud Legrand, Alan Su, Frédéric Vivien. Minimizing the stretch when scheduling flows of divisible requests. [Research Report] LIP RR-2008-08, Laboratoire de l'informatique du parallélisme. 2008, 2+59p. ⟨hal-02102657⟩



Record views


Files downloads