Optimizing memory allocation for multistage scheduling including setup times

Anne Benoit (), Mathias Coqblin (), Jean-Marc Nicod () and Veronika Rehn-Sonigo ()
Additional contact information
Anne Benoit: LIP, École Normale Supérieure de Lyon, CNRS & INRIA
Mathias Coqblin: FEMTO-ST Institute, UFC/CNRS/ENSMM/UTBM
Jean-Marc Nicod: FEMTO-ST Institute, UFC/CNRS/ENSMM/UTBM
Veronika Rehn-Sonigo: FEMTO-ST Institute, UFC/CNRS/ENSMM/UTBM

Journal of Scheduling, 2016, vol. 19, issue 6, No 4, 658 pages

Abstract: 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 holds true even when setup times occur in the execution and homogeneous buffers are available for the storage of intermediate results. In this kind of application, 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 in which the buffer sizes are not given beforehand and must be fixed before the execution to maximize the throughput within each processor. The goal of this work is to minimize the cost induced by the setup times by allocating buffers that are proportinal in size to each other. We present a closed formula to compute the optimal buffer allocation in the case of nondecreasing setup costs in the linear application. For the case of unsorted setup times, we provide competitive heuristics that are validated via extensive simulation. Three nonscalable brute force algorithms are also provided to compare heuristic approaches to optimal ones for small applications and to evaluate the relevance of our approach.

Keywords: Linear workflow; Mapping; Setup times; Buffers; Cost minimization (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-015-0437-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:19:y:2016:i:6:d:10.1007_s10951-015-0437-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-015-0437-x

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().