{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:55:06Z","timestamp":1760028906099,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,3,13]],"date-time":"2017-03-13T00:00:00Z","timestamp":1489363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Industry-IHL Partnership Grant and Huawei International Pte. Ltd.","award":["NRF2015-IIP003"],"award-info":[{"award-number":["NRF2015-IIP003"]}]},{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001381","name":"National Research Foundation, Prime Minister's Office, Singapore","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Transregional Collaborative Research Centre \u201cInvasive Computing\u201d","award":["SFB\/TR 89"],"award-info":[{"award-number":["SFB\/TR 89"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2017,3,31]]},"abstract":"<jats:p>Many-cores can execute multiple multithreaded tasks in parallel. A task performs most efficiently when it is executed over a spatially connected and compact subset of cores so that performance loss due to communication overhead imposed by the task\u2019s threads spread across the allocated cores is minimal. Over a span of time, unallocated cores can get scattered all over the many-core, creating fragments in the task mapping. These fragments can prevent efficient contiguous mapping of incoming new tasks leading to loss of performance. This problem can be alleviated by using a task defragmenter, which consolidates smaller fragments into larger fragments wherein the incoming tasks can be efficiently executed. Optimal defragmentation of a many-core is an NP-hard problem in the general case. Therefore, we simplify the original problem to a problem that can be solved optimally in polynomial time. In this work, we introduce a concept of exponentially separable mapping (ESM), which defines a set of task mapping constraints on a many-core. We prove that an ESM enforcing many-core can be defragmented optimally in polynomial time.<\/jats:p>","DOI":"10.1145\/3050437","type":"journal-article","created":{"date-parts":[[2017,3,15]],"date-time":"2017-03-15T14:18:04Z","timestamp":1489587484000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Defragmentation of Tasks in Many-Core Architecture"],"prefix":"10.1145","volume":"14","author":[{"given":"Anuj","family":"Pathania","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vanchinathan","family":"Venkataramani","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2607-8135","authenticated-orcid":false,"given":"Muhammad","family":"Shafique","sequence":"additional","affiliation":[{"name":"Vienna University of Technology, Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tulika","family":"Mitra","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg","family":"Henkel","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,3,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454115.1454128"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2024716.2024718"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063454"},{"volume-title":"2015 IEEE 26th International Conference on Application-specific Systems, Architectures and Processors (ASAP). IEEE, 162--163","author":"Catania V.","key":"e_1_2_1_4_1","unstructured":"V. Catania , A. Mineo , S. Monteleone , M. Palesi , and D. Patti . 2015. Noxim: An open, extensible and cycle-accurate network on chip simulator . In 2015 IEEE 26th International Conference on Application-specific Systems, Architectures and Processors (ASAP). IEEE, 162--163 . V. Catania, A. Mineo, S. Monteleone, M. Palesi, and D. Patti. 2015. Noxim: An open, extensible and cycle-accurate network on chip simulator. In 2015 IEEE 26th International Conference on Application-specific Systems, Architectures and Processors (ASAP). IEEE, 162--163."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2006.31"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-007-0713-4"},{"volume-title":"Proceedings of the Canadian Conference on Computational Geometry.","author":"Erik","key":"e_1_2_1_7_1","unstructured":"Erik D. Demaine and Michael Hoffmann. 2001. Pushing blocks is NP-complete for noncrossing solution paths . In Proceedings of the Canadian Conference on Computational Geometry. Erik D. Demaine and Michael Hoffmann. 2001. Pushing blocks is NP-complete for noncrossing solution paths. In Proceedings of the Canadian Conference on Computational Geometry."},{"volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"Dutot Pierre-Fran\u00e7ois","key":"e_1_2_1_8_1","unstructured":"Pierre-Fran\u00e7ois Dutot , Gr\u00e9gory Mouni\u00e9 , and Denis Trystram . 2004. Scheduling parallel tasks: Approximation algorithms . In Handbook of Scheduling: Algorithms, Models, and Performance Analysis . CRC Press , Boca Raton, FL , 26-1. Pierre-Fran\u00e7ois Dutot, Gr\u00e9gory Mouni\u00e9, and Denis Trystram. 2004. Scheduling parallel tasks: Approximation algorithms. In Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Boca Raton, FL, 26-1."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1687399.1687457"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391664"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488782"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2014.6742914"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0053978"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSESS.2010.5552275"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2012.6164944"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2012.6237032"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/365628.365655"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/100348.100352"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1362622.1362694"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2016.2548564"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 2006 Linux Symposium.","author":"Pallipadi Venkatesh","year":"2006","unstructured":"Venkatesh Pallipadi and Alexey Starikovskiy . 2006 . The ondemand governor . In Proceedings of the 2006 Linux Symposium. Venkatesh Pallipadi and Alexey Starikovskiy. 2006. The ondemand governor. In Proceedings of the 2006 Linux Symposium."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897937.2898009"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1275571.1275600"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488734"},{"key":"e_1_2_1_25_1","volume-title":"The On-Line Encyclopedia of Integer Sequences. Retrieved","author":"Sloane Neil J. A.","year":"2017","unstructured":"Neil J. A. Sloane . 2003. The On-Line Encyclopedia of Integer Sequences. Retrieved February 14, 2017 , from http:\/\/oeis.org. Neil J. A. Sloane. 2003. The On-Line Encyclopedia of Integer Sequences. Retrieved February 14, 2017, from http:\/\/oeis.org."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854283"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3050437","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3050437","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:28Z","timestamp":1750217788000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3050437"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,13]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3,31]]}},"alternative-id":["10.1145\/3050437"],"URL":"https:\/\/doi.org\/10.1145\/3050437","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2017,3,13]]},"assertion":[{"value":"2016-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}