A Multi-stage Hybrid Approach for Mapping Applications on Heterogeneous Multi-core Platforms

Due to the incorporation of heterogeneous cores in modern multi-core systems, the exploitation of their full potential strongly depends on the proper mapping of an application to the platform. This work presents an approach to map static applications on heterogeneous platforms minimizing their makespan based on the Benders decomposition principle combined with an Integer Linear Programming (ILP) model. The proposed approach adopts a three-stage decomposition scheme, finding permutations of infeasible solutions to generate multiple cuts in every iteration. The first stage deals with the assignment of the tasks to the cores and the last one with their scheduling, whereas the second stage propagates new bounds based on the current assignment and provides an explanation of the infeasibility in the form of subsets of assignment variables. Based on that, other infeasible combinations are computed by checking their permutations and more Benders cuts are produced. The proposed method is compared with a two-stage decomposition approach and an ILP model and exhibits better performance in terms of solution time and number solved instances to optimality.