Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Anne Benoit Connect in order to contact the contributor
Submitted on : Tuesday, June 19, 2012 - 9:41:22 AM
Last modification on : Wednesday, October 26, 2022 - 8:16:01 AM
Long-term archiving on: : Thursday, December 15, 2016 - 4:04:49 PM


Files produced by the author(s)


  • HAL Id : hal-00674057, version 2


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⟩



Record views


Files downloads