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 metadatas

https://hal.inria.fr/inria-00156732
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, June 27, 2007 - 3:42:50 PM
Last modification on : Friday, April 20, 2018 - 3:44:24 PM
Long-term archiving on: Tuesday, September 21, 2010 - 1:14:01 PM

Files

RR2007-32.inria.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

Anne Benoit, Veronika Rehn-Sonigo, Yves Robert. Multi-criteria scheduling of pipeline workflows. [Research Report] RR-6232, 2007. ⟨inria-00156732v2⟩

Share

Metrics

Record views

4

Files downloads

4