A hybrid approach for mapping and scheduling on heterogeneous multicore systems

A hybrid approach for mapping applications represented as Directed Acyclic Graphs (DAGs) is introduced in this work. It combines the Benders decomposition principle, which integrates Integer Linear and Constraint Programming (ILP and CP) methods, with a pure ILP model to find optimal solutions. The cuts that are generated during the iterative Benders solution process are later exploited by the ILP solver to prune the remaining search space. The proposed model succeeds to provide the optimal solution in cases where either method alone fails to do so, while it also reduces the total solution time.

I. Introduction

The proper mapping of an application on a multicore platform and the scheduling of its tasks is a key element in order to achieve the maximum possible performance. In its general form, this is a well-known NP-complete problem. Especially when the platform consists of heterogeneous cores, as many modern platforms do, the complexity of the problem increases since the execution time of each task is not the same when it is mapped on different cores.