TY - JOUR
T1 - EagerMap
T2 - A task mapping algorithm to improve communication and load balancing in clusters of multicore systems
AU - Cruz, Eduardo H.M.
AU - Diener, Matthias
AU - Pilla, Laércio L.
AU - Navaux, Philippe O.A.
N1 - Funding Information:
This research received funding from the EU H2020 Programme and from MCTI/RNP-Brazil under the HPC4E project, grant agreement n.° 689772. It was also supported by Intel. Authors’ addresses: E. H. M. Cruz, Instituto Federal do Paraná - Campus Paranavaí - Rua José Felipe Tequinha 1400 - Jardim das Nações - Cep: 87703-536 - Paranavaí - PR, Brazil; email: [email protected]; M. Diener, University of Illinois at Urbana-Champaign, 1308 W Main St, Urbana IL, 61801, USA; email: [email protected]; L. L. Pilla, Laboratoire de Recherche en Informatique Bât 650 Ada Lovelace, Université Paris Sud, 91405 Orsay Cedex France; email: [email protected]; P. O. A. Navaux, Instituto de Informática – Universidade Federal do Rio Grande do Sul (UFRGS), Caixa Postal 15.064 – 91.501-970, Porto Alegre – RS, Brazil; email: [email protected]. 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]. © 2019 Association for Computing Machinery. 2329-4949/2019/03-ART17 $15.00 https://doi.org/10.1145/3309711
Funding Information:
This research received funding from the EU H2020 Programme and from MCTI/RNP-Brazil under the HPC4E project, grant agreement n.° 689772. It was also supported by Intel.
Publisher Copyright:
© 2019 Association for Computing Machinery.
PY - 2019/3
Y1 - 2019/3
N2 - 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.
AB - 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.
KW - Clusters
KW - Communication
KW - Locality
KW - Task mapping
UR - http://www.scopus.com/inward/record.url?scp=85065770209&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85065770209&partnerID=8YFLogxK
U2 - 10.1145/3309711
DO - 10.1145/3309711
M3 - Article
AN - SCOPUS:85065770209
SN - 2329-4949
VL - 5
JO - ACM Transactions on Parallel Computing
JF - ACM Transactions on Parallel Computing
IS - 4
M1 - 17
ER -