Skip to Main content Skip to Navigation

Scheduling on Two Unbounded Resources with Communication Costs

Abstract : Heterogeneous computing systems became a popular and powerful platform, containing several heterogeneous computing elements (e.g. CPU+GPU). In this paper, we consider that we have two platforms, each with an unbounded number of processors. We want to execute an application represented as a Directed acyclic Graph (DAG) using these two platforms. Each task of the application has two possible execution times, depending on the platform it is executed on. Also, there is a cost to transfer data from one platform to another between successive tasks. The goal here is to minimize the finish execution time of the last task of the application (usually called makespan). We show that the problem is NP-complete for graphs of depth at least 3 but polynomial for graphs of depth at most 2. Finally, we focus on particular classes of graphs, by providing polynomial-time algorithms for bi-partite graphs, trees and 2-series-parallel graphs with different assumptions on communication delays.
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download
Contributor : Guillaume Pallez (aupy) Connect in order to contact the contributor
Submitted on : Friday, March 22, 2019 - 10:31:23 AM
Last modification on : Friday, January 21, 2022 - 3:12:50 AM
Long-term archiving on: : Sunday, June 23, 2019 - 1:36:05 PM


Files produced by the author(s)


  • HAL Id : hal-02076473, version 1


Massinissa Ait Aba, Guillaume Aupy, Alix Munier-Kordon. Scheduling on Two Unbounded Resources with Communication Costs. [Research Report] RR-9264, Inria. 2019. ⟨hal-02076473⟩



Les métriques sont temporairement indisponibles