2007/06/27 by Anne Benoît, Anne Benoit, Veronika Rehn‐Sonigo +5 · 1 citation
Computer Science · #Distributed #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Interconnection Networks and Systems #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.0706.4009
openalex publication_date 2007/06/27 · arxiv created 2007/06/28 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.