25 Aug

Panayiotis Alefragis presented the paper ”Improvements of a hybrid ILP-CP Benders decomposition for mapping and scheduling task DAGs on heterogeneous architectures” in the frame of the 11th International Conference of the Practice and Theory of Automated Timetabling (PATAT), hosted on the 23-26th August 2016, in Udine, Italy.

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