Asymptotically Optimal Load Balancing for Hierarchical Multi-Core Systems

Laércio Pilla 1 Christiane Pousa Ribeiro 2 Philippe Navaux 1 Pierre Coucheney 3 Francois Broquedis 4 Bruno Gaujal 5, * Jean-François Mehaut 5
* Auteur correspondant
3 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS
Inria Rennes – Bretagne Atlantique , IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES
4 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
5 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : Current multi-core machines feature a complex and hierarchical core topology, multiple levels of cache and memory subsystem with NUMA design. Although this design provides high processing power to parallel machines, it comes with the cost of asymmetric memory access latencies. Depending on the parallel application communication patterns, this asymmetry may reduce the overall performance of the system. Therefore, to achieve scalable performance in this environment, it becomes crucial to exploit the machine architecture while taking into account the application communication patterns. In this paper, we introduce a topology-aware load balancing algorithm named HwTopoLB. It combines the machine topology characteristics with the communication patterns of the application to equalize the application load on the available cores while reducing latencies. We also present the proof that the algorithm is asymptotically optimal (Theorem 1). We have implemented our load balancing algorithm using the Charm++ Parallel System and analyzed its performance using three different benchmarks. Our experimental results show that the HwTopoLB can achieve average performance improvements of 24% when compared to existing load balancing strategies on three different multi-core machines.
Type de document :
Communication dans un congrès
Proceedings of the 18th IEEE International Conference on Parallel and Distributed Systems, ICPADS, 2012, Singapore, Singapore. IEEE, pp.236 - 243, 2012, 〈10.1109/ICPADS.2012.41〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00788008
Contributeur : Arnaud Legrand <>
Soumis le : mercredi 13 février 2013 - 15:02:33
Dernière modification le : vendredi 16 novembre 2018 - 01:40:47

Identifiants

Citation

Laércio Pilla, Christiane Pousa Ribeiro, Philippe Navaux, Pierre Coucheney, Francois Broquedis, et al.. Asymptotically Optimal Load Balancing for Hierarchical Multi-Core Systems. Proceedings of the 18th IEEE International Conference on Parallel and Distributed Systems, ICPADS, 2012, Singapore, Singapore. IEEE, pp.236 - 243, 2012, 〈10.1109/ICPADS.2012.41〉. 〈hal-00788008〉

Partager

Métriques

Consultations de la notice

438