|
 
|
[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.
BibTeX
| @article { | |||
| KMM18, | |||
| 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", | |
| year | = | 2018, | |
| volume | = | 29, | |
| number | = | 1, | |
| pages | = | "63-90", | |
| doi | = | "/10.1142/S012905411850003X", | |
| } | |||
