research-article

Fast multidimension multichoice knapsack heuristic for MP-SoC runtime management

Authors:

Ch. Ykman-Couvreur,

H. CorporaalAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 10, Issue 3

Article No.: 35, Pages 1 - 16

https://doi.org/10.1145/1952522.1952528

Published: 05 May 2011 Publication History

Abstract

Since the application complexity is growing and applications can be dynamically activated, the major challenge for heterogeneous multiprocessor platforms is to select at runtime an energy-efficient mapping of these applications. Taking into account that many different possible implementations per application can be available, and that the selection must meet the application deadlines under the available platform resources, this runtime optimization problem can be modeled as a Multidimension Multichoice Knapsack Problem (MMKP), which is known to be NP-hard. Not only algorithms for an optimal solution, but also state-of-the-art heuristics for real-time systems are still too slow for runtime management of multiprocessor platforms. This article provides a new fast and lightweight heuristic for finding near-optimal solutions for MMKP problems. The main contribution of this heuristic is: (i) the Pareto filtering of each initial MMKP set to reduce the search space, (ii) the sorting of all Pareto points together in a single two-dimension search space, where (iii) a very fast greedy algorithm solves the MMKP. Experiments show that our heuristic finds solutions close (within 0% to 0.4%) to the ones obtained by the fastest state-of-the-art heuristics, in just a fraction of the execution time (more than 97.5% gain on a StrongARM processor) and can run in less than 1ms for multiprocessor problem sizes. This is required for realistic OS reaction times in video and wireless application sets.

References

[1]

Akbar, M., Manning, E., Shoja, G., and Khan, S. 2001. Heuristic solutions for the multiple-choice multiple-dimension knapsack problem. In Proceedings of the Conference on Computational Science. Springer, Berlin.

Digital Library

[2]

Akbar, M., Rahman, M., Kaykobad, M., Manning, E., and Shoja, G. 2006. Solving the multi-dimensional multiple-choice knapsack problem by constructing convex hulls. Comput. Oper. Res. 33, 5, 1259--1273.

[3]

Armstrong, R., Kung, D., Sinha, P., and Zoltners, A. 1983. A computational study of multiple-choice knapsack algorithm. ACM Trans. Math. Softw. 9, 184--198.

Digital Library

[4]

Bougard, B., Pollin, S., Lenoir, G., Van der Perre, L., Catthoor, F., and Dehaene, W. 2004. Transport level performance-energy trade-off in wireless networks and consequences on the system-level architecture and design paradigm. In Proceedings of the Workshop on Signal Processing Systems. IEEE, Los Alamitos, CA, 77--82.

[5]

CERMSEM. 2004. Multi-choice multi-dimension knapsack problems. ftp://cermsem.univ-paris1.fr/pub/CERMSEM/hi_/MMKP/MMKP.html.

[6]

Cormen, T., Leiserson, C., and Rivest, R. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA.

Digital Library

[7]

Dammeyer, F. and Voss, S. 1991. Dynamic tabu list management using the reverse elimination method. Ann. Oper. Res.

Digital Library

[8]

Drexel, A. 1988. A simulated annealing approach to the multi-constraint zero-one knapsack problem. Ann. Comput. 40, 1--8.

Digital Library

[9]

Khan, S. 1998. Quality adaptation in a multi-session adaptive multimedia system: Model and architecture. Ph.D. thesis, Department of Electrical and Computer Engineering, University of Victoria.

Digital Library

[10]

Khan, S., Li, K., and Manning, E. 1997. The utility model for adaptive multimedia systems. In Proceedings of the International Workshop on Multimedia Modeling. 111--126.

[11]

Khan, S., Li, K., Manning, E., and Akbar, M. 2002. Solving the knapsack problem for adaptive multimedia system. Studia Informatica Universalis, 161--182.

[12]

Khuri, S., Back, T., and Heitkotter, J. 1994. The zero/one multiple knapsack problem and genetic algorithms. InProceedings of the Symposium of Applied Computation. ACM, New York.

Digital Library

[13]

Koleser, P. 1967. A branch and bound algorithm for knapsack problem. Manage. Sci. 13, 723--735.

[14]

Lee, C., Lehoczky, J., Siewiorek, D., Rajkumar, R., and Hansen, J. 1999. A scalable solution to the multi-resource QoS problem. In Proceedings of the Real-Time Systems Symposium. IEEE, Los Alamitos, CA, 315--326.

Digital Library

[15]

Mangharam, R., Pollin, S., Bougard, B., Rajkumar, R., Catthoor, F., Van der Perre, L., and Moerman, I. 2005. Optimal fixed and scalable energy management for wireless networks. In Proceedings of the Conference on Computer Communications. IEEE, Los Alamitos, CA.

[16]

Martello, S. and Toth, P. 1990. Knapsack Problems: Algorithms and Computer Implementations. J. Wiley and Sons, Hoboken, NJ.

Digital Library

[17]

Maruyama, T., Takagi, M., and Hoshino, T. 1999. Hardware implementation techniques for recursive calls and loops. In Proceedings of the International Conference on Field Programmable Logic and Applications. IEEE, Los Alamitos, CA, 450--455.

Digital Library

[18]

McVoy, L. W. and Staelin, C. 1996. lmbench: Portable tools for performance analysis. In Proceedings of the Annual Technical Conference. USENIX, Berkeley, CA, 279--294.

Digital Library

[19]

Mejia-Alvarez, P., Levner, E., and Mosse, D. 2002. Power-optimized scheduling server for real-time tasks. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium. IEEE, Los Alamitos, CA, 239--250.

Digital Library

[20]

Moser, M., Jokanovic, D., and Shiratori, N. 1997. An algorithm for the multi-dimensional multiple-choice knapsack problem. IEICE Tran. Fundam. Electron. 80, 3, 582--589.

[21]

Parra-Hernandez, R. and Dimopoulos, N. 2005. A new heuristic for solving the multi-choice multi-dimensional knapsack problem. IEEE Trans. Syst. Man Cybernetics Part A Syst. Humans 35, 5, 708--717.

Digital Library

[22]

Qin, W. and Malik, S. 2003. Flexible and formal modeling of micro-processors with application to retargetable simulation. In Proceedings of the Conference on Design, Automation and Test in Europe. IEEE, Los Alamitos, CA, 556--561.

Digital Library

[23]

Tachibana, T., Murata, Y., Shibata, N., Yasumoto, K., and Ito, M. 2006. Flexible implementation of genetic algorithms on fpgas. In Proceedings of the International Symposium on Field Programmable Gate Arrays. ACM, New York, 236.

Digital Library

[24]

Volder, J. E. 1959. The CORDIC trigonometric computing technique. IRE Trans. Electron. Comput. EC-8, 330--334.

[25]

Yang, P. and Catthoor, F. 2003. Pareto-optimization-based run-time task scheduling for embedded systems. In Proceedings of the International Symposium on System Synthesis. IEEE, Los Alamitos, CA, 120--125.

Digital Library

[26]

Ykman-Couvreur, C., Brockmeyer, E., Nollet, V., Marescaux, T., Catthoor, F., and Corporaal, H. 2005. Design-time application exploration for MP-SoC customized run-time management. In Proceedings of the International Symposium on System-on-Chip. IEEE, Los Alamitos, CA, 66--73.

[27]

Ykman-Couvreur, C., Nollet, V., Marescaux, T., Brockmeyer, E., Catthoor, F., and corporaal, H. 2006. Pareto-based application specification for MP-SoC customized run-time management. In Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation. IEEE, Los Alamitos, CA, 78--84.

Cited By

Wilbaut CHanafi SCoelho ILucena A(2022)The Knapsack Problem and Its Variants: Formulations and Solution MethodsThe Palgrave Handbook of Operations Research10.1007/978-3-030-96935-6_4(105-151)Online publication date: 8-Jul-2022
https://doi.org/10.1007/978-3-030-96935-6_4
Byholm BPorres IReed DSun XFoster I(2014)Cost-efficient, reliable, utility-based session management in the cloudProceedings of the 14th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing10.1109/CCGrid.2014.22(102-111)Online publication date: 26-May-2014
https://dl.acm.org/doi/10.1109/CCGrid.2014.22
Posadas HNicolás APeñil PVillar EBroekaert FBourdelles MCohen ALazarescu MLavagno LTerechko AGlassee MPrieto M(2014)Improving the design flow for parallel and heterogeneous architectures running real-time applicationsMicroprocessors & Microsystems10.1016/j.micpro.2014.05.00338:8(960-975)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1016/j.micpro.2014.05.003
Show More Cited By

Index Terms

Fast multidimension multichoice knapsack heuristic for MP-SoC runtime management
1. Applied computing
  1. Physical sciences and engineering
    1. Mathematics and statistics
2. Mathematics of computing
  1. Discrete mathematics

Recommendations

A fast and scalable multidimensional multiple-choice knapsack heuristic
Special Section on Networks on Chip: Architecture, Tools, and Methodologies

Many combinatorial optimization problems in the embedded systems and design automation domains involve decision making in multidimensional spaces. The multidimensional multiple-choice knapsack problem (MMKP) is among the most challenging of the ...
A New Heuristic for Solving the Multichoice Multidimensional Knapsack Problem

A new heuristic for solving the multichoice multidimensional knapsack problem (MMKP) is presented in this paper. The MMKP is first reduced to a multidimensional knapsack problem (MKP). A linear programming relaxation of the resulting MKP is solved, and ...
An exact algorithm for the knapsack sharing problem

In this paper, we develop an exact algorithm for solving the knapsack sharing problem. The algorithm is a new version of the method proposed in Hifi and Sadfi (J. Combin. Optim. 6 (2002) 35). It seems quite efficient in the sense that it solves quickly ...

Reviews

Reviewer: Hamid R. Noori

Knapsack problems are among the most intensely studied problems in combinatorial optimization. In this paper, Ykman-Couvreur et al. present "a new fast and lightweight heuristic for finding near-optimal solutions for [multidimension multichoice knapsack problems (MMKPs)]." The MMKP is a combination of the multidimension knapsack problem (where several resources are present, but only one set) and the multichoice knapsack problem (where several sets exist, but only one resource). Within this framework, the authors introduce a multiprocessor system-on-chip (MP-SoC) heuristic suitable for multiprocessor platforms, which they then challenge on both solution quality and performance, compared with the state-of-the-art heuristics. Although the discussed issue is very complex, the authors manage to find an optimal balance between a comprehensive presentation, in terms of a consistent thread and useful illustrations, and high mathematical accuracy. However, while this paper targets specialists in this area with an interest in efficient algorithms for solving MMKPs, it fails to attract mathematicians in other disciplines. Based on the remarkable advantages of the presented study, the paper is recommended to readers with further applications in mind. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

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 10, Issue 3

April 2011

205 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/1952522

Issue’s Table of Contents

Copyright © 2011 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: 05 May 2011

Accepted: 01 November 2007

Revised: 01 June 2007

Received: 01 November 2006

Published in TECS Volume 10, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
384
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wilbaut CHanafi SCoelho ILucena A(2022)The Knapsack Problem and Its Variants: Formulations and Solution MethodsThe Palgrave Handbook of Operations Research10.1007/978-3-030-96935-6_4(105-151)Online publication date: 8-Jul-2022
https://doi.org/10.1007/978-3-030-96935-6_4
Byholm BPorres IReed DSun XFoster I(2014)Cost-efficient, reliable, utility-based session management in the cloudProceedings of the 14th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing10.1109/CCGrid.2014.22(102-111)Online publication date: 26-May-2014
https://dl.acm.org/doi/10.1109/CCGrid.2014.22
Posadas HNicolás APeñil PVillar EBroekaert FBourdelles MCohen ALazarescu MLavagno LTerechko AGlassee MPrieto M(2014)Improving the design flow for parallel and heterogeneous architectures running real-time applicationsMicroprocessors & Microsystems10.1016/j.micpro.2014.05.00338:8(960-975)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1016/j.micpro.2014.05.003
(2013)BibliographyMulticore Technology10.1201/b15268-20(409-450)Online publication date: 18-Jul-2013
https://doi.org/10.1201/b15268-20
Shojaei HBasten TGeilen MDavoodi A(2013)A fast and scalable multidimensional multiple-choice knapsack heuristicACM Transactions on Design Automation of Electronic Systems10.1145/2541012.254101418:4(1-32)Online publication date: 25-Oct-2013
https://dl.acm.org/doi/10.1145/2541012.2541014
Mariani GPalermo GZaccaria VSilvano C(2013)Design-space exploration and runtime resource management for multicoresACM Transactions on Embedded Computing Systems10.1145/2514641.251464713:2(1-27)Online publication date: 30-Sep-2013
https://dl.acm.org/doi/10.1145/2514641.2514647
Mariani GPalermo GZaccaria VSilvano C(2013)ARTE: An Application-specific Run-Time managEment framework for multi-cores based on queuing modelsParallel Computing10.1016/j.parco.2013.04.00239:9(504-519)Online publication date: Sep-2013
https://doi.org/10.1016/j.parco.2013.04.002
Mariani GSima VPalermo GZaccaria VSilvano CBertels KRosenstiel WMacii E(2012)Using multi-objective design space exploration to enable run-time resource management for reconfigurable architecturesProceedings of the Conference on Design, Automation and Test in Europe10.5555/2492708.2493045(1379-1384)Online publication date: 12-Mar-2012
https://dl.acm.org/doi/10.5555/2492708.2493045
Ykman-Couvreur CHartmann PPalermo GColas-Bigey FSan LJerraya ACarloni LChang NFummi F(2012)Run-time resource management based on design space explorationProceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis10.1145/2380445.2380530(557-566)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.1145/2380445.2380530
Paone EPalermo GZaccaria VSilvano CMelpignano DHaugou GLepley TJerraya ACarloni LChang NFummi F(2012)An exploration methodology for a customizable OpenCL stereo-matching application targeted to an industrial multi-cluster architectureProceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis10.1145/2380445.2380523(503-512)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.1145/2380445.2380523
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