Approximation algorithm for scheduling applications on hybrid multi-core machines with communications delays
| Autor: | Alix Munier, Massinissa Ait Aba, Lilia Zaourar |
|---|---|
| Přispěvatelé: | Département d'Architectures, Conception et Logiciels Embarqués-LIST (DACLE-LIST), Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Architecture et Logiciels pour Systèmes Embarqués sur Puce (ALSOC), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
020203 distributed computing
Multi-core processor Job shop scheduling Computer science Processor scheduling Approximation algorithm makespan DAG applications 02 engineering and technology Parallel computing Directed acyclic graph hybrid CPU GPU Scheduling (computing) 0202 electrical engineering electronic engineering information engineering Task analysis 020201 artificial intelligence & image processing [INFO]Computer Science [cs] scheduling Computer Science::Operating Systems approximation algorithm |
| Zdroj: | 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) IPDPS Workshops 2018, 2018 IEEE International Parallel and Distributed Processing Symposium Workshops IPDPS Workshops 2018, 2018 IEEE International Parallel and Distributed Processing Symposium Workshops, May 2018, Vancouver, Canada. pp.36-45, ⟨10.1109/IPDPSW.2018.00016⟩ IPDPS Workshops |
| DOI: | 10.1109/IPDPSW.2018.00016⟩ |
| Popis: | International audience; This paper presents an efficient algorithm with performance guarantee (approximation algorithm) to solve task scheduling problem on hybrid platform. The underlying platform architecture in this work is composed by two types of resources CPU and GPU, often called hybrid parallel multi-core platforms. We consider here for each type of resource identical nodes with communications delays. We focus in finding a generic approach to schedule applications presented by DAG (Directed Acyclic Graph) that minimizes makespan by considering communication delay between processors and tasks. A 6-approximation scheduling algorithm is proposed and evaluated in comparison to exact solutions and to another method. We demonstrate that the proposed algorithm achieves a close-to-optimal performance. Finally, our algorithm has been experimented on a large number of instances. These tests assess the good practical behavior of the algorithms with respect to the state-of-the-art solutions whenever these exist. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|