On the complexity of mapping linear chain applications onto heterogeneous platforms

Anne Benoit 1, 2 Eric Thierry 1 Yves Robert 1, 2
2 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this paper, we explore the problem of mapping linear chain applications onto large-scale heterogeneous platforms. A series of data sets enter the input stage and progress from stage to stage until the final result is computed. An important optimization criterion that should be considered in such a framework is the latency, or makespan, which measures the response time of the system in order to process one single data set entirely. For such applications, which are representative of a broad class of real-life applications, we can consider one-to-one mappings, in which each stage is mapped onto a single processor. However, in order to reduce the communication cost, it seems natural to group stages into intervals. The interval mapping problem can be solved in a straightforward way if the platform has homogeneous communications: the whole chain is grouped into a single interval, which in turn is mapped onto the fastest processor. But the problem becomes harder when considering a fully heterogeneous platform. Indeed, we prove the NP-completeness of this problem. Furthermore, we prove that neither the interval mapping problem nor the similar one-to-one mapping problem can be approximated in polynomial time by any constant factor (unless P=NP).
Type de document :
Article dans une revue
Parallel Processing Letters, World Scientific Publishing, 2009, 19 (3), pp.383-397. 〈10.1142/S0129626409000298〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00786381
Contributeur : Equipe Roma <>
Soumis le : vendredi 8 février 2013 - 14:54:18
Dernière modification le : vendredi 20 avril 2018 - 15:44:24

Lien texte intégral

Identifiants

Collections

Citation

Anne Benoit, Eric Thierry, Yves Robert. On the complexity of mapping linear chain applications onto heterogeneous platforms. Parallel Processing Letters, World Scientific Publishing, 2009, 19 (3), pp.383-397. 〈10.1142/S0129626409000298〉. 〈hal-00786381〉

Partager

Métriques

Consultations de la notice

108