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
* Corresponding author
3 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS
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.
Liste complète des métadonnées
Contributor : Arnaud Legrand <>
Submitted on : Wednesday, February 13, 2013 - 3:02:33 PM
Last modification on : Friday, November 16, 2018 - 1:40:47 AM



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. pp.236 - 243, ⟨10.1109/ICPADS.2012.41⟩. ⟨hal-00788008⟩



Record views