Skip to Main content Skip to Navigation
Journal articles

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).
Document type :
Journal articles
Complete list of metadatas
Contributor : Equipe Roma <>
Submitted on : Friday, February 8, 2013 - 2:54:18 PM
Last modification on : Wednesday, February 26, 2020 - 11:14:02 AM

Links full text




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⟩



Record views