Skip to Main content Skip to Navigation
Reports

Throughput optimization for pipeline workflow scheduling with setup times

Abstract : In this paper, we tackle pipeline workflow applications that are executed on a dis- tributed heterogeneous platform with setup times. In such applications, several computation stages are interconnected as a linear application graph. The considered stage/processor mapping strategy is based on interval mappings, where an interval of consecutive stages is performed by the same processor. Each stage holds a buffer of limited size where intermediate results are stored and a setup time occurs when passing from one stage to another. Typical examples for this kind of applications are streaming applications such as audio and video coding or decoding, image pro- cessing using co-processing devices as FPGA. In this paper, we focus on throughput optimization. This problem is known to be NP-hard as soon as heterogeneous processors are used, even without setup times and with homogeneous communication links. We provide an optimal algorithm for the inner-processor scheduling of stages on homogeneous platforms with identical buffer capacities. We also provide an interval mapping that, when running the former algorithm including all processors, maximizes the throughput of the application. Last, we deal with the problem of allocating the buffers for each stage in shared memory. We provide an optimal algorithm for buffer allocation in the case where the memory may be split evenly, and we propose heuristics to handle any remainder in the memory allocation.
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-00674057
Contributor : Anne Benoit <>
Submitted on : Tuesday, June 19, 2012 - 9:41:22 AM
Last modification on : Wednesday, September 16, 2020 - 10:42:19 AM
Long-term archiving on: : Thursday, December 15, 2016 - 4:04:49 PM

File

RR-7886.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00674057, version 2

Citation

Anne Benoit, Mathias Coqblin, Jean-Marc Nicod, Laurent Philippe, Veronika Rehn-Sonigo. Throughput optimization for pipeline workflow scheduling with setup times. [Research Report] RR-7886, INRIA. 2012, pp.29. ⟨hal-00674057v2⟩

Share

Metrics

Record views

836

Files downloads

385