Skip to Main content Skip to Navigation

On the Complexity of Mapping Linear Chain Applications onto Heterogeneous Platforms

Abstract : 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).
Document type :
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 4:26:40 PM
Last modification on : Wednesday, February 26, 2020 - 11:14:31 AM


Files produced by the author(s)


  • HAL Id : hal-02102806, version 1



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⟩



Record views


Files downloads