Multicore Scheduling of Parallel Tasks Described by Generic DAG Model with Multiple Parallelization Options

Abstract

In this paper, a method for scheduling a set of parallel tasks modeled by a generic DAG task model is discussed. A method that handles the intra-task parallelism between computational units as well as the parallelization of individual computational units in order to schedule the tasks on multiple CPU cores is presented. A density packing problem that describes our approach for handling intra-task parallelism in order to minimize the overall task minimum peak density is introduced. The density packing problem addresses each node of the DAG as a variable block of density that can take on different density values for different virtual deadlines and parallelization options. An algorithm that seeks to minimize the overall task density by setting virtual deadlines and parallelization options appropriately for each block is discussed. Furthermore, the algorithm seeks to appropriately handle the intra-task parallelism by arranging the blocks in a way to maximize the innate parallelism of the DAG task model. A Flex-density algorithm that allows nodes with further parallelization freedom to be stretched across the execution of other parallel nodes is also introduced. The results of both algorithms show promising results compared to more naive solutions that ignore the innate parallelism of DAGs and simply execute nodes in sequence.