Task graph mapping and scheduling on heterogeneous architectures under communication constraints

An approach for mapping applications represented as Directed Acyclic Graphs (DAGs) on platforms consisting of heterogeneous cores considering the communication overhead between the cores is introduced. The approach is based on the Benders decomposition principle and integrates Integer Linear and Constraint Programming formulations. Both formulations take into account the communication delay between dependent tasks that are assigned to different cores trying to optimize the application's execution time. The proposed approach succeeds to provide the optimal solution in all cases of synthetic and real-application DAGs, while the pure ILP model fails more than half of them. Also, the average solution time of the proposed method is about 1 minute, whereas for instances solved by both models, the speedup equals to 11× over the ILP model.