Article

A Hybrid ILP-CP Model for Mapping Directed Acyclic Task Graphs to Multicore Architectures

Authors:

Andreas Emeretlis,

George Theodoridis,

Panayiotis Alefragis,

Nikolaos VorosAuthors Info & Claims

IPDPSW '14: Proceedings of the 2014 IEEE International Parallel & Distributed Processing Symposium Workshops

Pages 176 - 182

https://doi.org/10.1109/IPDPSW.2014.24

Published: 19 May 2014 Publication History

Abstract

Directed Acyclic Task Graphs serve as typical kernel representation for embedded applications. Modern embedded multicore architectures raise new challenges for efficient mapping and scheduling of task DAGs providing a large number of heterogeneous resources. In this paper, a hybrid Integer Linear Programming – Constraint Programming method that uses the Benders decomposition is used to find proven optimal solutions. The proposed method is augmented with cuts generation schemes for accelerating the solution process. Experimental results show that the proposed method systematically outperforms an ILP-based solution method.

Cited By

View all

Zhang JHan Z(2024)Optimization of uncertain dependent task mapping on heterogeneous computing platformsThe Journal of Supercomputing10.1007/s11227-024-06032-w80:11(15868-15893)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11227-024-06032-w
Kelefouras VDjemame K(2022)Workflow simulation and multi-threading aware task scheduling for heterogeneous computingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.05.011168:C(17-32)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.jpdc.2022.05.011
Alefragis PSofos CVlachos VSavvas ISgouropoulou CPlagianakos VDouligeris CVoyiatzis ITampakas VSoultis G(2017)Automated parameter selection of scheduling algorithms using machine learning techniquesProceedings of the 21st Pan-Hellenic Conference on Informatics10.1145/3139367.3139442(1-5)Online publication date: 28-Sep-2017
https://dl.acm.org/doi/10.1145/3139367.3139442
Show More Cited By

A Hybrid ILP-CP Model for Mapping Directed Acyclic Task Graphs to Multicore Architectures
1. Mathematics of computing
  1. Discrete mathematics

Recommendations

Implementing directed acyclic graphs with the heterogeneous system architecture
GPGPU '16: Proceedings of the 9th Annual Workshop on General Purpose Processing using Graphics Processing Unit

Achieving optimal performance on heterogeneous computing systems requires a programming model that supports the execution of asynchronous, multi-stream, and out-of-order tasks in a shared memory environment. Asynchronous dependency-driven tasking is one ...
Directed acyclic graphs with the unique dipath property

Let P be a family of dipaths of a DAG (Directed Acyclic Graph) G. The load of an arc is the number of dipaths containing this arc. Let @p(G,P) be the maximum of the load of all the arcs and let w(G,P) be the minimum number of wavelengths (colors) needed ...
The nucleolus of arborescence games in directed acyclic graphs

In this paper, we consider the problem of finding the nucleolus of arborescence games. We prove that the nucleolus of arborescence games in directed acyclic graphs can be found in linear time.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

IPDPSW '14: Proceedings of the 2014 IEEE International Parallel & Distributed Processing Symposium Workshops

May 2014

1737 pages

ISBN:9781479941162

Publisher

IEEE Computer Society

United States

Publication History

Published: 19 May 2014

Author Tag

multicore architectures, DAG mapping, tasks scheduling, integer linear programming, constraint programming

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang JHan Z(2024)Optimization of uncertain dependent task mapping on heterogeneous computing platformsThe Journal of Supercomputing10.1007/s11227-024-06032-w80:11(15868-15893)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11227-024-06032-w
Kelefouras VDjemame K(2022)Workflow simulation and multi-threading aware task scheduling for heterogeneous computingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.05.011168:C(17-32)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.jpdc.2022.05.011
Alefragis PSofos CVlachos VSavvas ISgouropoulou CPlagianakos VDouligeris CVoyiatzis ITampakas VSoultis G(2017)Automated parameter selection of scheduling algorithms using machine learning techniquesProceedings of the 21st Pan-Hellenic Conference on Informatics10.1145/3139367.3139442(1-5)Online publication date: 28-Sep-2017
https://dl.acm.org/doi/10.1145/3139367.3139442
Emeretlis ATheodoridis GAlefragis PVoros N(2016)A Logic-Based Benders Decomposition Approach for Mapping Applications on Heterogeneous Multicore PlatformsACM Transactions on Embedded Computing Systems10.1145/283873315:1(1-28)Online publication date: 20-Feb-2016
https://dl.acm.org/doi/10.1145/2838733

Abstract

Cited By

Recommendations

Implementing directed acyclic graphs with the heterogeneous system architecture

Directed acyclic graphs with the unique dipath property

The nucleolus of arborescence games in directed acyclic graphs

Comments

Information

Published In

Publisher

Publication History

Author Tag

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations