Skip to Main content Skip to Navigation

Multi-criteria scheduling of pipeline workflows

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). In this paper, we study the complexity of the bi-criteria mapping problem for pipeline graphs on communication homogeneous platforms. In particular, we assess the complexity of the well-known chains-to-chains problem for different-speed processors, which turns out to be NP-hard. We provide several efficient polynomial bi-criteria heuristics, and their relative performance is evaluated through extensive simulations.
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Thursday, June 28, 2007 - 5:19:56 PM
Last modification on : Saturday, September 11, 2021 - 3:17:26 AM


  • HAL Id : inria-00156732, version 4
  • ARXIV : 0706.4009



Anne Benoit, Veronika Rehn-Sonigo, Yves Robert. Multi-criteria scheduling of pipeline workflows. [Research Report] RR-6232, LIP RR-2007-32, INRIA. 2007, 2+17p. ⟨inria-00156732v4⟩



Record views


Files downloads