[KMM18] A Family of Scheduling Algorithms for Hybrid Parallel Platforms

Revue Internationale avec comité de lecture : Journal International Journal of Foundations of Computer Science, vol. 29(1), pp. 63-90, 2018, (doi:/10.1142/S012905411850003X)

Mots clés: Scheduling, approximation algorithms, parallel heterogeneous systems

Résumé: More and more parallel computing platforms are built upon hybrid architectures combining multi-core processors (CPUs) and hardware accelerators like General Purpose Graphics Processing Units (GPGPUs). We present in this paper a new method for scheduling efficiently parallel applications with m CPUs and k GPGPUs, where each task of the application can be processed either on an usual core (CPU) or on a GPGPU. We consider the problem of scheduling n independent tasks with the objective to minimize the time for completing the whole application (makespan). This problem is NP-hard, thus, we present two families of approximation algorithms that can achieve approximation ratios of 2q+12q+𝜖 or 2(q+1)2q+1+𝜖 for any integer q≥1 when only one GPGPU is considered, and 2q+12q+12qk+𝜖 or 2(q+1)2q+1+1(2q+1)k+𝜖 for k≥2 GPGPUs, where 𝜖 is an arbitrary small value which corresponds to the target accuracy of a binary search. The proposed method is based on a dual approximation scheme that uses a dynamic programming algorithm. The associated computational costs are for the first (resp. second) family in 𝒪(n2kq+1mq) (resp. 𝒪(n2kq+2mq+1)) per step of dual approximation. The greater the value of parameter q, the better the approximation, but the more expensive the computational cost. Finally, we propose a relaxed version of the algorithm which achieves a running time in 𝒪(nlogn) with a constant approximation bound of 2. This last result is compared to the state-of-the-art algorithm HEFT. The proposed solving method is the first general purpose algorithm for scheduling on hybrid machines with a theoretical performance guarantee that can be used for practical purposes.


@article {
title="{A Family of Scheduling Algorithms for Hybrid Parallel Platforms}",
author="S. Kedad-Sidhoum and F. Monna and G. Mounié and D. Trystram",
journal="International Journal of Foundations of Computer Science",