Search

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.

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.

International audience; Finite-difference methods are commonplace in High Performance Computing applications. Despite their apparent regularity, they often exhibit load imbalance that damages their efficiency. We characterize the spatial and temporal load imbalance of Ondes3D, a typical finite-differences application dedicated to earthquake mod-eling. Our analysis reveals imbalance originating from the structure of the input data, and from low-level CPU optimizations. Ondes3D was successfully ported to AMPI/CHARM++ using over-decomposition and MPI process migration techniques to dynamically rebalance the load. However, this approach requires careful selection of the over-decomposition level, the load balancing algorithm, and its activation frequency. These choices are usually tied to application structure and platform characteristics. In this article, we propose a workflow that leverages the capabilities of SimGrid to conduct such study at low experimental cost. We rely on a combination of emulation, simulation, and application modeling that requires minimal code modification and manages to capture both spatial and temporal load imbalance to faithfully predict the performance of dynamic load balancing. We evaluate the quality of our simulation by comparing simulation results with the outcome of real executions and demonstrate how this approach can be used to quickly find the optimal load balancing configuration for a given application/hardware configuration.