Improvements of a hybrid ILP-CP Benders decomposition for mapping and scheduling task DAGs on heterogeneous architectures

25 Aug

Andreas Emeretlis George Theodoridis, Panayiotis Alefragis, Nikolaos Voros, Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling, PATAT 2016, 23-26 August 2016, Udine, Italy 2016, pp 477-479, ISBN: 978-0-9929984-1-7

Presented by Panayiotis Alefragis.

Abstract: A hybrid approach for mapping applications
represented as Directed Acyclic Graphs (DAGs) that integrates Integer Linear and Constraint Programming is extended to introduce extra constraints in the Master Problem of Benders decomposition. The constraints are trying to reflect the impact of the sequencing of the direct predecessors and successors of every node of the DAG. A set of relaxed constraints are introduced in the model and comparative results on the performance and quality of the approach are presented. The results show that the introduction of the constraint reduce by 50% the execution time compared to previous approaches managing to be 9 times faster than the pure ILP approach.

Leave a Reply