A Simulation Workflow to Evaluate the Performance of Dynamic Load Balancing with Over-decomposition for Iterative Parallel Applications

Autor: Keller Tesser, Rafael
Přispěvatelé: Universidade Federal do Rio Grande do Sul [Porto Alegre] (UFRGS), Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Universidade Federal Do Rio Grande Do Sul, Philippe Olivier A. Navaux, Arnaud Legrand (arnaud.legrand@imag.fr)
Jazyk: angličtina
Rok vydání: 2018
Předmět:
Zdroj: Distributed, Parallel, and Cluster Computing [cs.DC]. Universidade Federal Do Rio Grande Do Sul, 2018. English
Popis: In this thesis we present a novel simulation workflow to evaluate the performance of dynamic load balancing with over-decomposition applied to iterative parallel applications at low-cost. Its goals are to perform such evaluation with minimal application modification and at a low cost in terms of time and of resource requirements. Many parallel applications suffer from dynamic (temporal) load imbalance that can not be treated at the application level. It may be caused by intrinsic characteristics of the application or by external software and hardware factors. As demonstrated in this thesis, such dynamic imbalance can be found even in applications whose codes do not hint at any dynamism. Therefore, we need to rely on runtime dynamic load balancing mechanisms, such as dynamic load balancing based on over-decomposition. The problem is that evaluating and tuning the performance of such technique can be costly. This usually entails modifications to the application and a large number of executions to get statistically sound performance measurements with different load balancing parameter combinations. Moreover, useful and accurate measurements often require big resource allocations on a production cluster. Our simulation workflow, dubbed Simulated Adaptive MPI (SAMPI), employs a combined sequential emulation and trace-replay simulation approach to reduce the cost of such an evaluation. Both sequential emulation and trace-replay require a single computer node. Additionally, the trace-replay simulation lasts a small fraction of the real-life parallel execution time of the application. Besides the basic SAMPI simulation, we developed spatial aggregation and application-level rescaling techniques to speed-up the emulation process. To demonstrate the real-life performance benefits of dynamic load balance with over-decomposition, we evaluated the performance gains obtained by employing this technique on a iterative parallel geophysics application, called Ondes3D. Dynamic load balancing support was provided by Adaptive MPI (AMPI). This resulted in up to 36.58% performance improvement, on 288 cores of a cluster. This real-life evaluation also illustrates the difficulties found in this process, thus justifying the use of simulation. To implement the SAMPI workflow, we relied on SimGrid’s Simulated MPI (SMPI) interface in both emulation and trace-replay modes. To validate our simulator, we compared simulated (SAMPI) and real-life (AMPI) executions of Ondes3D. The simulations presented a load balance evolution very similar to real-life and were also successful in choosing the best load balancing heuristic for each scenario. Besides the validation, we demonstrate the use of SAMPI for load balancing parameter exploration and for computational capacity planning. As for the performance of the simulation itself, we roughly estimate that our full workflow can simulate the execution of Ondes3D with 24 different load balancing parameter combinations in ≈ 5 hours for our heavier earthquake scenario and in ≈ 3 hours for the lighter one.; Dans cette thèse, nous présentons un nouveau workflow de simulation pour évaluer la performance de l'équilibrage dynamique de charge quand on surdécompose des applications parallèles itératives à faible coût. L'objectif est d'effectuer une telle évaluation avec un minimum de modifications des applications et à un faible coût en termes de temps et de ressources nécessaires. De nombreuses applications parallèles souffrent d'un déséquilibre de charge dynamique (temporel) qui ne peut être traité au niveau de l'application. Elle peut être causée par des caractéristiques intrinsèques de l'application ou par des facteurs logiciels et matériels externes. Comme le démontre cette thèse, un tel déséquilibre dynamique se retrouve même dans des applications dont les codes ne laissent entrevoir aucun dynamisme. Par conséquent, nous devons nous appuyer sur des mécanismes d'équilibrage de charge dynamique, tels que l'équilibrage de charge dynamique basé sur la surdécomposition. Le problème est que l'évaluation et l'ajustement des performances d'une telle technique peuvent être coûteux. Cela implique généralement des modifications à l'application et un grand nombre d'exécutions pour obtenir des mesures de performance statistiquement fiables avec différentes combinaisons de paramètres d'équilibrage de charge. De plus, des mesures utiles et précises nécessitent souvent d'importantes allocations de ressources sur un cluster de production. Notre workflow de simulation, appelé SAMPI (Simulated Adaptive Adaptive MPI), utilise une approche combinée d'émulation séquentielle et de simulation en mode trace-replay pour réduire le coût d'une telle évaluation. L'émulation séquentielle et l'analyse de traces nécessitent toutes deux un seul nœud d'ordinateur. De plus, la simulation de trace-replay ne dure qu'une petite fraction du temps d'exécution parallèle réel de l'application. En plus de la simulation SAMPI de base, nous avons développé des techniques d'agrégation spatiale et de redimensionnement au niveau de l'application pour accélérer le processus d'émulation. Pour démontrer les avantages réels de l'équilibrage dynamique de charge avec surdécomposition, nous avons évalué les gains de performance obtenus en utilisant cette technique sur une application itérative de géophysique parallèle, appelée Ondes3D. L'équilibrage dynamique de la charge a été assuré par Adaptive MPI (AMPI). Il en a résulté une amélioration de la performance pouvant atteindre 36,58 % sur 288 cœurs d'une grappe. Cette évaluation en situation réelle illustre également les difficultés rencontrées dans ce processus, justifiant ainsi le recours à la simulation. Pour implémenter le workflow SAMPI, nous nous sommes appuyés sur l'interface Simulated MPI (SMPI) de SimGrid en mode émulation et trace-replay. Pour valider notre simulateur, nous avons comparé les exécutions simulées (SAMPI) et réelles (AMPI) d'Ondes3D. Les simulations ont présenté une évolution de l'équilibrage de charge très similaire à la vie réelle et ont également permis de choisir la meilleure heuristique d'équilibrage de charge pour chaque scénario. En plus de la validation, nous démontrons l'utilisation de SAMPI pour l'exploration des paramètres d'équilibrage de charge et pour la planification de la capacité de calcul. Quant à la performance de la simulation elle-même, nous estimons que notre workflow complet peut simuler l'exécution d'Ondes3D avec 24 combinaisons différentes de paramètres d'équilibrage de charge dans ≈ 5 heures pour notre scénario de séisme plus lourd et dans ≈ 3 heures pour le plus simple.
Databáze: OpenAIRE
Externí odkaz: