No description available.

Heterogeneity is increasing across all levels of computing, with the rise of accelerators such as GPUs, FPGAs, and other coprocessors into everything from cell phones to supercomputers. More quietly it is increasing with the rise of NUMA systems, hierarchical caching, OS noise, and a myriad of other factors. As heterogeneity becomes a fact of life, efficiently managing heterogeneous compute resources is becoming a critical, and ever more complex, task. The focus of this dissertation is to lay the foundation for an autonomic system for heterogeneous computing, employing runtime adaptation to improve performance portability and performance consistency while maintaining or increasing programmability. We investigate heterogeneity arising from a myriad of factors, grouped into the dimensions of locality and capability. This work has resulted in runtime schedulers capable of automatically detecting and mitigating heterogeneity in physically homogeneous systems through MPI and adaptive coscheduling for physically heterogeneous accelerator based systems as well as a synthesis of the two to address multiple levels of heterogeneity as a coherent whole. We also discuss our current work towards the next generation of fine-grained scheduling and synchronization across heterogeneous platforms in the design of a highly-scalable and portable concurrent queue for many-core systems. Each component addresses aspects of the urgent need for automated management of the extreme and ever expanding complexity introduced by heterogeneity. / Ph. D.

L'évolution du calcul haute performance est aujourd'hui dirigée par les besoins des applications de simulation numérique.Ces applications sont exécutées sur des supercalculateurs qui peuvent proposer plusieurs milliers de cœurs, et qui sont découpés en un très grand nombre de nœuds de calcul ayant eux un nombre de cœurs beaucoup plus faible.Chacun de ces nœuds de calcul repose sur une architecture à mémoire partagée, dont la mémoire est découpée en plusieurs blocs physiques différents : cela implique un temps d'accès dépendant à la fois de la donnée accédée ainsi que du processeur y accédant.On appelle ce genre d'architectures NUMA (pour emph{Non Uniform Memory Access}).La manière actuelle de les exploiter tend vers l'utilisation d'un modèle de programmation à base de tâches, qui permet de traiter des programmes irréguliers au delà du simple parallélisme de boucle.L'exploitation efficace des machines NUMA est critique pour l'amélioration globale des performances des supercalculateurs.Cette thèse a été axée sur l'amélioration des techniques usuelles pour leur exploitation : elle propose une réponse au compromis qu'il faut faire entre localité des données et équilibrage de charge, qui sont deux points critiques dans l'ordonnancement d'applications.Les contributions de cette thèse peuvent se découper en deux parties : une partie dédiée à fournir au programmeur les moyens de comprendre, analyser, et mieux spécifier le comportement des parties critiques de son application, et une autre partie dédiée à différentes améliorations du support exécutif.Cette seconde partie a été évaluée sur différentes applications, ce qui a permis de montrer des gains de performances significatifs. / Nowadays the evolution of High Performance Computing follows the needs of numerical simulations.These applications are executed on supercomputers which can offer several thousands of cores, split into a large number of computing nodes, which possess a relatively low number of cores.Each of these nodes consists of a shared memory architecture, in which the memory is physically split into several distinct blocks: this implies that the memory access time depends both on which data is accessed, and on which core tries to access it.These architectures are named NUMA (for Non Uniform Memory Access).The current way to exploit them tends to be through a tasks-based programming model, which can handle irregular applications beyond a simple loop-based parallelism.Efficient use of NUMA architectures is critical for the overall performance improvements of supercomputers.This thesis has been targetted at improving common techniques for their exploitation: it proposes an answer to the tradeoff that has to be made between data locality and load balancing, that are two critical aspects of applications scheduling.Contributions of this thesis can be split into two parts: the first part is dedicated to providing the programmer with means to understand, analyze, and better characterize the behavior of their applications' critical parts, and the second part is dedicated to several improvements made to the runtime systems.This last part has been evaluated on various applications, and has shown some significant performance gains.

Η εργασία αυτή ασχολείται με την υλοποίηση ενός μεταφραστή για το μοντέλο παράλληλου προγραμματισμού OpenMP. Το μοντέλο αυτό χρησιμοποιείται για την υλοποίηση παράλληλων εφαρμογών για την αρχιτεκτονική κοινής μνήμης, και δίνει έμφαση στην ευκολία του προγραμματισμού και την μεταφερσιμότητα των παράλληλων εφαρμογών που αναπτύσσονται μ’ αυτό. Στην εργασία αυτή παρουσιάζεται η σχεδίαση και η υλοποίηση ενός μεταγλωττιστή παράλληλων εφαρμογών OpenMP για τη γλώσσα προγραμματισμού C σύμφωνα με την έκδοση 2.0 του προτύπου OpenMP. Ο μεταγλωττιστής που υλοποιήθηκε ανήκει στην κατηγορία των μεταφραστών, δηλαδή μεταφράζει τον πηγαίο κώδικα σε γλώσσα προγραμματισμού C με τις επεκτάσεις OpenMP, σε ισοδύναμο πηγαίο κώδικα σε γλώσσα προγραμματισμού C, στον οποίο οι επεκτάσεις OpenMP έχουν αντικατασταθεί από ισοδύναμα τμήματα κώδικα τα οποία χρησιμοποιούν κλήσεις βιβλιοθήκης νημάτων για την υλοποίηση του παραλληλισμού. Ο μεταφραστής έχει σχεδιαστεί με τέτοιο τρόπο ώστε να είναι μεταφέρσιμος, υποστηρίζοντας πολλαπλές πλατφόρμες εκτέλεσης, και επεκτάσιμος, υποστηρίζοντας πολλαπλές βιβλιοθήκες νημάτων κατά τη μετάφραση των οδηγιών OpenMP. Η υλοποίηση του μεταφραστή έγινε στη γλώσσα προγραμματισμού Java, χρησιμοποιώντας το γλωσσικό εργαλείο ANTLR για την υλοποίηση του λεκτικού και συντακτικού αναλυτή. Ο μεταφραστής συνοδεύεται, επίσης, από μια βιβλιοθήκη χρόνου εκτέλεσης, η οποία περιέχει τις συναρτήσεις που ορίζονται από το πρότυπο OpenMP v2.0, καθώς και άλλες συναρτήσεις που είναι απαραίτητες για την εκτέλεση των μεταφρασμένων παράλληλων εφαρμογών. Επίσης, στη βιβλιοθήκη υλοποιούνται οι πολιτικές χρονοδρομολόγησης, επιτρέπωντας εύκολα την υλοποίηση κάποιας νέας πολιτικής. Η βιβλιοθήκη έχει υλοποιηθεί σε γλώσσα προγραμματισμού C. Στα πλαίσια της εργασίας αυτής, έχει υλοποιηθεί η υποστήριξη των βιβλιοθηκών νημάτων POSIX και NANOS σε πολυεπεξεργαστικά συστήματα κοινής μνήμης, καθώς και οι πολιτικές χρονοδρομολόγησης που ορίζονται στο πρότυπο OpenMP v2.0. / The subject of this thesis is the implementation of a translator for the OpenMP parallel programming model. This model is used for the development of parallel applications for the shared memory model and emphasizes on the ease of programming and the portability of the applications developed with it. This thesis describes the design and the implementatino of a compiler for OpenMP parallel applications for the C programming language according to version 2.0 of the OpenMP model. The compiler that has been implemented belongs to the translator class, that is translates the source code in C programming language with the OpenMP extensions to equivalent source code in C programming language where the OpenMP extensions have been replaced with equivalent code segments which use thread library calls to implement the parallelism. The translator has been designed in order to be portable, supporting multiple execution platforms, and extensible, supporting multiple thread libraries during the translation of the OpenMP directives. The translator has been implemented using the Java language and using the language tool ANTLR for the implementation of the lexer and the parser. The translator comes with a run-time library, which contains all of the functions which are defined by the OpenMP v2.0, as well as other functions which are needed for the execution of the translated parallel applications. Also, the library contains the scheduling policies allowing easy implementation of a new one. The library has been implemented using the C language. The current implementation supports the POSIX and NANOS thread libraries in shared memory SMPs, as well as all the scheduling policies defined in OpenMP v2.0

Baigiamajame magistro darbe nagrinėjamos OpenMP, UPC, MPI ir BSP lygiagrečiojo programavimo technologijos sprendžiant dvimatį šilumos laidumo uždavinį lygiagrečiuoju Jakobio iteraciniu metodu. Kiekvienai technologijai sudaromi lygiagretieji algoritmai, aptariamas jų realizacijos sudėtingumas programuotojo požiūriu ir efektyvumas skirtingose kompiuterių architektūrose. Dabą sudaro 6 dalys: įvadas, technologijų apžvalga, šilumos laidumo uždavinys, programų realizacija, rezultatų palyginimas, išvados, literatūra. Darbo apimtis – 38 p. teksto be priedų, 9 paveikslėliai, 3 lentelės, 10 bibliografinių šaltinių. / In this thesis, we consider OpenMP, UPC, MPI and BSP parallel programming technologies - solving two dimensional heat equation, using parallel Jacobi iterative method. Parallel algorithms are constructed and implemented for each technology. Their effectiveness in different computer architectures is discussed as well as the complexity of different implementations from programmer’s point of view. Thesis consists of 6 parts: introduction, technology overview, heat conduction problem, program implementations, comparison of the results, conclusions and references. Thesis consist of: 38 p. text without appendixes, 9 pictures, 3 tables, 10 bibliographical entries.

Made available in DSpace on 2014-12-17T14:56:07Z (GMT). No. of bitstreams: 1 FranciscoAAS_DISSERT.pdf: 1526658 bytes, checksum: 7ba5b80f03a10eaf25a4f9e6a4c91372 (MD5) Previous issue date: 2012-08-07 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Artificial neural networks are usually applied to solve complex problems. In problems with more complexity, by increasing the number of layers and neurons, it is possible to achieve greater functional efficiency. Nevertheless, this leads to a greater computational effort. The response time is an important factor in the decision to use neural networks in some systems. Many argue that the computational cost is higher in the training period. However, this phase is held only once. Once the network trained, it is necessary to use the existing computational resources efficiently. In the multicore era, the problem boils down to efficient use of all available processing cores. However, it is necessary to consider the overhead of parallel computing. In this sense, this paper proposes a modular structure that proved to be more suitable for parallel implementations. It is proposed to parallelize the feedforward process of an RNA-type MLP, implemented with OpenMP on a shared memory computer architecture. The research consistes on testing and analizing execution times. Speedup, efficiency and parallel scalability are analyzed. In the proposed approach, by reducing the number of connections between remote neurons, the response time of the network decreases and, consequently, so does the total execution time. The time required for communication and synchronization is directly linked to the number of remote neurons in the network, and so it is necessary to investigate which one is the best distribution of remote connections / As redes neurais artificiais geralmente s?o aplicadas ? solu??o de problemas comple- xos. Em problemas com maior complexidade, ao aumentar o n?mero de camadas e de neur?nios, ? poss?vel conseguir uma maior efici?ncia funcional, por?m, isto acarreta em um maior esfor?o computacional. O tempo de resposta ? um fator importante na decis?o de us?-las em determinados sistemas. Muitos defendem que o maior custo computacional est? na fase de treinamento. Por?m, esta fase ? realizada apenas uma ?nica vez. J? trei- nada, ? necess?rio usar os recursos computacionais existentes de forma eficiente. Diante da era multicore esse problema se resume ? utiliza??o eficiente de todos os n?cleos de processamento dispon?veis. No entanto, ? necess?rio considerar a sobrecarga existente na computa??o paralela. Neste sentido, este trabalho prop?e uma estrutura modular que ? mais adequada para as implementa??es paralelas. Prop?e-se paralelizar o processo feed- forward (passo para frente) de uma RNA do tipo MLP, implementada com o OpenMP em uma arquitetura computacional de mem?ria compartilhada. A investiga??o dar-se-? com a realiza??o de testes e an?lises dos tempos de execu??o. A acelera??o, a efici?ncia e a es- calabilidade s?o analisados. Na proposta apresentada ? poss?vel perceber que, ao diminuir o n?mero de conex?es entre os neur?nios remotos, o tempo de resposta da rede diminui e por consequ?ncia diminui tamb?m o tempo total de execu??o. O tempo necess?rio para comunica??o e sincronismo est? diretamente ligado ao n?mero de neur?nios remotos da rede, sendo ent?o, necess?rio observar sua melhor distribui??o

L’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.

Afin de répondre aux besoins croissants de la simulation numérique et de rester à la pointe de la technologie, les supercalculateurs doivent d’être constamment améliorés. Ces améliorations peuvent être d’ordre matériel ou logiciel. Cela force les applications à s’adapter à un nouvel environnement de programmation au fil de son développement. Il devient alors nécessaire de se poser la question de la pérennité des applications et de leur portabilité d’une machine à une autre. L’utilisation de machines virtuelles peut être une première réponse à ce besoin de pérennisation en stabilisant les environnements de programmation. Grâce à la virtualisation, une application peut être développée au sein d’un environnement figé, sans être directement impactée par l’environnement présent sur une machine physique. Pour autant, l’abstraction supplémentaire induite par les machines virtuelles entraine en pratique une perte de performance. Nous proposons dans cette thèse un ensemble d’outils et de techniques afin de permettre l’utilisation de machines virtuelles en contexte HPC. Tout d’abord nous montrons qu’il est possible d’optimiser le fonctionnement d’un hyperviseur afin de répondre le plus fidèlement aux contraintes du HPC que sont : le placement des fils d’exécution et la localité mémoire des données. Puis en s’appuyant sur ce résultat, nous avons proposé un service de partitionnement des ressources d’un noeud de calcul par le biais des machines virtuelles. Enfin, pour étendre nos travaux à une utilisation pour des applications MPI, nous avons étudié les solutions et performances réseau d’une machine virtuelle. / To meet the growing needs of the digital simulation and remain at the forefront of technology, supercomputers must be constantly improved. These improvements can be hardware or software order. This forces the application to adapt to a new programming environment throughout its development. It then becomes necessary to raise the question of the sustainability of applications and portability from one machine to another. The use of virtual machines may be a first response to this need for sustaining stabilizing programming environments. With virtualization, applications can be developed in a fixed environment, without being directly impacted by the current environment on a physical machine. However, the additional abstraction induced by virtual machines in practice leads to a loss of performance. We propose in this thesis a set of tools and techniques to enable the use of virtual machines in HPC context. First we show that it is possible to optimize the operation of a hypervisor to respond accurately to the constraints of HPC that are : the placement of implementing son and memory data locality. Then, based on this, we have proposed a resource partitioning service from a compute node through virtual machines. Finally, to expand our work to use for MPI applications, we studied the network solutions and performance of a virtual machine.

Afin de répondre aux besoins de plus en plus importants en puissance de calcul de la part des applicationsnumériques, les supercalculateurs ont dû évoluer et sont ainsi de plus en plus compliqués àprogrammer. Ainsi, en plus de l’apparition des systèmes à mémoire partagée, des architectures ditesNUMA (Non Uniform Memory Access) sont présentes au sein de ces machines, fournissant plusieursniveaux de parallélisme. Une autre contrainte, la diminution de la mémoire disponible par coeur decalcul, doit être soulignée. C’est ainsi que des modèles parallèles tels que MPI (Message Passing Interface)ne permettent plus aux codes scientifiques haute performance de passer à l’echelle et d’exploiterefficacement les machines de calcul, et doivent donc être combinés avec d’autres modèles plus adaptésaux architectures à mémoire partagée. OpenMP, en tant que modèle standardisé, est un choix privilégiépour être combiné avec MPI. Mais mélanger deux modèles avec des paradigmes différents est unet âche compliquée et peut engendrer des goulets d’étranglement qui doivent être identifiés. Cette thèsea pour objectif d’aborder ces limitations et met en avant plusieurs contributions couvrant divers aspects.Notre première contribution permet de r éduire le surcoût des supports exécutifs OpenMP en optimisantle travail d’activation et de synchronisation des threads OpenMP pour les codes MPI+OpenMP. Dansun second temps, nous nous focalisons sur les opérations collectives MPI. Notre contribution a pourbut d’optimiser l’opération MPI Allreduce en réutilisant des unités de calcul inoccupées, et faisant intervenirdes threads OpenMP. Nous introduisons également le concept de collectives unifiées, impliquantdes tâches MPI et des threads OpenMP dans une même opération. Enfin, nous nous intéressons àl’analyse de performance et plus précisément l’instrumentation des applications MPI+OpenMP, et notredernière contribution consiste en l’implémentation et l’ évaluation de l’outil OpenMP Tools API (OMPT)dans le support exécutif OpenMP du framework MPC. Cet outil nous permet d’instrumenter des constructionsOpenMP et de conduire une analyse axée aussi bien du côté des applications que dessupports d’exécution / To provide increasing computational power for numerical simulations, supercomputers evolved and arenow more and more complex to program. Indeed, after the appearance of shared memory systemsemerged architectures such as NUMA (Non Uniform Memory Access) systems, providing several levelsof parallelism. Another constraint, the decreasing amount of memory per compute core, has to bementioned. Therefore, parallel models such as Message Passing Interface (MPI) are no more sufficientto enable scalability of High Performance applications, and have to be coupled with another modeladapted to shared memory architectures. OpenMP, as a de facto standard, is a good candidate to bemixed with MPI. The principle is to use this model to augment legacy codes already parallelized withMPI. But hybridizing scientific codes is a complex task, bottlenecks exist and need to be identified. Thisthesis tackles these limitations and proposes different contributions following various aspects. Our firstcontribution reduces the overhead of the OpenMP layer by optimizing the creation and synchronizationof threads for MPI+OpenMP codes. On a second time, we target MPI collective operations. Our contributionconsists in proposing a technique to exploit idle cores in order to help the operation, with theexample of MPI Allreduce collective. We also introduce unified Collectives involving both MPI tasks andOpenMP threads. Finally, we focus on performance analysis of hybrid MPI+OpenMP codes, and ourlast contribution consists in the implementation of OpenMP Tools API (OMPT), an instrumentation tool,inside the OpenMP runtime of MPC framework. This tool allows us to instrument and profile OpenMPconstructs and allows the analysis of both runtime and application sides

Les processeurs graphiques (GPU), originellement dédiés à l'accélération de traitements graphiques, ont une structure hautement parallèle. Les innovations matérielles et de langage de programmation ont permis d'ouvrir le domaine du GPGPU, où les cartes graphiques sont utilisées comme des accélérateurs de calcul pour des applications HPC généralistes.L'objectif de nos travaux est de faciliter l'utilisation de ces nouvelles architectures pour les besoins du calcul haute performance ; ils suivent deux objectifs complémentaires.Le premier axe de nos recherches concerne la transformation automatique de code, permettant de partir d'un code de haut niveau pour le transformer en un code de bas niveau, équivalent, pouvant être exécuté sur des accélérateurs. Dans ce but nous avons implémenté un transformateur de code capable de prendre en charge les boucles « pour » parallèles d'un code OpenMP (simples ou imbriquées) et de le transformer en un code CUDA équivalent, qui soit suffisamment lisible pour permettre de le retravailler par des optimisations ultérieures.Par ailleurs, le futur des architectures HPC réside dans les architectures distribuées basées sur des nœuds dotés d'accélérateurs. Pour permettre aux utilisateurs d'exploiter les nœuds multiGPU, il est nécessaire de mettre en place des schémas d'exécution appropriés. Nous avons mené une étude comparative et mis en évidence que les threads OpenMP permettent de gérer de manière efficace plusieurs cartes graphiques et les communications au sein d'un nœud de calcul multiGPU. / Graphic cards (GPUs), initially used for graphic processing, have a highly parallel architecture. Innovations in both architecture and programming languages opened the new domain of GPGPU where GPUs are used as accelerators for general purpose HPC applications.Our main objective is to facilitate the use of these new architectures for high-performance computing needs; our research follows two main directions.The first direction concerns an automatic code transformation from a high level code into an equivalent low level one, capable of running on accelerators. To this end we implemented a code transformer that can handle parallel “for” loops (single or nested) of an OpenMP code and convert it into an equivalent CUDA code, which is in a human readable form that allows for further optimizations.Moreover, the future of HPC lies in distributed architectures based on hybrid nodes. Specific programming schemes have to be used in order to allow users to benefit from such multiGPU nodes. We conducted a comparative study which revealed that using OpenMP threads is the most adequate way to control multiple graphic cards as well as manage communications efficiently within a multiGPU node.