Generic algorithms for scheduling applications on hybrid multi-core machines

Abstract : We study the problem of executing an application represented by a precedence task graph on a multi-core machine composed of standard computing cores and accelerators. Contrary to most existing approaches, we distinguish the allocation and the scheduling phases and we mainly focus on the allocation part of the problem: choose the more appropriate type of computing unit for each task. We address both off-line and on-line settings. In the first case, we establish strong lower bounds on the worst-case performance of a known approach based on Linear Programming for solving the allocation problem. Then, we refine the scheduling phase and we replace the greedy list scheduling policy used in this approach by a better ordering of the tasks. Although this modification leads to the same approximability guarantees, it performs much better in practice. We also extend this algorithm to more types of heterogeneous cores, achieving an approximation ratio which depends on the number of different types. In the on-line case, we assume that the tasks arrive in any, not known in advance, order which respects the precedence relations and the scheduler has to take irrevocable decisions about their allocation and execution. In this setting, we propose the first scheduling algorithm with precedences based on adequate rules for selecting the type of processor where to allocate the tasks. This algorithm achieves a constant factor approximation guarantee if the ratio of the number of CPUs over the number of GPUs is bounded. Finally, all the previous algorithms have been experimented on a large number of simulations built upon actual libraries. These simulations assess the good practical behavior of the algorithms with respect to the state-of-the-art solutions whenever these exist or baseline algorithms.
Type de document :
Communication dans un congrès
23rd International European Conference on Parallel and Distributed Computing (EuroPar 2017), Aug 2017, Santiago de Compostela, Spain. Lecture Notes in Computer Science
Liste complète des métadonnées


https://hal.inria.fr/hal-01420798
Contributeur : Clement Mommessin <>
Soumis le : mercredi 21 décembre 2016 - 09:28:45
Dernière modification le : jeudi 15 juin 2017 - 09:09:27
Document(s) archivé(s) le : mardi 21 mars 2017 - 00:55:04

Fichier

Generic algorithms for schedul...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01420798, version 1

Collections

Citation

Marcos Amaris, Giorgio Lucarelli, Clément Mommessin, Denis Trystram. Generic algorithms for scheduling applications on hybrid multi-core machines. 23rd International European Conference on Parallel and Distributed Computing (EuroPar 2017), Aug 2017, Santiago de Compostela, Spain. Lecture Notes in Computer Science. <hal-01420798>

Partager

Métriques

Consultations de
la notice

375

Téléchargements du document

63