research-article

A Logic-Based Benders Decomposition Approach for Mapping Applications on Heterogeneous Multicore Platforms

Authors:

Andreas Emeretlis,

George Theodoridis,

Panayiotis Alefragis,

Nikolaos VorosAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 15, Issue 1

Article No.: 19, Pages 1 - 28

https://doi.org/10.1145/2838733

Published: 20 February 2016 Publication History

Abstract

The development of efficient methods for mapping applications on heterogeneous multicore platforms is a key issue in the field of embedded systems. In this article, a novel approach based on the Logic-Based Benders decomposition principle is introduced for mapping complex applications on these platforms, aiming at optimizing their execution time. To provide optimal solutions for this problem in a short time, a new hybrid model that combines Integer Linear Programming (ILP) and Constraint Programming (CP) models is introduced. Also, to reduce the complexity of the model and its solution time, a set of novel techniques for generating additional constraints called Benders cuts is proposed. An extensive set of experiments has been performed in which synthetic applications described by Directed Acyclic Graphs (DAGs) were mapped to a number of heterogeneous multicore platforms. Moreover, experiments with DAGs that correspond to two real-life applications have also been performed. Based on the experimental results, it is proven that the proposed approach outperforms the pure ILP model in terms of the solution time and quality of the solution. Specifically, the proposed approach is able to find an optimal solution within a time limit of 2 hours in the vast majority of performed experiments, while the pure ILP model fails. Also, for the cases where both methods fail to find an optimal solution within the time limit, the solution of the proposed approach is systematically better than the solution of the ILP model.

References

[1]

Ishfaq Ahmad and Yu-Kwong Kwok. 1998. On exploiting task duplication in parallel program scheduling. IEEE Trans. Parallel Distrib. Syst. 9, 9 (1998), 872--892.

Digital Library

[2]

Luca Benini, Michele Lombardi, Michela Milano, and Martino Ruggiero. 2010. Optimal resource allocation and scheduling for the CELL BE platform. Ann. Oper. Res. 184, 1 (February 2010), 51--77. doi.org/10.1007/s10479-010-0718-x

[3]

Luiz F. Bittencourt, Rizos Sakellariou, and Edmundo R. M. Madeira. 2010. DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm. In Proceedings of the 2010 18th Euromicro Conf. Parallel, Distrib. Network-based Process. 27--34.

Digital Library

[4]

Hadrien Cambazard, Pierre-Emmanuel Hladik, Anne-Marie Déplanche, Narendra Jussien, and Yvon Trinquet. 2004. Decomposition and learning for a hard real time task allocation problem. In Proceedings of the 10th International Conference (CP’04). 153--167.

Digital Library

[5]

Louis-Claude Canon, Emmanuel Jeannot, Rizos Sakellariou, and Wei Zheng. 2008. Comparative evaluation of the robustness of DAG scheduling heuristics. Grid Comput. Achiev. Prospect. (2008), 73--84.

[6]

Thidapat Chantem, X. Sharon Hu, and Robert P. Dick. 2011. Temperature-aware scheduling and assignment for hard real-time applications on MPSoCs. IEEE Trans. Very Large Scale Integr. Syst. 19, 10 (2011), 1884--1897.

Digital Library

[7]

Junchul Choi, Hyunok Oh, Sungchan Kim, and Soonhoi Ha. 2012. Executing synchronous dataflow graphs on a SPM-based multicore architecture. In Proceedings of the 49th ACM/EDAC/IEEE Des. Autom. Conf. 664--971.

Digital Library

[8]

Pablo E. Coll, Celso C. Ribeiro, and Cid C. Souza. 2006. Multiprocessor scheduling under precedence constraints: Polyhedral results. Discret. Appl. Math. 154, 1 (2006), 770--801. 10.1016/j.dam.2004.07.009

Digital Library

[9]

Daniel Cordes, Michael Engel, Olaf Neugebauer, and Peter Marwedel. 2013. Automatic extraction of pipeline parallelism for embedded heterogeneous multi-core platforms. In Proceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES’13). 1--10. 10.1109/CASES.2013.6662508

Digital Library

[10]

TECS DAGs. 2015. Data sets of Directed Acyclic Graphs. (2015).

[11]

Andreas Emeretlis, George Theodoridis, Panayiotis Alefragis, and Nikolaos Voros. 2014. A hybrid ILP-CP model for mapping directed acyclic task graphs to multicore architectures. In IEEE International Parallel & Distributed Processing Symposium Workshops (IPDPSW’’14). 176--182. 10.1109/IPDPSW.2014.24

Digital Library

[12]

Fair Isaac Corporation FICO®. 2013. FICO Xpress Optimization Suite. Retrieved from http://www.fico.com/ en/products/fico-xpress-optimization-suite/.

[13]

Milind Girkar and Constantine D. Polychronopoulos. 1994. The hierarchical task graph as a universal intermediate representation. Int. J. Parallel Program. 22, 5 (1994), 519--551. BF02577777

Digital Library

[14]

Sachi Gupta, Vikas Kumar, and Gaurav Agarwal. 2010. Task scheduling in multiprocessor system using genetic algorithm. In Proceedings of the 2nd International Confence on Machine Learning and Computing. 267--271.

Digital Library

[15]

Pascal Van Hentenryck and Michela Milano. 2010. Hybrid Optimization: The Ten Years of CPAIOR. Springer.

[16]

J. N. Hooker and G. Ottosson. 2003. Logic-based benders decomposition. Math. Program. 96, 1 (2003), 33--60.

[17]

J. N. Hooker. 2007. Planning and scheduling by logic-based benders decomposition. Oper. Res. 55, 3 (2007), 588--602.

Digital Library

[18]

John N. Hooker. 2012. Integrated Methods for Optimization. Springer.

Digital Library

[19]

Jingcao Hu and Radu Marculescu. 2005. Energy- and performance-aware mapping for regular NoC architectures. IEEE Trans. Comput. Des. Integr. Circuits Syst. 24, 4 (2005), 551--562. 10.1109/TCAD.2005.844106

Digital Library

[20]

Olivera Jovanovic, Nils Kneuper, Michael Engel, and Peter Marwedel. 2012. ILP-based memory-aware mapping optimization for MPSoCs. In 15th IEEE International Conference on Computational Science and Engineering (CSE’12). 413--420.

Digital Library

[21]

Krzysztof Kuchcinski. 2003. Constraints-driven scheduling and resource assignment. ACM Trans. Des. Autom. Electron. Syst. 8, 3 (July 2003), 355--383.

Digital Library

[22]

David G. Lowe. 2004. Distinctive image features from scale-invariant keypoints. Int. J. Comput. Vis. 60, 2 (2004), 91--110.

Digital Library

[23]

Christos T. Maravelias. 2006. A decomposition framework for the scheduling of single- and multi-stage processes. Comput. Chem. Eng. 30, 3 (2006), 407--420. 2005.09.011

[24]

Kevin Martin, Christophe Wolinski, Krzysztof Kuchcinski, Antoine Floch, and François Charot. 2012. Constraint programming approach to reconfigurable processor extension generation and application compilation. ACM Trans. Reconfigurable Technol. Syst. 5, 2 (June 2012), 1--38. 2209285.2209289

Digital Library

[25]

George L. Nemhauser and Laurence A. Wolsey. 1999. Integer and Combinatorial Optimization. John Wiley & Sons.

Digital Library

[26]

Samantha Ranaweera and Dharma P. Agrawal. 2000. A task duplication based scheduling algorithm for heterogeneous systems. In Proc. 14th Int. Parallel Distrib. Process. Symp (IPDPS’00). 445--450.

Digital Library

[27]

Francesca Rossi, Peter Van Beek, and Toby Walsh. 2006. Handbook of Constraint Programming. Elsevier Science.

Digital Library

[28]

Martino Ruggiero, Alessio Guerri, Davide Bertozzi, Michela Milano, and Luca Benini. 2007. A fast and accurate technique for mapping parallel applications on stream-oriented MPSoC platforms with communication awareness. Int. J. Parallel Program. 36, 1 (April 2007), 3--36.

Digital Library

[29]

Ruslan Sadykov and Laurence A. Wolsey. 2006. Integer programming and constraint programming in solving a multimachine assignment scheduling problem with deadlines and release dates. INFORMS J. Comput. 18, 2 (2006), 209--217.

Digital Library

[30]

O. L. Sathappan, P. Chitra, P. Venkatesh, and M. Prabhu. 2011. Modified genetic algorithm for multiobjective task scheduling on heterogeneous computing system. Int. J. Inf. Technol. Commun. Converg. 1, 2 (2011), 146--158.

[31]

Nadathur Satish, Kaushik Ravindran, and Kurt Keutzer. 2007. A decomposition-based constraint optimization approach for statically scheduling task graphs with communication delays to multiprocessors. In Proceedings of the 2007 Design Automation Test Europe Conference Exhibit. 1--6.

Digital Library

[32]

Amit Kumar Singh, Muhammad Shafique, Akash Kumar, and Jörg Henkel. 2013. Mapping on multi many core systems: Survey of current and emerging trends. In 50th ACM/EDAC/IEEE Des. Autom. Conf. (DAC’ 13). 1--10.

Digital Library

[33]

Oliver Sinnen. 2007. Task Scheduling for Parallel Systems. John Wiley & Sons.

Digital Library

[34]

Timo Stripf, Oliver Oey, Thomas Bruckschloegl, Juergen Becker, Gerard Rauwerda, Kim Sunesen, George Goulas, Panayiotis Alefragis, Nikolaos S. Voros, Steven Derrien, Olivier Sentieys, Nikolaos Kavvadias, Grigoris Dimitroulakos, Kostas Masselos, Dimitrios Kritharidis, Nikolaos Mitas, and Thomas Perschke. 2013. Compiling Scilab to high performance embedded multicore systems. Microprocess. Microsyst. 37, 8 (2013), 1033--1049.

Digital Library

[35]

Timo Stripf, Ralf Koenig, and Juergen Becker. 2012. A cycle-approximate, mixed-ISA simulator for the KAHRISMA architecture. In Proceedings of the 2012 Design, Automation & Test in Europe Conference & Exhibition (DATE’& Exhibition (DATE’’12). 21--26.

Digital Library

[36]

George Theodoridis, Nikolaos Vassiliadis, and Spyridon Nikolaidis. 2009. An integer linear programming model for mapping applications on hybrid systems. IET Comput. Digit. Tech. 3, 1 (2009), 33--42.

[37]

Lothar Thiele, Iuliana Bacivarov, Wolfgang Haid, and Kai Huang. 2007. Mapping applications to tiled multiprocessor embedded systems. In Proceedings of the 7th International Conference on Application of Concurrency to System Design (ACSD’07). 29--40.

Digital Library

[38]

Haluk Topcuoglu, Salim Hariri, and Min-You Wu. 2002. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst. 1, 3 (2002), 260--274.

Digital Library

Cited By

Chen HQin WWang L(2022)Task partitioning and offloading in IoT cloud-edge collaborative computing framework: a surveyJournal of Cloud Computing10.1186/s13677-022-00365-811:1Online publication date: 3-Dec-2022
https://doi.org/10.1186/s13677-022-00365-8
Emeretlis ATheodoridis GAlefragis PVoros N(2022)A Multi-stage Hybrid Approach for Mapping Applications on Heterogeneous Multi-core Platforms2022 IFIP/IEEE 30th International Conference on Very Large Scale Integration (VLSI-SoC)10.1109/VLSI-SoC54400.2022.9939643(1-6)Online publication date: 3-Oct-2022
https://doi.org/10.1109/VLSI-SoC54400.2022.9939643
Karlsson ERönnberg E(2022)Logic-based Benders decomposition with a partial assignment acceleration technique for avionics schedulingComputers and Operations Research10.1016/j.cor.2022.105916146:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.cor.2022.105916
Show More Cited By

Index Terms

A Logic-Based Benders Decomposition Approach for Mapping Applications on Heterogeneous Multicore Platforms

Recommendations

Static Mapping of Applications on Heterogeneous Multi-Core Platforms Combining Logic-Based Benders Decomposition with Integer Linear Programming

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) ...
Planning and Scheduling by Logic-Based Benders Decomposition

We combine mixed-integer linear programming (MILP) and constraint programming (CP) to solve an important class of planning and scheduling problems. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-...
Benders decomposition with integer subproblem

A Branch-and-Cut algorithm using Benders decomposition method is proposed.The algorithm is applied in case of integer subproblem.Local and Global Cuts are used to warm start the master problem in each node.The validity of the cuts is mathematically ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 15, Issue 1

February 2016

530 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/2872313

Editor:
Sandeep K. Shukla
Indian Institute of Technology, India

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 20 February 2016

Accepted: 01 October 2015

Revised: 01 August 2015

Received: 01 March 2015

Published in TECS Volume 15, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Seventh Framework Programme

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
244
Total Downloads

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

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen HQin WWang L(2022)Task partitioning and offloading in IoT cloud-edge collaborative computing framework: a surveyJournal of Cloud Computing10.1186/s13677-022-00365-811:1Online publication date: 3-Dec-2022
https://doi.org/10.1186/s13677-022-00365-8
Emeretlis ATheodoridis GAlefragis PVoros N(2022)A Multi-stage Hybrid Approach for Mapping Applications on Heterogeneous Multi-core Platforms2022 IFIP/IEEE 30th International Conference on Very Large Scale Integration (VLSI-SoC)10.1109/VLSI-SoC54400.2022.9939643(1-6)Online publication date: 3-Oct-2022
https://doi.org/10.1109/VLSI-SoC54400.2022.9939643
Karlsson ERönnberg E(2022)Logic-based Benders decomposition with a partial assignment acceleration technique for avionics schedulingComputers and Operations Research10.1016/j.cor.2022.105916146:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.cor.2022.105916
Mo LKritikakou ASentieys OCao X(2021)Real-Time Imprecise Computation Tasks Mapping for DVFS-Enabled Networked SystemsIEEE Internet of Things Journal10.1109/JIOT.2020.30449108:10(8246-8258)Online publication date: 15-May-2021
https://doi.org/10.1109/JIOT.2020.3044910
Richthammer VFassnacht FGlaß M(2020)Search-space Decomposition for System-level Design Space Exploration of Embedded SystemsACM Transactions on Design Automation of Electronic Systems10.1145/336938825:2(1-32)Online publication date: 10-Jan-2020
https://dl.acm.org/doi/10.1145/3369388
Mo LKritikakou A(2019)Mapping imprecise computation tasks on cyber-physical systemsPeer-to-Peer Networking and Applications10.1007/s12083-019-00749-9Online publication date: 8-Apr-2019
https://doi.org/10.1007/s12083-019-00749-9
Richthammer VSchwarzer TWildermann STeich JGlaß M(2018)Architecture decomposition in system synthesis of heterogeneous many-core systemsProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3195995(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3195995
Mo LKritikakou ASentieys O(2018)Controllable QoS for Imprecise Computation Tasks on DVFS Multicores With Time and Energy ConstraintsIEEE Journal on Emerging and Selected Topics in Circuits and Systems10.1109/JETCAS.2018.28520058:4(708-721)Online publication date: Dec-2018
https://doi.org/10.1109/JETCAS.2018.2852005
Richthammer VSchwarzer TWildermann STeich JGlas M(2018)Architecture Decomposition in System Synthesis of Heterogeneous Many-Core Systems2018 55th ACM/ESDA/IEEE Design Automation Conference (DAC)10.1109/DAC.2018.8465811(1-6)Online publication date: Jun-2018
https://doi.org/10.1109/DAC.2018.8465811
Alefragis PTheodoridis GKatsimpris MValouxis CGogos CGoulas GVoros NReder SKasnakli KBednara MMüller DDurak UBecker J(2018)Mapping and Scheduling Hard Real Time Applications on Multicore Systems - The ARGO ApproachApplied Reconfigurable Computing. Architectures, Tools, and Applications10.1007/978-3-319-78890-6_56(700-711)Online publication date: 8-Apr-2018
https://doi.org/10.1007/978-3-319-78890-6_56
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents