Paper Info
Title
Static Mapping of Applications on Heterogeneous Multi-Core Platforms Combining Logic-Based Benders Decomposition with Integer Linear Programming.
Abstract
The proper mapping of an application on a multi-core platform and the scheduling of its tasks are key elements to achieve the maximum performance. In this article, a novel hybrid approach based on integrating the Logic-Based Benders Decomposition (LBBD) principle with a pure Integer Linear Programming (ILP) model is introduced for mapping applications described by Directed Acyclic Graphs (DAGs) on platforms consisting of heterogeneous cores. The LBBD approach combines two optimization techniques with complementary strengths, namely ILP and Constraint Programming (CP), and is employed as a cut generation scheme. The generated constraints are utilized by the ILP model to cut possible assignment combinations aiming at improving the solution or proving the optimality of the best-found one. The introduced approach was applied both on synthetic DAGs and on DAGs derived from real applications. Through the proposed approach, many problems were optimally solved that could not be solved by any of the above methods (ILP, LBBD) alone within a time limit of 2 hours, while the overall solution time was also significantly decreased. Specifically, the hybrid method exhibited speedups equal to 4.2× for the synthetic instances and 10× for the real-application DAGs over the LBBD approach and two orders of magnitude over the ILP model.
Year
DOI
Venue
2018
10.1145/3133219
ACM Trans. Design Autom. Electr. Syst.
Keywords
Field
DocType
Benders decomposition, Task scheduling, constraint programming, integer linear programming, multi-core embedded platforms
Static mapping,Scheduling (computing),Computer science,Parallel computing,Constraint programming,Directed acyclic graph,Integer programming,Order of magnitude,Multi-core processor,Benders' decomposition
Journal
Volume
Issue
ISSN
23
2
1084-4309
Citations 
PageRank 
References 
1
0.36
26
Authors
4
Name
Order
Citations
PageRank
Andreas Emeretlis1112.95
George Theodoridis2101.91
Panayiotis Alefragis312014.33
Nikos S. Voros4255.31