Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata
Contributor : Arnaud Legrand Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 3:02:33 PM
Last modification on : Friday, January 21, 2022 - 3:10:13 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⟩



Les métriques sont temporairement indisponibles