{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T21:55:42Z","timestamp":1773438942701,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,12,31]],"date-time":"2018-12-31T00:00:00Z","timestamp":1546214400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"HPC4E project","award":["689772"],"award-info":[{"award-number":["689772"]}]},{"name":"EU H2020 Programme"},{"name":"MCTI\/RNP-Brazil"},{"name":"Intel"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>Communication between tasks and load imbalance have been identified as a major challenge for the performance and energy efficiency of parallel applications. A common way to improve communication is to increase its locality, that is, to reduce the distances of data transfers, prioritizing the usage of faster and more efficient local interconnections over remote ones. Regarding load imbalance, cores should execute a similar amount of work. An important problem to be solved in this context is how to determine an optimized mapping of tasks to cluster nodes and cores that increases the overall locality and load balancing. In this article, we propose the EagerMap algorithm to determine task mappings, which is based on a greedy heuristic to match application communication patterns to hardware hierarchies and which can also consider the task load. Compared to previous algorithms, EagerMap is faster, scales better, and supports more types of computer systems, while maintaining the same or better quality of the determined task mapping. EagerMap is therefore an interesting choice for task mapping on a variety of modern parallel architectures.<\/jats:p>","DOI":"10.1145\/3309711","type":"journal-article","created":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T13:16:43Z","timestamp":1552051003000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["EagerMap"],"prefix":"10.1145","volume":"5","author":[{"given":"Eduardo H. M.","family":"Cruz","sequence":"first","affiliation":[{"name":"Federal Institute of Parana (IFPR), Paranava\u00ed - PR, Brazil"}]},{"given":"Matthias","family":"Diener","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana IL, USA"}]},{"given":"La\u00e9rcio L.","family":"Pilla","sequence":"additional","affiliation":[{"name":"Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, Orsay Cedex France"}]},{"given":"Philippe O. A.","family":"Navaux","sequence":"additional","affiliation":[{"name":"Informatics Institute -- Federal University of Rio Grande do Sul (UFRGS), Porto Alegre -- RS, Brazil"}]}],"member":"320","published-online":{"date-parts":[[2019,3,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897783"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531793.1531803"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1177\/109434209100500306"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2018.00018"},{"key":"e_1_2_1_5_1","first-page":"1","article-title":"Communication lower bounds and optimal algorithms for numerical linear algebra","author":"Ballard G.","year":"2014","unstructured":"G. Ballard , E. Carson , J. Demmel , M. Hoemmen , N. Knight , and O. Schwartz . 2014 . Communication lower bounds and optimal algorithms for numerical linear algebra . Acta Numer. 23 , May (2014), 1 -- 155 . G. Ballard, E. Carson, J. Demmel, M. Hoemmen, N. Knight, and O. Schwartz. 2014. Communication lower bounds and optimal algorithms for numerical linear algebra. Acta Numer. 23, May (2014), 1--155.","journal-title":"Acta Numer. 23"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2009.5306792"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454115.1454128"},{"key":"e_1_2_1_8_1","volume-title":"Joint International Conference on Vector and Parallel Processing (CONPAR 90 -- VAPP IV). 405--416","author":"Jacques","unstructured":"Jacques E. Boillat and Peter G. Kropf. 1990. A fast distributed mapping algorithm . In Joint International Conference on Vector and Parallel Processing (CONPAR 90 -- VAPP IV). 405--416 . Jacques E. Boillat and Peter G. Kropf. 1990. A fast distributed mapping algorithm. In Joint International Conference on Vector and Parallel Processing (CONPAR 90 -- VAPP IV). 405--416."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675756"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compfluid.2012.01.019"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/PDP.2010.67"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183401.1183451"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2007.12.001"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.11.006"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/PDP.2015.25"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2975587"},{"key":"e_1_2_1_17_1","volume-title":"Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP). 93--100","author":"Cruz E. H. M.","unstructured":"E. H. M. Cruz , M. Diener , M. S. Serpa , P. O. A. Navaux , L. Pilla , and I. Koren . 2018. Improving communication and load balancing with thread mapping in manycore systems . In Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP). 93--100 . E. H. M. Cruz, M. Diener, M. S. Serpa, P. O. A. Navaux, L. Pilla, and I. Koren. 2018. Improving communication and load balancing with thread mapping in manycore systems. In Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP). 93--100."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.93"},{"key":"e_1_2_1_20_1","volume-title":"Catalyurek","author":"Devine Karen D.","year":"2006","unstructured":"Karen D. Devine , Erik G. Boman , Robert T. Heaphy , Rob H. Bisseling , and Umit V . Catalyurek . 2006 . Parallel hypergraph partitioning for scientific computing. In IEEE International Parallel 8 Distributed Processing Symposium (IPDPS) . 124--133. Karen D. Devine, Erik G. Boman, Robert T. Heaphy, Rob H. Bisseling, and Umit V. Catalyurek. 2006. Parallel hypergraph partitioning for scientific computing. In IEEE International Parallel 8 Distributed Processing Symposium (IPDPS). 124--133."},{"key":"e_1_2_1_21_1","volume-title":"Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Stand.\u2014Section B. Math. Math. Phys. 69B, 1 and 2","author":"Edmonds Jack","year":"1965","unstructured":"Jack Edmonds . 1965. Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Stand.\u2014Section B. Math. Math. Phys. 69B, 1 and 2 ( 1965 ), 125. Jack Edmonds. 1965. Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Stand.\u2014Section B. Math. Math. Phys. 69B, 1 and 2 (1965), 125."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/PDP.2015.21"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compfluid.2012.04.024"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Emmanuel Jeannot and Guillaume Mercier. 2010. Near-optimal placement of MPI processes on hierarchical NUMA architectures. In Euro-Par Parallel Processing. 199--210.   Emmanuel Jeannot and Guillaume Mercier. 2010. Near-optimal placement of MPI processes on hierarchical NUMA architectures. In Euro-Par Parallel Processing. 199--210.","DOI":"10.1007\/978-3-642-15291-7_20"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.104"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3018058.3018065"},{"key":"e_1_2_1_28_1","unstructured":"H. Jin M. Frumkin and J. Yan. 1999. The OpenMP Implementation of NAS Parallel Benchmarks and Its Performance. Technical Report October. NASA.  H. Jin M. Frumkin and J. Yan. 1999. The OpenMP Implementation of NAS Parallel Benchmarks and Its Performance. Technical Report October. NASA."},{"key":"e_1_2_1_29_1","volume-title":"Inside the Linux 2.6 Completely Fair Scheduler. Retrieved","author":"Jones M. Tim","year":"2018","unstructured":"M. Tim Jones . 2009. Inside the Linux 2.6 Completely Fair Scheduler. Retrieved June 2018 from https:\/\/www.ibm.com\/developerworks\/linux\/library\/l-completely-fair-scheduler\/. M. Tim Jones. 2009. Inside the Linux 2.6 Completely Fair Scheduler. Retrieved June 2018 from https:\/\/www.ibm.com\/developerworks\/linux\/library\/l-completely-fair-scheduler\/."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-739X(00)00055-8"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/369028.369103"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065034"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018759"},{"key":"e_1_2_1_37_1","volume-title":"USENIX Annual Technical Conference (ATC). 23--38","author":"McVoy Larry","year":"1996","unstructured":"Larry McVoy and Carl Staelin . 1996 . Lmbench: Portable tools for performance analysis . In USENIX Annual Technical Conference (ATC). 23--38 . Larry McVoy and Carl Staelin. 1996. Lmbench: Portable tools for performance analysis. In USENIX Annual Technical Conference (ATC). 23--38."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SHPCC.1994.296682"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"John Shalf Sudip Dosanjh and John Morrison. 2010. Exascale computing technology challenges. In High Performance Computing for Computational Science (VECPAR). 1--25.   John Shalf Sudip Dosanjh and John Morrison. 2010. Exascale computing technology challenges. In High Performance Computing for Computational Science (VECPAR). 1--25.","DOI":"10.1007\/978-3-642-19328-6_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.30"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGrid.2011.83"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2703149"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPASS.2012.6189222"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2011.49"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309711","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3309711","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:35Z","timestamp":1750204415000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309711"}},"subtitle":["A Task Mapping Algorithm to Improve Communication and Load Balancing in Clusters of Multicore Systems"],"short-title":[],"issued":{"date-parts":[[2018,12,31]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3309711"],"URL":"https:\/\/doi.org\/10.1145\/3309711","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,31]]},"assertion":[{"value":"2017-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}