This thesis introduces the Progressive Messages model of communication. It is an event-driven framework for building scalable parallel and distributed computing applications on modern networks. In particular, the paradigm provides notification of message termination. That is, when a message succeeds or fails, the user’s application can capture an event (often through a callback) and perform a designated action. The semantics of the Progressive Messages model are defined as an extension to the message-driven model, which is like an asynchronous RPC. Together, these models can be contrasted to the message-passing model (the basis of Sockets and MPI), which has no event notification. Using Progressive Messages allows for a more scalable design than permitted by either the message-passing or message-driven model. In particular, Progressive Messages can handle communication concurrently with computation, which means that one process does not need to wait in order to service a request or response from another process. This overlap leads to more efficiency. As part of the study of Progressive Messages, we create the MATE (Message Alerts Through Events) library, which is a prototype API that supports event notification in communication. This API was implemented in both MPI and InfiniBand verbs (OpenFabrics). "Unit tests" of network metrics shows that there is some latency in event-driven message handling, though it is difficult to determine if the source of the latency is hardware or software based. The goal of the Progressive Messages model is that parallel and distributed computing applications will be easier to build and will be more scalable.

Dans le domaine des sciences et technologies, la simulation numérique est un élément-clé des processus de recherche ou de validation. Grâce aux moyens informatiques modernes, elle permet des expérimentations numériques rapides et moins coûteuses que des maquettes réelles, sans pour autant les remplacer totalement, mais permettant de réaliser des expérimentations mieux calibrées. Dans le domaine de la physique des réacteurs et plus précisément de la neutronique, le calcul de valeurs propres est la base de la résolution de l’équation du transport des neutrons. La complexité des problèmes à résoudre (dimension spatiale, énergétique, nombre de paramètres, …) est telle qu’une grande puissance de calcul peut être nécessaire. Les travaux de cette thèse concernent dans un premier temps l’évaluation des nouveaux matériels de calculs tels que les cartes graphiques ou les puces massivement multicoeurs, et leur application aux problèmes de valeurs propres pour la neutronique. Ensuite, dans le but d’utiliser le parallélisme massif des supercalculateurs, nous étudions également l’utilisation de méthodes hybrides asynchrones pour résoudre des problèmes à valeur propre avec ce très haut niveau de parallélisme. Nous expérimentons ensuite le résultat de ces recherches sur plusieurs supercalculateurs nationaux tels que la machine hybride Titane du Centre de Calcul, Recherche et Technologies (CCRT), la machine Curie du Très Grand Centre de Calcul (TGCC) qui est en cours d’installation, et la machine Hopper du Lawrence Berkeley National Laboratory (LBNL), mais également sur des stations de travail locales pour illustrer l’intérêt de ces recherches dans une utilisation quotidienne avec des moyens de calcul locaux. / In science, simulation is a key process for research or validation. Modern computer technology allows faster numerical experiments, which are cheaper than real models. In the field of neutron simulation, the calculation of eigenvalues is one of the key challenges. The complexity of these problems is such that a lot of computing power may be necessary. The work of this thesis is first the evaluation of new computing hardware such as graphics card or massively multicore chips, and their application to eigenvalue problems for neutron simulation. Then, in order to address the massive parallelism of supercomputers national, we also study the use of asynchronous hybrid methods for solving eigenvalue problems with this very high level of parallelism. Then we experiment the work of this research on several national supercomputers such as the Titane hybrid machine of the Computing Center, Research and Technology (CCRT), the Curie machine of the Very Large Computing Centre (TGCC), currently being installed, and the Hopper machine at the Lawrence Berkeley National Laboratory (LBNL). We also do our experiments on local workstations to illustrate the interest of this research in an everyday use with local computing resources.

Ce travail propose un modèle d'exécution pour les systèmes massivement parallèles qui vise à assurer le recouvrement des communications par les calculs. Le modèle d'exécution défini dans cette thèse est nommé SCAC: Synchronous Communication Asynchronous Computation. Ce modèle faiblement couplé, sépare l'exécution des phases de communication de celles de calculs afin de faciliter leur chevauchement pour recouvrir les délais de transfert de données. Pour permettre l'exécution simultanée de ces deux phases, nous proposons une approche basée sur trois niveaux: deux niveaux de contrôle hiérarchiques globalement centralisés/localement distribués et un niveau de calcul parallèle. Une implémentation générique et paramétrique du modèle SCAC a été réalisée afin de permettre la conception d'une architecture qui convient à l'application. Cette implémentation donne la possibilité au concepteur de choisir les composants de son système parmi un ensemble de composants préconçus, et d'en fixer les paramètres afin de construire la configuration SCAC adéquate à l'exécution de son application. Une estimation analytique est ensuite proposée pour évaluer les performances d'une application exécutée en mode SCAC. Cette estimation permet de prédire le temps d'exécution sans passer par l'implémentation physique afin de faciliter la conception du programme parallèle et la définition de la configuration de l'architecture SCAC. Le modèle SCAC a été validé par simulation, synthèse et implémentation sur une plateforme FPGA en traitant différents exemples d'applications de calcul parallèle. La comparaison des résultats obtenus par le modèle SCAC avec d'autres modèles a montré son efficacité en termes de flexibilité et d'accélération du temps d'exécution. / This work proposes an execution model for massively parallel systems aiming at ensuring the communications overlap by the computations. The execution model defined in this PhD thesis is named SCAC: Synchronous Communication Asynchronous Computation. This weakly coupled model separates the execution of communication phases from those of computation in order to facilitate their overlapping, thus covering the data transfer time. To allow the simultaneous execution of these two phases, we propose an approach based on three levels: two globally-centralized/locally-distributed hierarchical control levels and a parallel computation level. A generic and parametric implementation of the SCAC model was performed to fit different applications. This implementation allows the designer to choose the system components (from pre-designed ones) and to set its parameters in order to build the adequate SCAC configuration for the target application. An analytical estimation is proposed to evaluate the performance of an application running in SCAC mode. This estimation is used to predict the execution time without passing through the physical implementation in order to facilitate the parallel program design and the SCAC architecture configuration. The SCAC model was validated by simulation, synthesis and implementation on an FPGA platform, with different examples of parallel computing applications. The comparison of the results obtained by the SCAC model with other models has shown its effectiveness in terms of flexibility and execution time acceleration.

Les méthodes de Krylov sont fréquemment utilisés dans des problèmes linéaires, comme de résoudre des systèmes linéaires ou de trouver des valeurs propres et vecteurs propres de matrices, avec une taille extrêmement grande. Comme ces méthodes itératives nécessitent un calcul intensif, ils sont normalement déployés sur des grands clusters avec les mémoires distribués et les données communiqués par MPI. Lorsque la taille du problème augmente, la communication devient un bouchon principale d'atteindre une haute scalabité à cause de deux raisons: 1) La plupart des méthodes itératives comptent sur BLAS-2 matrices-vecteurs opérations de bas niveau qui sont communication intensive. 2) Le mouvement de données (accès à la mémoire, la communication par MPI) est beaucoup plus lent que la fréquence du processeur. Dans le cas des opérations de matrice creuse tels que la multiplication de matrices creuses et vecteurs (SpMV), le temps de communication devient dominant par rapport au temps de calcul. En outre, l'avènement des accélérateurs et coprocesseurs comme le GPU de NVIDIA fait le coût du calcul moins cher, tandis que le coût de la communication reste élevé dans des systèmes hétérogènes. Ainsi, la première partie de nos travaux se concentre sur l'optimisation des coûts de communication pour des méthodes itératives sur des clusters hétérogènes. En dehors du coût de communication, le mur de la puissance et de l’énergie devient un autre bouchon de scalabité pour le futur calcul exascale. Les recherches indiquent que la mise en œuvre des implémentations d'algorithmes qui sont informées pourrait efficacement réduire la dissipation de puissance des clusters. Nous explorons également la mise en œuvre des méthodes et des implémentations qui économisent l'énergie dans notre expérimentation. Enfin, l'optimisation de la communication et la mise en œuvre de l'efficacité énergétique seraient intégrés dans un schéma de méthode GMRES, qui exige un cadre d'auto-tuning pour optimiser sa performance. / Iterative methods are frequently used in extremely large scale linear problems, such solving linear systems or finding eigenvalue/eigenvectors of matrices. As these iterative methods require a substantial computational workload, they are normally deployed on large clusters of distributed memory architectures communicated via MPI. When the problem size scales up, the communication becomes a major bottleneck of reaching a higher scalability because of two reasons: 1) Many of the iterative methods rely on BLAS-2 low level matrix vector kernels that are communication intensive. 2) Data movement (memory access, MPI communication) is much slower than processor's speed. In case of sparse matrix operations such as Sparse Matrix Vector Multiplication (SpMV), the communication even replaces the computation as the dominant time cost. Furthermore, the advent of accelerators/coprocessors like Nvidia's GPU make computation cost more cheaper, while the communication cost remains high in such CPU-coprocessor heterogeneous systems. Thus, the first part of our work focus on the optimization of communication cost of iterative methods on heterogeneous clusters. Besides the communication cost, power wall becomes another bottleneck of future exascale computing in recent time. Researches indicate that a power-aware algorithmic implementation strategy could efficiently reduce the power dissipation of large clusters. We also explore the potential energy saving implementation of iterative methods in our experimentation. Finally, both the communication optimization and energy efficiency implementation would be integrated into a GMRES method, which demands an auto-tuning framework to maximize its performance.

Σκοπός της διπλωματικής εργασίας είναι η ανάπτυξη εργαλείου το οποίο θα δέχεται ως είσοδο C πρόγραμμα και θα βρίσκει όλη τη πληροφορία η οποία σχετίζεται με την επαναχρησιμοποίηση των δεδομένων. Τα δεδομένα αφορούν πίνακες μέσα σε βρόχους. Η επαναχρησιμοποίηση δεδομένων χωρίζεται σε τρεις κατηγορίες: α) Εύρεση της επαναχρησιμοποίησης για κάθε πίνακα ξεχωριστά. β) Εύρεση της επαναχρησιμοποίησης στοιχείων πίνακα που χρησιμοποιούνται σε διάφορες εκφράσεις. γ) Εύρεση χρήσης στοιχείων μεταξύ διαφορετικών πινάκων στην ίδια έκφραση. Η εύρεση των χαρακτηριστικών της επαναχρησιμοποίησης χρησιμεύει για την εύρεση αποδοτικού χρονοπρογραμματισμού (scheduling) του προγράμματος το οποίο θα έχει καλύτερη τοπικότητα (data locality). Η επαναχρησιμοποίηση δεδομένων εφαρμόζεται στο πρόβλημα πολλαπλασιασμού πίνακα επί διάνυσμα. Συμβατικές και μη τεχνικές υλοποίησης του προβλήματος έχουν συγκριθεί με τη προτεινόμενη. Η σύγκριση πραγματοποιήθηκε με τον εξομοιωτή SimpleScalar στον οποίο μπορούμε να τροποποιήσουμε την αρχιτεκτονική και σε υπολογιστή Desktop Pentium 4. / -

Cette thèse aborde les difficultés de mise au point de codes multicibles - c'est-à-dire de codes dont performances sont portables entre différentes cibles matérielles. Nous avons identifié deux principales difficultés à surmonter : l'unification de l'expression du parallélisme d'une part et la nécessité d'adapter le format de stockage des données d'autre part. Afin de mettre au point une version multicible de la bibliothèque d'algèbre linéaire Legolas++ mise au point à EDF R&D, nous avons conçu MTPS (MultiTarget Parallel Skeleton), une bibliothèque dédiée à la mise au point de codes multicible. MTPS permet d'obtenir une implémentation multicible pour les problèmes appliquant une même fonction aux différents éléments d'une collection. MTPS prend alors en charge l'adaptation du format de stockage des données en fonction de l'architecture ciblée. L'intégration des concepts de MTPS dans Legolas++ a conduit à l'obtention d'un prototype multicible de Legolas++. Ce prototype a permis de mettre au point des solveurs dont les performances sont proches de l'optimal sur différentes architectures matérielles / This thesis addresses the challenges of developing multitarget code - that is to say, codes whose performance is portable across different hardware targets. We identified two key challenges : the unification of the the parallelism expression and the need to adapt the format for storing data according to the target architecture. In order to develop a multitarget version of Legolas++, a linear algebra library developed at EDF R&D, we designed MTPS (Multi-Tatget Parallel Skeleton), a library dedicated to the development of multitarget codes. MTPS allows for multitarget implementations of problems that apply the same function to all the elements of a collection. MTPS then handles the adaptation of the format for storing data according to the targeted architecture. Integrating the concepts of MTPS in Legolas++ has led to the production of a multitarget prototype of Legolas++. This prototype has allowed the development of solvers whose performances near the harware limits on different hardware architectures

Σε αυτή την πτυχιακή εργασία γίνεται μελέτη του προβλήματος της ομαδοποίησης δεδομένων και πιο συγκεκριμένα οnline ομαδοποίηση σε ροές δεδομένων. Στην αρχή παρουσιάζεται η απλή offline εκδοχή του προβλήματος, όπου όλα τα δεδομένα προς ομαδοποίηση είναι γνωστά εκ των προτέρων. Παρουσιάζονται οι πιο βασικοί αλγόριθμοι και στοιχειώδεις εφαρμογές που καταδεικνύουν ότι η εύρεση αποδοτικών αλγορίθμων μπορεί να δώσει ώθηση σε νέα περιβάλλοντα που η ομαδοποίηση αποτελεί υπολογιστικό πυρήνα. Στη συνέχεια γίνεται εισαγωγή στο μοντέλο ροών δεδομένων, όπου εκεί η γνώση του αλγορίθμου για τη φύση των δεδομένων αποκτάται σταδιακά, όσο παρουσιάζονται νέα στοιχεία. Ο περιορισμός της διαθέσιμης μνήμης και η ανάγκη μας για αποδοτικούς αλγορίθμους μας οδηγεί σε κατασκευή προσεγγιστικών ευρετικών. Παρουσιάζονται ανοιχτά προβλήματα που έχουν τεθεί στη βιβλιογραφία καθώς και διάφορες εφαρμογές που προκύπτουν από δεδομένα που σχηματίζουν ροές. Συνεχίζοντας γίνεται μια εκτενής μελέτη της σύγχρονης βιβλιογραφίας και παρουσιάζονται οι πιο αντιπροσωπευτικοί αλγόριθμοι από κάθε βασική τεχνική προσέγγισης, όπως η ομαδοποίηση με βάση την πυκνότητα, ομαδοποίηση με γραμμική παλινδρόμηση, ομαδοποίηση δύο σταδίων κα. Παρουσιάζεται επίσης και ένας νέος αλγόριθμος που συνδυάζει προεπεξεργασία των δεδομένων της ροής με έναν online αλγόριθμο ομαδοποίησης και παραγωγή της τελικής ομαδοποίησης με μία παραλλαγή του LocalSearch. Τέλος ακολουθούν διάφορα πειραματικά αποτελέσματα που πραγματοποιήθηκαν επί αυτών των αντιπροσωπευτικών αλγορίθμων και γίνεται σύγκριση μεταξύ τους. Παρατηρούμε ότι τα νέα σχήματα που που προκύπτουν με βάση τον αλγόριθμο Localsearch πετυχαίνουν πολύ καλύτερα τελικά αποτελέσματα σε σχέση με τον αλγόριθμο Birch. / -

Η κρυφή μνήμη αποτελεί έναν σημαντικό παράγοντα για την απόδοση του επεξεργαστή. Ταυτόχρονα όμως αποτελεί και ένα από τα δομικά μέρη πάνω στο chip στο οποίο καταναλώνεται σημαντικό κομμάτι της ισχύος. Στην παρούσα εργασία γίνεται μία ανάλυση πάνω στην κατανάλωση των διαφόρων επιπέδων της ιεαραρχίας της κρυφής μνήμη του επεξεργαστή και παρουσιάζονται ορισμένες τεχνικές που οδηγούν στην μείωση της ενώ παράλληλα διατηρείται η απόδοση του υπολογιστικού συστήματος όσο το δυνατόν πιο σταθερή. Η αποτίμηση των τεχνικών αυτών έγινε με την βοήθεια του SimpleScalar, εξομοιωτή υπερβαθμωτών αρχιτεκτονικών επεξεργαστή, και του εργαλείου CACTI της HP, το οποίο μοντελοποιεί διάφορα χαρακτηριστικά (χρόνο προσπέλασης, δυναμική κατανάλωση ισχύος κτλ.) της κρυφής και κύριας μνήμης του επεξεργαστή. / Cache memory plays an important role in the performance of the processor. Simultaneously, however, it is one of the core components of the chip which consume a significant percentage of the total power. In this thesis we present an analysis of the power dissipation of the different levels in cache memory hierarchy and we propose techniques that lead to a reduction of power consumption while maintaning the system performance. For the efficiency study of these techniques we use SimpleScalar, a superscalar architecture simulator, and CACTI, an enhanced cache access and cycle time model.

La complexité et le nombre toujours plus grandissant des applications, notamment les standards vidéo, nécessite d’étudier des méthodes et outils pour leur déploiement sur des architectures elles aussi toujours plus complexes. En effet, afin d’atteindre les performances requises en matière de temps d’exécution ou consommation énergétique, les architectures modernes proposent des éléments de calculs hétérogènes, où chacun est spécialisé pour une fonction précise. Cette thèse s’appuie sur le modèle flot de données pour la spécification de l’application. Ce modèle permet d’exposer explicitement le parallélisme spatial et temporel de l’application à travers un réseau d’acteurs interconnectés par des canaux de type FIFO. Les acteurs, en charge du calcul, peuvent exhiber un comportement statique ou dynamique. Les derniers standards vidéo contraignent à s’appuyer sur les modèles dynamiques pour obtenir une spécification fonctionnelle. Les besoins de calcul sont alors dépendants des données à traiter. Le déploiement d’une application dynamique ne peut donc se faire à l’aide des approches statiques existantes dans la littérature. L’objectif de cette thèse est de proposer des algorithmes efficaces permettant de déployer à la volée une application flot de données dynamique sur une architecture multiprocesseurs hétérogène. La première contribution est un algorithme qui permet de trouver rapidement une solution de déploiement de l’application. La deuxième contribution est un algorithme basé sur les mouvements pour adapter en cours d’exécution le déploiement en réponse aux aspects dynamiques de l’application. / Modern multimedia applications are subject to an increasing complexity with widespread standards. This has led to the interest in dataflow approach that offers a powerful perspective on parallel com- putations at high level. In the meantime, the emergence of massively parallel architectures has revealed the trend towards heterogeneous Multi-Processor System-on-Chips (MPSoCs) to offer a better perfor- mance and energy tradeoff than their homogeneous counterparts. However, this also imposes challenges to the mapping of multimedia applications on such complex architectures. This thesis presents an adaptive methodology for mapping dataflow applications on heterogeneous MPSoCs. This thesis focuses on video decoders specified in RVC-CAL language, a dedicated dataflow language for video applications. Existing static approaches cannot capture all behaviors in dynamic dataflow applications. Thus, this requires to adapt the mapping according to the input data. The algorithm offers some adaptive parameters combined with our analyt- ical communication model to improve a performance while consider- ing load balancing. We evaluate our algorithms on a set of randomly generated benchmarks and real video decoders like MPEG4-SP and HEVC. Experimental results reveal that our mapping methodology is fast enough (in milliseconds) and the runtime remapping signifi- cantly improves the initial mapping. In the remapping process, we take the migration cost into account because the reconfiguration time also contributes to the overall performance.

In parallelen Anwendungen, die auf Grundlage des Programmiermodells der gemischten Parallelität implementiert wurden, lassen sich meist unabhängige Programmteile (Tasks) identifizieren, die sowohl parallel zueinander als auch selbst parallel ausgeführt werden können. Zur Reduzierung der Ausführungszeit solcher Anwendungen auf einem parallelen System wird eine zeitliche und räumliche Zuordnung dieser parallelen Tasks zu den Prozessoren benötigt, welche mithilfe von Schedulingverfahren ermittelt werden kann. Jedoch ist bereits das Scheduling voneinander abhängiger Single-Prozessor-Tasks auf ein paralleles System mit zwei Prozessoren NP-schwer, weshalb zur Lösung von Schedulingproblemen häufig List-Scheduling-Heuristiken verwendet werden. Das Scheduling unabhängiger paralleler Tasks ist aufgrund der vielen zusätzlichen Zuordnungsmöglichkeiten deutlich komplexer und erfordert daher dedizierte Lösungsverfahren. Einen vielversprechenden Ansatz zur Lösung komplexer Schedulingprobleme bilden suchbasierte Verfahren, die lokale oder globale Suchstrategien zur Lösungsfindung nutzen. In der vorliegenden Arbeit wird untersucht, inwieweit sich derartige Verfahren für das Scheduling unabhängiger paralleler Tasks auf heterogene Systeme bestehend aus Multicore- Rechnern mit unterschiedlichen Eigenschaften eignen. Zu diesem Zweck werden vier suchbasierte Schedulingverfahren entwickelt und untersucht. Konkret werden zwei modifizierende und zwei inkrementelle Verfahren vorgestellt, die von Suchverfahren wie der A*-Suche und Metaheuristiken wie der Tabu-Suche und des Simulated Annealing inspiriert sind. Zusätzlich wird eine Kostenmodellierung in Form von parametrisierten Laufzeitformeln präsentiert, mit der die Ausführungszeiten der parallelen Tasks auf heterogenen Systemen modelliert werden können. Die Verfahren werden in Laufzeitmessungen auf heterogenen Rechnerplattformen untereinander und mit existierenden List-Scheduling-Heuristiken verglichen. Als Anwendungen für die Messungen werden sowohl Programme der SPLASH-3-Benchmark-Suite als auch eine praxisnahe Simulationsanwendung zur Bauteilbelastung untersucht. Die Ergebnisse zeigen, dass alle vier Verfahren im Vergleich zu existierenden List-Scheduling-Heuristiken eine signifikante Reduktion der Ausführungszeit erreichen können.