Scalable Load Balancing: Distributed Approaches and the Packing Model - Equipe : Graphes, Algorithmes et Combinatoire Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2019

Scalable Load Balancing: Distributed Approaches and the Packing Model

Résumé

Periodical load balancing heuristics are employed in parallel iterative applications to assure the effective use of high performance computing platforms. Work stealing is one of the most widely used load balancing techniques, but it is not the most friendly for iterative applications. Optimal mapping of tasks to machines, while minimizing overall makespan, is regarded as an NP-Hard problem; so suboptimal heuristics are used to schedule these tasks in feasible time. Among the existing approaches, distributed load balancers are the most scalable for iterative applications and have much to profit from work stealing. In this work, we propose the discretization of application workload for load balancing, as well as two distributed load balancers: PackDrop, which is based on constrained work diffusion; and PackSteal, which is based on work stealing. Our algorithms group tasks in batches before migration, creating packs of homogeneous load to make scheduling decisions in an informed and timely fashion. Our results show that PackSteal and PackDrop enhanced our molecular dynamics benchmark performance by up to 41% and 29%, respectively, on our largest evaluated scale. Moreover, PackSteal is consistently the most effective in 8 of 9 evaluated scenarios, compared to PackDrop and other load balancing algorithms.
Fichier principal
Vignette du fichier
bare_jrnl_compsoc.pdf (1.53 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02405735 , version 1 (11-12-2019)
hal-02405735 , version 2 (09-06-2020)
hal-02405735 , version 3 (06-07-2020)

Identifiants

  • HAL Id : hal-02405735 , version 1

Citer

Vinicius Freitas, Laércio Lima Pilla, Alexandre Santana, Marcio Castro, Johanne Cohen. Scalable Load Balancing: Distributed Approaches and the Packing Model. 2019. ⟨hal-02405735v1⟩
403 Consultations
285 Téléchargements

Partager

Gmail Facebook X LinkedIn More