{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T20:07:15Z","timestamp":1682366835995},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2011,4]]},"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.<\/jats:p>","DOI":"10.1145\/1952522.1952528","type":"journal-article","created":{"date-parts":[[2011,5,3]],"date-time":"2011-05-03T12:48:53Z","timestamp":1304426933000},"page":"1-16","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Fast multidimension multichoice knapsack heuristic for MP-SoC runtime management"],"prefix":"10.1145","volume":"10","author":[{"given":"Ch.","family":"Ykman-Couvreur","sequence":"first","affiliation":[{"name":"IMEC Leuven, Belgium"}]},{"given":"V.","family":"Nollet","sequence":"additional","affiliation":[{"name":"IMEC Leuven, Belgium"}]},{"given":"F.","family":"Catthoor","sequence":"additional","affiliation":[{"name":"IMEC Leuven, Katholieke University, Belgium"}]},{"given":"H.","family":"Corporaal","sequence":"additional","affiliation":[{"name":"Technical University Eindhoven"}]}],"member":"320","published-online":{"date-parts":[[2011,5,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Conference on Computational Science. Springer","author":"Akbar M.","unstructured":"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. 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."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2004.09.016"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/357456.357458"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Workshop on Signal Processing Systems. IEEE","author":"Bougard B.","unstructured":"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. 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."},{"key":"e_1_2_1_5_1","unstructured":"CERMSEM. 2004. Multi-choice multi-dimension knapsack problems. ftp:\/\/cermsem.univ-paris1.fr\/pub\/CERMSEM\/hi_\/MMKP\/MMKP.html. CERMSEM. 2004. Multi-choice multi-dimension knapsack problems. ftp:\/\/cermsem.univ-paris1.fr\/pub\/CERMSEM\/hi_\/MMKP\/MMKP.html."},{"key":"e_1_2_1_6_1","unstructured":"Cormen T. Leiserson C. and Rivest R. 1990. Introduction to Algorithms. MIT Press Cambridge MA. Cormen T. Leiserson C. and Rivest R. 1990. Introduction to Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_1_7_1","unstructured":"Dammeyer F. and Voss S. 1991. Dynamic tabu list management using the reverse elimination method. Ann. Oper. Res. Dammeyer F. and Voss S. 1991. Dynamic tabu list management using the reverse elimination method. Ann. Oper. Res."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242185"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the International Workshop on Multimedia Modeling. 111--126","author":"Khan S.","unstructured":"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 . 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."},{"key":"e_1_2_1_11_1","unstructured":"Khan S. Li K. Manning E. and Akbar M. 2002. Solving the knapsack problem for adaptive multimedia system. Studia Informatica Universalis 161--182. Khan S. Li K. Manning E. and Akbar M. 2002. Solving the knapsack problem for adaptive multimedia system. Studia Informatica Universalis 161--182."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/326619.326694"},{"key":"e_1_2_1_13_1","first-page":"723","article-title":"A branch and bound algorithm for knapsack problem. Manage","volume":"13","author":"Koleser P.","year":"1967","unstructured":"Koleser , P. 1967 . A branch and bound algorithm for knapsack problem. Manage . Sci. 13 , 723 -- 735 . Koleser, P. 1967. A branch and bound algorithm for knapsack problem. Manage. Sci. 13, 723--735.","journal-title":"Sci."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Real-Time Systems Symposium. IEEE","author":"Lee C.","unstructured":"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. 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."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Conference on Computer Communications. IEEE","author":"Mangharam R.","unstructured":"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. 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."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/98124"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the International Conference on Field Programmable Logic and Applications. IEEE","author":"Maruyama T.","unstructured":"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. 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."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Annual Technical Conference. USENIX","author":"McVoy L. W.","unstructured":"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. 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."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Real-Time and Embedded Technology and Applications Symposium. IEEE","author":"Mejia-Alvarez P.","unstructured":"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. 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."},{"key":"e_1_2_1_20_1","first-page":"582","article-title":"An algorithm for the multi-dimensional multiple-choice knapsack problem","volume":"80","author":"Moser M.","year":"1997","unstructured":"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 . 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.","journal-title":"IEICE Tran. Fundam. Electron."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCA.2005.851140"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe. IEEE","author":"Qin W.","unstructured":"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. 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."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1117201.1117264"},{"key":"e_1_2_1_24_1","article-title":"The CORDIC trigonometric computing technique. IRE","author":"Volder J. E.","year":"1959","unstructured":"Volder , J. E. 1959 . The CORDIC trigonometric computing technique. IRE Trans. Electron. Comput. EC-8, 330--334. Volder, J. E. 1959. The CORDIC trigonometric computing technique. IRE Trans. Electron. Comput. EC-8, 330--334.","journal-title":"Trans. Electron. Comput. EC-8, 330--334."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/944645.944680"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the International Symposium on System-on-Chip. IEEE","author":"Ykman-Couvreur C.","unstructured":"Ykman-Couvreur , C. , Brockmeyer , E. , Nollet , V. , Marescaux , T. , Catthoor , F. , and Corp oraal, 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. 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."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSAMOS.2006.300812"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1952522.1952528","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T19:42:24Z","timestamp":1672342944000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1952522.1952528"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["10.1145\/1952522.1952528"],"URL":"https:\/\/doi.org\/10.1145\/1952522.1952528","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4]]},"assertion":[{"value":"2006-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-05-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}