Skip to Main content Skip to Navigation
Journal articles

Optimizing memory allocation for multi stage scheduling including setup times

Abstract : Mapping linear workflow applications onto a set of homogeneous processors can be optimally solved in polynomial time for the throughput objective with fewer processors than stages. This result even holds true, when setup times occur in the execution and homogeneous buffers are available for the storage of intermediate results. In this kind of applications, several computation stages are interconnected as a linear application graph, and each stage holds a buffer of limited size where intermediate results are stored and a processor setup time occurs when passing from one stage to another. In this paper, we tackle the problem where the buffer sizes are not given beforehand and have to be fixed before the execution to maximize the through-put within each processor. The goal of this work is to minimize the cost induced by the setup times by allocating buffers with proportional sizes of each other. We present a closed formula to compute the optimal buffer allocation in the case of non-decreasing setup costs in the linear application. For the case of unsorted setup times, we provide competitive heuristics that are validated via extensive simulation. Three non scalable brute force algorithms are also provided to compare heuristic approaches to optimal ones for small applications and to evaluate the relevance of our approach
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-02082773
Contributor : Equipe Roma <>
Submitted on : Thursday, March 28, 2019 - 2:24:13 PM
Last modification on : Wednesday, September 16, 2020 - 10:42:50 AM
Long-term archiving on: : Saturday, June 29, 2019 - 2:12:58 PM

File

journalOfScheduling-sti-bi_sub...
Files produced by the author(s)

Identifiers

Citation

Anne Benoit, Mathias Coqblin, Jean-Marc Nicod, Veronika Rehn-Sonigo. Optimizing memory allocation for multi stage scheduling including setup times. Journal of Scheduling, Springer Verlag, 2016, 19 (6), pp.641-658. ⟨10.1007/s10951-015-0437-x⟩. ⟨hal-02082773⟩

Share

Metrics

Record views

147

Files downloads

249