Scheduling Algorithms for Parallel Real-Time Tasks with Multiple Parallelization Options on Multicore/GPGPU System

Abstract

Past researches on multicore/GPGPU scheduling assume that a computational unit has a pre-fixed number of CPU and GPU threads. However, with recent technologies such as OpenCL, a computational unit can be parallelized in many different ways with runtime selectable numbers of CPU and GPU threads. This paper proposes algorithms for optimally parallelizing and scheduling a set of parallel tasks with multiple parallelization options on multiple CPU cores and multiple GPU devices. Our experimental study says that the proposed algorithms can successfully schedule up to two times more tasks compared with other algorithms assuming pre-fixed parallelization. To the best of our knowledge, this is the first work addressing the problem of scheduling parallel tasks with multiple parallelization options on multiple heterogeneous resources.