Multi-criteria scheduling of pipeline workflows (and application to the JPEG encoder)

Abstract : Mapping workflow applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline graphs. Several antagonist criteria should be optimized, such as throughput and latency (or a combination). A typical application class is digital image coding, where images are processed in steady-state mode. In this paper, we study the general bi-criteria mapping problem (minimizing period and latency) for pipeline graphs on communication homogeneous platforms. We present an integer linear programming formulation for this NP-hard problem. Furthermore, we provide several efficient polynomial bi-criteria heuristics, whose relative performance is evaluated through extensive simulations. As a case study, we provide simulations and MPI experimental results for the JPEG encoder application pipeline on a cluster of workstations.
Complete list of metadatas

https://hal.inria.fr/hal-00980694
Contributor : Equipe Roma <>
Submitted on : Friday, April 18, 2014 - 3:53:45 PM
Last modification on : Friday, April 20, 2018 - 3:44:24 PM

Links full text

Identifiers

Collections

Citation

Anne Benoit, Harald Kosch, Veronika Rehn-Sonigo, Yves Robert. Multi-criteria scheduling of pipeline workflows (and application to the JPEG encoder). International Journal of High Performance Computing Applications, SAGE Publications, 2009, 23 (2), pp.171-187. ⟨10.1177/1094342009104009⟩. ⟨hal-00980694⟩

Share

Metrics

Record views

183