research-article

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

Authors:

Andreas Emeretlis,

George Theodoridis,

Panayiotis Alefragis,

Nikolaos VorosAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 23, Issue 2

Article No.: 26, Pages 1 - 24

https://doi.org/10.1145/3133219

Published: 21 December 2017 Publication History

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.

References

[1]

Mehdi Akbari and Hassan Rashidi. 2016. A multi-objectives scheduling algorithm based on cuckoo optimization for task allocation problem at compile time in heterogeneous systems. Expert Syst. Appl. 60 (2016), 234--248.

Digital Library

[2]

Philippe Baptiste, Claude Le Pape, and Wim Nuijten. 2001. Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems, Springer US.

Digital Library

[3]

Luca Benini, Michele Lombardi, Michela Milano, and Martino Ruggiero. 2011. Optimal resource allocation and scheduling for the CELL BE platform. Ann. Oper. Res. 184, 1 (April 2011), 51--77.

[4]

Shishir Bharathi, Ann Chervenak, Ewa Deelman, Gaurang Mehta, Mei-Hui Su, and Karan Vahi. 2008. Characterization of scientific workflows. In Proceedings of the 3rd Workshop on Workflows in Support of Large-Scale Science. IEEE, 1--10.

[5]

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 Conference on Parallel, Distributed and Network-Based Processing. IEEE, 27--34.

Digital Library

[6]

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 Principles and Practice of Constraint Programming -- CP 2004. 153--167.

Digital Library

[7]

Louis-Claude Canon, Emmanuel Jeannot, Rizos Sakellariou, and Wei Zheng. 2008. Comparative evaluation of the robustness of DAG scheduling heuristics. In Grid Computing. Boston, MA: Springer US, 73--84.

[8]

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 (October 2011), 1884--1897.

Digital Library

[9]

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 Annual Design Automation Conference (DAC’12). New York, New York: ACM, 664.

Digital Library

[10]

Pablo E. Coll, Celso C. Ribeiro, and Cid C. de Souza. 2006. Multiprocessor scheduling under precedence constraints: Polyhedral results. Discret. Appl. Math. 154, 5 (April 2006), 770--801.

Digital Library

[11]

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 2013 International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES). IEEE, 1--10.

Digital Library

[12]

TODAES DAGs. 2017. Data sets of Directed Acyclic Graphs. Retrieved from https://www.dropbox.com/s/21dc97fzcwfc380/TODAES_DAGs.rar?dl=0.

[13]

Yanyan Dai and Xiangli Zhang. 2014. A synthesized heuristic task scheduling algorithm. Sci. World J. 2014 (2014).

[14]

Andreas Emeretlis, George Theodoridis, Panayiotis Alefragis, and Nikolaos Voros. 2016a. A hybrid approach for mapping and scheduling on heterogeneous multicore systems. In Proceedings of the 2016 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS).

[15]

Andreas Emeretlis, George Theodoridis, Panayiotis Alefragis, and Nikolaos Voros. 2016b. A logic-based benders decomposition approach for mapping applications on heterogeneous multicore platforms. ACM Trans. Embed. Comput. Syst. 15, 1 (February 2016), 1--28.

Digital Library

[16]

FICO®. 2013. FICO Xpress Optimization Suite. Retrieved May 1, 2016 from http://www.fico.com/en/products/fico-xpress-optimization-suite/.

[17]

Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman.

Digital Library

[18]

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

Digital Library

[19]

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

Digital Library

[20]

J. N. Hooker. 2005. A hybrid method for the planning and scheduling. Constraints 10, 4 (October 2005), 385--401.

Digital Library

[21]

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

Digital Library

[22]

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

[23]

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

Digital Library

[24]

Yuyi Jiang, Zhiqing Shao, and Yi Guo. 2014. A DAG scheduling scheme on heterogeneous computing systems using tuple-based chemical reaction optimization. Sci. World J. 2014 (2014).

[25]

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

Digital Library

[26]

Ulrich Junker. 2004. QuickXplain: Preferred explanations and relaxations for over-constrained problems. In Proceedings of the 19th National Conference on Artifical Intelligence (AAAI’04). 167--172.

Digital Library

[27]

Konstantinos Kaparis and Adam N. Letchford. 2011. Cover inequalities. In Wiley Encyclopedia of Operations Research and Management Science. 1--11.

[28]

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

Digital Library

[29]

Kenli Li, Shuai Li, Yuming Xu, and Zhaoxin Xie. 2014. A DAG Task scheduling scheme on heterogeneous computing systems using invasive weed optimization algorithm. In Proceedings of the 2014 6th Int. Symposium on Parallel Architectures, Algorithms, and Programming. 262--267.

[30]

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

[31]

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.

Digital Library

[32]

Richard Kipp Martin. 1999. Large Scale Linear and Integer Optimization: A Unified Approach. Springer.

[33]

Michela Milano ed. 2004. Constraint and Integer Programming: Toward a Unified Methodology. Springer.

[34]

George L. Nemhauser and Laurence A. Wolsey. 1999. Integer and Combinatorial Optimization. John Wiley 8 Sons, Inc.

Digital Library

[35]

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

Digital Library

[36]

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 (May 2006), 209--217.

Digital Library

[37]

Georgios K. D. Saharidis and Marianthi G. Ierapetritou. 2010. Improving benders decomposition using maximum feasible subsystem (MFS) cut generation strategy. Comput. Chem. Eng. 34, 8 (2010), 1237--1245.

[38]

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.

[39]

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 8 Test in Europe Conference 8 Exhibition. IEEE, 1--6.

Digital Library

[40]

Amit Kumar Singh, Muhammad Shafique, Akash Kumar, and Jörg Henkel. 2013. Mapping on multi/many-core systems. In Proceedings of the 50th Annual Design Automation Conference (DAC’13). ACM, New York, 1.

Digital Library

[41]

Oliver Sinnen. 2007. Task Scheduling for Parallel Systems. John Wiley 8 Sons, Inc., Hoboken, NJ.

Digital Library

[42]

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.

[43]

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). IEEE, 29--40.

Digital Library

[44]

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

Digital Library

[45]

Tony T. Tran and J. Christopher Beck. 2012. Logic-based benders decomposition for alternative resource scheduling with sequence dependent setups. Front. Artif. Intell. Appl. 242 (2012), 774--779.

[46]

Pascal van Hentenryck and Michela Milano, eds. 2011. Hybrid Optimization, New York, NY: Springer New York.

[47]

Guan Wang, Yuxin Wang, Hui Liu, and He Guo. 2016. HSIP: A novel task scheduling algorithm for heterogeneous computing. Sci. Program. 2016 (2016).

[48]

Christophe Wolinski, Krzysztof Kuchcinski, and Erwan Raffin. 2009. Automatic design of application-specific reconfigurable processor extensions with UPaK synthesis kernel. ACM Trans. Des. Autom. Electron. Syst. 15, 1 (2009), 1--36.

Digital Library

Cited By

Ahmadi-Pour SSaha SMcDonald-Maier KDrechsler R(2025)MESSI: Task Mapping and Scheduling Strategy for FPGA-based Heterogeneous Real-Time SystemsACM Transactions on Design Automation of Electronic Systems10.1145/371532330:3(1-29)Online publication date: 25-Jan-2025
https://dl.acm.org/doi/10.1145/3715323
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
Wilhelm MGeppert HDrewes APionteck T(2023)A comprehensive modeling approach for the task mapping problem in heterogeneous systems with dataflow processing unitsConcurrency and Computation: Practice and Experience10.1002/cpe.790935:25Online publication date: 14-Sep-2023
https://doi.org/10.1002/cpe.7909
Show More Cited By

Index Terms

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

Recommendations

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

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 ...
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 ...
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-...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 23, Issue 2

March 2018

341 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/3149546

Editor:
Naehyuck Chang
Korea Advanced Institute of Science and Technology, Korea

Issue’s Table of Contents

Copyright © 2017 Owner/Author.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

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: 21 December 2017

Accepted: 01 August 2017

Revised: 01 May 2017

Received: 01 July 2016

Published in TODAES Volume 23, Issue 2

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

WCET-Aware Parallelization of Model-Based Applications for Heterogeneous Parallel Systems (ARGO)
European Union under the Horizon 2020 Framework Program

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
174
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ahmadi-Pour SSaha SMcDonald-Maier KDrechsler R(2025)MESSI: Task Mapping and Scheduling Strategy for FPGA-based Heterogeneous Real-Time SystemsACM Transactions on Design Automation of Electronic Systems10.1145/371532330:3(1-29)Online publication date: 25-Jan-2025
https://dl.acm.org/doi/10.1145/3715323
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
Wilhelm MGeppert HDrewes APionteck T(2023)A comprehensive modeling approach for the task mapping problem in heterogeneous systems with dataflow processing unitsConcurrency and Computation: Practice and Experience10.1002/cpe.790935:25Online publication date: 14-Sep-2023
https://doi.org/10.1002/cpe.7909
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
Guo PHe XLuan YWang Y(2020)Logic-based Benders decomposition for gantry crane scheduling with transferring position constraints in a rail–road container terminalEngineering Optimization10.1080/0305215X.2019.1699919(1-21)Online publication date: 10-Jan-2020
https://doi.org/10.1080/0305215X.2019.1699919
Reder SKempf FBucher HBecker JAlefragis PVoros NSkalistis SDerrien SPuaut IOey OStripf TFerdinand CDavid CUlbig PMueller DDurak U(2019)Worst-Case Execution-Time-Aware Parallelization of Model-Based Avionics ApplicationsJournal of Aerospace Information Systems10.2514/1.I010749(1-14)Online publication date: 25-Oct-2019
https://doi.org/10.2514/1.I010749
Li SChen WChen YChen CZheng Z(2019)Makespan-minimized Computation Offloading for Smart Toys in Edge-Cloud ComputingElectronic Commerce Research and Applications10.1016/j.elerap.2019.100884(100884)Online publication date: Aug-2019
https://doi.org/10.1016/j.elerap.2019.100884

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.

Figures

Tables

Media

View Issue’s Table of Contents