On the Complexity of Mapping Linear Chain Applications onto Heterogeneous Platforms - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 2008

On the Complexity of Mapping Linear Chain Applications onto Heterogeneous Platforms

Résumé

In this paper, we explore the problem of mapping simple application patterns onto large-scale heterogeneous platforms. An important optimization criteria that should be considered in such a framework is the latency, or makespan, which measures the response time of the system in orderto process one single data set entirely. We focus in this work on linear chain applications, which are representative of a broad class of real-life applications. For such applications, we can considerone-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 ontothe 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 beapproximated by any constant factor (unless P=NP).
Fichier principal
Vignette du fichier
LIP-RR_2008-32.pdf (200.54 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102806 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102806 , version 1

Citer

Anne Benoit, Yves Robert, Eric Thierry. On the Complexity of Mapping Linear Chain Applications onto Heterogeneous Platforms. [Research Report] LIP RR-2008-32, Laboratoire de l'informatique du parallélisme. 2008, 12p. ⟨hal-02102806⟩
62 Consultations
133 Téléchargements

Partager

More