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 : mardi 16 janvier 2018 - 15:59:28

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

86