97 research outputs found
Vérification et optimisation à la compilation des communications MPI non-bloquantes
No full textLes clusters de Calcul Haute Performance (HPC) sont composés de multiples unités de calcul ou de stockage mémoire, aussi appelés « nœuds », interconnectés par un réseau haut débit et basse latence. Une telle architecture est qualifiée de « distribuée ». Les calculs sont ainsi distribués sur ces nœuds qui vont chacun travailler sur une section d’une simulation, ce qui permet de réduire le temps d’exécution de simulations grâce au parallélisme. Les nœuds doivent toutefois se communiquer leurs résultats afin d’avancer dans les calculs, ce qui cause des latences. Message Passing Interface (MPI) est la solution la plus utilisée en HPC pour définir ces échanges entre nœuds de calcul. Elle définit des communications point-à-point et des communications collectives. Chaque type de communication existe en trois versions : bloquante, non-bloquante, et persistante. Les communications non-bloquantes permettent une meilleure utilisation des ressources de calcul en recouvrant les communications par des calculs, ce qui permet de réduire le temps d’obtention des résultats. Cependant, ces communications non-bloquantes sont plus complexes à l’usage, et offrent moins de mécanismes de sécurité. Les développeurs sont davantage susceptibles de commettre des erreurs de programmation pouvant conduire à des blocages du programme ou corrompre les résultats. Cela conduit à une moindre popularité de ces communications, en particulier de la forme collective introduite lors de la troisième révision majeure de l’interface en 2012, pour dégager du recouvrement. L’objectif de cette étude est de proposer des méthodes visant à aider les développeurs à utiliser ces communications. Premièrement, nous proposons une méthode pour associer les appels non-bloquants lors de la compilation d’un programme MPI en utilisant des informations sur le flot de contrôle et de le flot de données. Dans un deuxième temps, nous proposons une méthode pour automatiquement transformer les appels bloquants dans leur version non-bloquante. Cette méthode va ensuite réorganiser le code d’une fonction en déplaçant les dépendances des communications dans le but de maximiser la taille des intervalles de recouvrement. Cette méthode est également appliquée sur les appels non-bloquants existants en exploitant les associations trouvées par le processus de validation. Enfin, nous exploitons les limitations du processus de transformation automatique afin de proposer une méthode permettant d’améliorer le potentiel de recouvrement des programmes MPI en identifiant les bornes de ces intervalles et en suggérant des modifications de code à appliquer. Les trois processus que nous proposons ont été testés sur plusieurs benchmarks, dont des miniapps et des codes CORAL.High-Performance Computation (HPC) clusters are made of multiple computing and memory storage units (or nodes) interconnected with a high performance network. Such architecture is called”distributed”. Computations are spread over these nodes which each work on a subset of the whole simulation, leading to increased performance thanks to parallelism. The results then needs to be shared between the nodes to carry out the computations, which is source of latencies. The Message Passing Interface (MPI) is the most widely used solution in HPC to implement these exchanges. It defines multiple flavors of communications, including point-to-point and collective communications. They exist in three versions: blocking, nonblocking, and persistent. Nonblocking communications allow the overlapping of communications by computations, thus leading to a better use of computing resources and reduced time to results. Yet this version of the communications, whose collective forms were added to the interface by its third major version in 2012, are harder to use because of their composition and offer less security mechanisms. Developers are more prone to commit programming errors which can lead to deadlocks or data corruption. Consequently, nonblocking communications, and more specifically the collective forms, are still not widely used to create overlapping opportunities. The goal of this study is the development of methods to help developers in using these communications. First, we propose a method to match nonblocking calls at compile-time and to detect programming errors involving those using information on the control flow and the data flow. Secondly, we propose a method to automatically transform existing blocking calls into their nonblocking versions. This method then reorganizes the code of a function by moving the dependencies of communications in order to maximize the length of overlapping intervals. It is also applied on existing nonblocking calls using the matching information found by the verification process. Finally, we build upon the limitations of the automatic approach to propose a method to improve the overlapping potential of MPI programs by identifying the boundaries of overlapping intervals and suggesting code modification to developers. The three processes we proposed have been tested on several benchmarks, including miniapps and CORAL codes
Contribution à la compilation de programmes irréguliers pour des architectures complexes
No full textThès
Contribution to the compilation of irregular programs for complex architectures
No full textContribution à la compilation de programmes irréguliers pour des architecturescomplexesLes architectures multicoeurs sont omniprésentes dans les processeurs généralistes et embarqués. Plusieurs flôts d'instructions (threads) sont exécutés, augmentant le parallélisme, évitant des contentions de ressources.L'execution concurrente d'un thread est déterminant pour le temps d'execution de l'application. Ainsi, l'exploitation fine d'un coeur est indispensable afin de découvrir du parallelisme d'instructions (ILP) au sein d'un flot d'instructions.Cette thèse traite de l'optimisation monocoeur de codes irréguliers comportant du parallélisme "caché". Nous avons conçus des transformations permettant d'augmenter leur ILP : Deep Jam convertissant du parallelisme à gros grain,restructuration des arbres de décisions et une plateforme d'ordonnancement d'instructions unifiant les dépendences de données et les contraintes de ressources complexes. Des accélérations par rapport à des techniques et compilateurs de pointe ont été obtenues sur Itanium 2.Contribution to the Compilation of Irregular Programs for Complex ArchitecturesMulticore architectures are ubiquitous in general purpose and embedded systems. Modern processors execute several instruction flows (threads) increasing the parallelism and accommodating for resource stalls. Both the execution of a thread and its interaction with the others shape the overall performance of an application. Thus, an accurate exploitation of a single core is mandatory: it leads to the necessity to discover the instruction-level parallelism (ILP) within an instruction flow.This thesis focuses on the monocore optimization of irregular codes hoseparallelism is "hidden" behind complex control flow. We designedtransformations to increase their ILP: Deep Jam converting coarse-grain parallelism, decision tree reshaping and an instruction-scheduling framework unifying data dependences and complex resource constraints. Everytransformation leads to significant speedups on a wide issue architecture(Itanium), compared to state-of-the-art techniques and compilers.VERSAILLES-BU Sciences et IUT (786462101) / SudocSudocFranceF
Application of Storage Mapping Optimization to Register Promotion
No full textInternational audienceStorage mapping optimization is a flexible approach to folding array dimensions in numerical codes. It is designed to reduce thememory footprint after a wide spectrum of loop transformations,whether based on uniform dependence vectors or more expressivepolyhedral abstractions. Conversely, few loop transformations havebeen proposed to facilitate register promotion, namely loop fusion,unroll-and-jam or tiling. Building on array data-flow analysis andexpansion, we extend storage mapping optimization to improve opportunities for register promotion.Our work is motivated by the empirical study of a computational biology benchmark, the approximate string matching algorithm BPR from NR-grep , on a wide issue micro-architecture. Ourexperiments confirm the major benefit of register tiling (even onnon-numerical benchmarks) but also shed the light on two novel issues: prior array expansion may be necessary to enable loop trans-formations that finally authorize profitable register promotion, andmore advanced scheduling techniques (beyond tiling and unroll-and-jam) may significantly improve performance in fine-tuning reg-ister usage and instruction-level parallelism
Applications of Storage Mapping Optimization to Register Promotion
No full textStorage mapping optimization is a flexible approach to folding array dimensions in numerical codes. It is designed to reduce the memory footprint after a wide spectrum of loop transformations, whether based on uniform dependence vectors or more expressive polyhedral abstractions. Conversely, few loop transformations have been proposed to facilitate register promotion, namely loop fusion, unroll-and-jam or tiling. Building on array data-flow analysis and expansion, we extend storage mapping optimization to improve opportunities for register promotion. Our work i
From Software Locality to Hardware Locality in Shared Memory Systems with NUMA and Heterogenous Memory
No full textLa hiérarchie mémoire des serveurs de calcul est de plus en plus complexe. Les machines disposent de plusieurs niveaux de caches plus ou moins partagés et d’une mémoire distribuée. Plus récemment le paysage du Calcul Haute Performance (CHP) a vu apparaître des mémoires adressables embarquées dans le processeur ainsi que de nouvelles mémoires non-volatiles (périphérique mémoire sur le bus d’entrées sorties et prochainement de la mémoire non-volatile directement sur le bus mémoire). Cette hiérarchie est nécessaire pour espérer obtenir de bonnes performances de calcul, au prix d’une gestion minutieuse du placement des données et des tâches de calcul. Là où la gestion des caches était entièrement matérielle et masquée au développeur, le choix du placement des données dans telle ou telle zone de mémoire, plus ou moins rapide, volatile ou non, volumineuse ou non, est maintenant paramétrable logiciellement. Cette nouvelle flexibilité donne une grande liberté aux développeurs mais elle complexifie surtout leur travail quand il s’agit de choisir les stratégies d’allocation, de communication, de placement, etc. En effet, les caractéristiques des nombreux niveaux de hiérarchie impliqués varient significativement en vitesse, taille et fonctionnalités. Dans cette thèse, co-encadrée entre Atos Bull Technologies et Inria Bordeaux– Sud-Ouest, nous détaillons la structure des plates-formes contemporaines et caractérisons la performance des accès à la mémoire selon plusieurs scénarios de localité des tâches de calcul et des données accédées. Nous expliquons comment la sémantique du langage de programmation impacte la localité des données dans la machine et donc la performance des applications. En collaboration avec le laboratoire INESC-ID de Lisbonne, nous proposons une extension au célèbre modèle Roofline pour exposer de manière intelligible les compromis de performance et de localité aux développeurs d’applications. Nous proposons par ailleurs un outil de synthèse de métriques de localité mettant en lien les évènements de performance de l’application et de la machine avec la topologie de cette dernière. Enfin, nous proposons une approche statistique pour sélectionner automatiquement la meilleure politique de placement des tâches de calcul sur les coeurs de la machine et des données sur les mémoires.Through years, the complexity of High Performance Computing (HPC) systems’ memory hierarchy has increased. Nowadays, large scale machines typically embed several levels of caches and a distributed memory. Recently, on-chip memories and non-volatile PCIe based flash have entered the HPC landscape. This memory architecture is a necessary pain to obtain high performance, but at the cost of a thorough task and data placement. Hardware managed caches used to hide the tedious locality optimizations. Now, data locality, in local or remote memories, in fast or slow memory, in volatile or non-volatile memory, with small or wide capacity, is entirely software manageable. This extra flexibility grants more freedom to application designers but with the drawback of making their work more complex and expensive. Indeed, when managing tasks and data placement, one has to account for several complex trade-offs between memory performance, size and features. This thesis has been supervised between Atos Bull Technologies and Inria Bordeaux – Sud-Ouest. In the hereby document, we detail contemporary HPC systems and characterize machines performance for several locality scenarios. We explain how the programming language semantics affects data locality in the hardware, and thus applications performance. Through a joint work with the INESC-ID laboratory in Lisbon, we propose an insightful extension to the famous Roofline performance model in order to provide locality hints and improve applications performance. We also present a modeling framework to map platform and application performance events to the hardware topology, in order to extract synthetic locality metrics. Finally, we propose an automatic locality policy selector, on top of machine learning algorithms, to easily improve applications tasks and data placement
Unified system of code transformation and execution for heterogeneous multi-core architectures.
No full textArchitectures hétérogènes sont largement utilisées dans le domaine de calcul haute performance. Cependant, le développement d'applications sur des architectures hétérogènes est indéniablement fastidieuse et sujette à erreur pour un programmeur même expérimenté. Pour passer une application aux architectures multi-cœurs hétérogènes, les développeurs doivent décomposer les données de l'entrée, gérer les échanges de valeur intermédiaire au moment d’exécution et garantir l'équilibre de charge de système. L'objectif de cette thèse est de proposer une solution de programmation parallèle pour les programmeurs novices, qui permet de faciliter le processus de codage et garantir la qualité de code. Nous avons comparé et analysé les défauts de solutions existantes, puis nous proposons un nouvel outil de programmation STEPOCL avec un nouveau langage de domaine spécifique qui est conçu pour simplifier la programmation sur les architectures hétérogènes. Nous avons évalué la performance de STEPOCL sur trois cas d'application classiques : un stencil 2D, une multiplication de matrices et un problème à N corps. Le résultat montre que : (i) avec l'aide de STEPOCL, la performance d'application varie linéairement selon le nombre d'accélérateurs, (ii) la performance de code généré par STEPOCL est comparable à celle de la version manuscrite. (iii) les charges de travail, qui sont trop grandes pour la mémoire d'un seul accélérateur, peuvent être exécutées en utilisant plusieurs accélérateurs. (iv) grâce à STEPOCL, le nombre de lignes de code manuscrite est considérablement réduit.Heterogeneous architectures have been widely used in the domain of high performance computing. However developing applications on heterogeneous architectures is time consuming and error-prone because going from a single accelerator to multiple ones indeed requires to deal with potentially non-uniform domain decomposition, inter-accelerator data movements, and dynamic load balancing. The aim of this thesis is to propose a solution of parallel programming for novice developers, to ease the complex coding process and guarantee the quality of code. We lighted and analysed the shortcomings of existing solutions and proposed a new programming tool called STEPOCL along with a new domain specific language designed to simplify the development of an application for heterogeneous architectures. We evaluated both the performance and the usefulness of STEPOCL. The result show that: (i) the performance of an application written with STEPOCL scales linearly with the number of accelerators, (ii) the performance of an application written using STEPOCL competes with an handwritten version, (iii) larger workloads run on multiple devices that do not fit in the memory of a single device, (iv) thanks to STEPOCL, the number of lines of code required to write an application for multiple accelerators is roughly divided by ten
Unified system of code transformation and execution for heterogeneous multi-core architectures.
No full textArchitectures hétérogènes sont largement utilisées dans le domaine de calcul haute performance. Cependant, le développement d'applications sur des architectures hétérogènes est indéniablement fastidieuse et sujette à erreur pour un programmeur même expérimenté. Pour passer une application aux architectures multi-cœurs hétérogènes, les développeurs doivent décomposer les données de l'entrée, gérer les échanges de valeur intermédiaire au moment d’exécution et garantir l'équilibre de charge de système. L'objectif de cette thèse est de proposer une solution de programmation parallèle pour les programmeurs novices, qui permet de faciliter le processus de codage et garantir la qualité de code. Nous avons comparé et analysé les défauts de solutions existantes, puis nous proposons un nouvel outil de programmation STEPOCL avec un nouveau langage de domaine spécifique qui est conçu pour simplifier la programmation sur les architectures hétérogènes. Nous avons évalué la performance de STEPOCL sur trois cas d'application classiques : un stencil 2D, une multiplication de matrices et un problème à N corps. Le résultat montre que : (i) avec l'aide de STEPOCL, la performance d'application varie linéairement selon le nombre d'accélérateurs, (ii) la performance de code généré par STEPOCL est comparable à celle de la version manuscrite. (iii) les charges de travail, qui sont trop grandes pour la mémoire d'un seul accélérateur, peuvent être exécutées en utilisant plusieurs accélérateurs. (iv) grâce à STEPOCL, le nombre de lignes de code manuscrite est considérablement réduit.Heterogeneous architectures have been widely used in the domain of high performance computing. However developing applications on heterogeneous architectures is time consuming and error-prone because going from a single accelerator to multiple ones indeed requires to deal with potentially non-uniform domain decomposition, inter-accelerator data movements, and dynamic load balancing. The aim of this thesis is to propose a solution of parallel programming for novice developers, to ease the complex coding process and guarantee the quality of code. We lighted and analysed the shortcomings of existing solutions and proposed a new programming tool called STEPOCL along with a new domain specific language designed to simplify the development of an application for heterogeneous architectures. We evaluated both the performance and the usefulness of STEPOCL. The result show that: (i) the performance of an application written with STEPOCL scales linearly with the number of accelerators, (ii) the performance of an application written using STEPOCL competes with an handwritten version, (iii) larger workloads run on multiple devices that do not fit in the memory of a single device, (iv) thanks to STEPOCL, the number of lines of code required to write an application for multiple accelerators is roughly divided by ten
Deep Jam: Conversion of Coarse-Grain Parallelism to Instruction-Level and Vector Parallelism for Irregular Applications
No full textA number of compute-intensive applications suffer from performance loss due to the lack of instruction-level parallelism in sequences of dependent instructions. This is particularly accurate on wide-issue architectures with large register banks, when the memory hierarchy (locality and bandwidth) is not the dominant bottleneck. We consider two real applications from computational biology and from cryptanalysis, characterized by long sequences of dependent instructions, irregular control-flow and intricate scalar and array dependence patterns. Although these applications exhibit excellent memory locality and branch-prediction behavior, state-ofthe -art loop transformations and back-end optimizations are unable to exploit much instruction-level parallelism. We show that good speedups can be achieved through deep jam, a new transformation of the program control- and data-flow. Deep jam combines scalar and array renaming with a generalized form of recursive unrolland -jam; it brings together independent instructions across irregular control structures, removing memory-based dependences. This optimization contributes to the extraction of fine-grain parallelism in irregular applications. We propose a feedback-directed deep jam algorithm, selecting a jamming strategy, function of the architecture and application charactristics
Static/Dynamic Analyses for Validation and Improvements of Multi-Model HPC Applications.
No full textL’utilisation du parallélisme des architectures actuelles dans le domaine du calcul hautes performances, oblige à recourir à différents langages parallèles. Ainsi, l’utilisation conjointe de MPI pour le parallélisme gros grain, à mémoire distribuée et OpenMP pour du parallélisme de thread, fait partie des pratiques de développement d’applications pour supercalculateurs. Des erreurs, liées à l’utilisation conjointe de ces langages de parallélisme, sont actuellement difficiles à détecter et cela limite l’écriture de codes, permettant des interactions plus poussées entre ces niveaux de parallélisme. Des outils ont été proposés afin de palier ce problème. Cependant, ces outils sont généralement focalisés sur un type de modèle et permettent une vérification dite statique (à la compilation) ou dynamique (à l’exécution). Pourtant une combinaison statique/- dynamique donnerait des informations plus pertinentes. En effet, le compilateur est en mesure de donner des informations relatives au comportement général du code, indépendamment du jeu d’entrée. C’est par exemple le cas des problèmes liés aux communications collectives du modèle MPI. Cette thèse a pour objectif de développer des analyses statiques/dynamiques permettant la vérification d’une application parallèle mélangeant plusieurs modèles de programmation, afin de diriger les développeurs vers un code parallèle multi-modèles correct et performant. La vérification se fait en deux étapes. Premièrement, de potentielles erreurs sont détectées lors de la phase de compilation. Ensuite, un test au runtime est ajouté pour savoir si le problème va réellement se produire. Grâce à ces analyses combinées, nous renvoyons des messages précis aux utilisateurs et évitons les situations de blocage.Supercomputing plays an important role in several innovative fields, speeding up prototyping or validating scientific theories. However, supercomputers are evolving rapidly with now millions of processing units, posing the questions of their programmability. Despite the emergence of more widespread and functional parallel programming models, developing correct and effective parallel applications still remains a complex task. Although debugging solutions have emerged to address this issue, they often come with restrictions. However programming model evolutions stress the requirement for a convenient validation tool able to handle hybrid applications. Indeed as current scientific applications mainly rely on the Message Passing Interface (MPI) parallel programming model, new hardwares designed for Exascale with higher node-level parallelism clearly advocate for an MPI+X solutions with X a thread-based model such as OpenMP. But integrating two different programming models inside the same application can be error-prone leading to complex bugs - mostly detected unfortunately at runtime. In an MPI+X program not only the correctness of MPI should be ensured but also its interactions with the multi-threaded model, for example identical MPI collective operations cannot be performed by multiple nonsynchronized threads. This thesis aims at developing a combination of static and dynamic analysis to enable an early verification of hybrid HPC applications. The first pass statically verifies the thread level required by an MPI+OpenMP application and outlines execution paths leading to potential deadlocks. Thanks to this analysis, the code is selectively instrumented, displaying an error and synchronously interrupting all processes if the actual scheduling leads to a deadlock situation
- …
