A Constraint Programming Approach to Scheduling of Malleable Tasks

Abstract

With the increasing demand for high-performance computing, multicore architectures became appealing in various application domains. In order to exploit the parallelism of the multicore architectures, task scheduling has become more important than ever. Classical multicore task scheduling assumes that each task is executed on one of the cores. However, many tasks in modern applications have inherent parallelism and can be multi-threaded. A task is partitioned into threads which can be executed on multiple cores in a fork-join fashion. A multi-threaded task is called malleable if the number of threads is flexible and is determined at the same time as task scheduling.

This paper proposes multicore scheduling methods for malleable tasks. Given a set of dependent tasks in the form of directed acyclic graph and homogeneous multiple cores, the proposed methods decide the number of threads for each task and schedule the threads on the multicores simultaneously, with the goal of minimizing the overall schedule length. The proposed scheduling methods are based on constraint programming. Experimental results show that the proposed methods outperform state-of-the-art work which is based on integer linear programming.