Добірка наукової літератури з теми "Programmation parallèle et distribuée multi-Niveaux"

La réduction des temps de trajet et de la consommation d'énergie dans les réseaux routiers urbains est cruciale pour le bien-être collectif et la durabilité environnementale. Depuis les années 1950, la modélisation du trafic a été un axe central de la recherche. Avec l'évolution des capacités informatiques, des simulations sophistiquées représentant fidèlement les complexités du trafic routier ont émergé, essentielles pour évaluer les technologies sans perturber le trafic réel.Les systèmes de transport deviennent plus complexes avec des informations en temps réel, nécessitant des modèles de simulation adaptés. Les simulations multi-agents, analysant les comportements individuels dans un environnement dynamique, sont particulièrement efficaces pour cette tâche, permettant de comprendre et de gérer le trafic urbain en représentant les interactions entre les voyageurs et leur environnement.Simuler de grandes populations de voyageurs dans les villes a longtemps été une tâche exigeante en termes de ressources informatiques. Les technologies avancées permettant la distribution des calculs sur plusieurs ordinateurs ont ouvert de nouvelles possibilités. Cependant, de nombreux simulateurs de mobilité urbaine n'exploitent pas pleinement ces architectures distribuées, limitant leur capacité à modéliser des scénarios complexes.L'objectif principal de cette recherche est d'améliorer la performance algorithmique et computationnelle des simulateurs de mobilité. Nous développons et validons des modèles de distribution génériques et reproductibles pouvant être adoptés par divers simulateurs de mobilité multi-agents, surmontant ainsi les barrières techniques pour analyser les systèmes de transport complexes dans des environnements urbains dynamiques.Nous utilisons le simulateur de trafic MATSim, reconnu pour la simulation de trafic multi-agents, pour tester nos méthodes génériques. Notre première contribution applique l'approche "Unite and Conquer" (UC) à MATSim. Cette méthode accélère les simulations en exploitant les architectures informatiques modernes. L'approche multiMATSim réplique plusieurs instances de MATSim sur plusieurs nœuds de calcul avec des communications périodiques, chaque instance fonctionnant sur un nœud séparé, utilisant les capacités de multithreading de MATSim pour améliorer le parallélisme. La synchronisation périodique assure la cohérence des données, tandis que les mécanismes de tolérance aux pannes permettent à la simulation de se poursuivre même en cas d'échec de certaines instances. Cette approche optimise l'utilisation des ressources informatiques selon les capacités spécifiques de chaque nœud.La deuxième contribution explore les techniques d'intelligence artificielle pour accélérer la simulation. Nous utilisons des réseaux de neurones profonds pour prédire les résultats des simulations MATSim. Initialement mise en œuvre sur un seul nœud, cette approche de preuve de concept utilise efficacement les ressources CPU disponibles. Les réseaux de neurones sont entraînés sur des données de simulations précédentes pour prédire des indicateurs tels que les temps de trajet et les niveaux de congestion. Les résultats sont comparés à ceux de MATSim pour évaluer leur précision. Cette approche est conçue pour évoluer avec des plans futurs pour une formation distribuée sur plusieurs nœuds.En résumé, nos contributions fournissent de nouvelles variantes algorithmiques et explorent l'intégration du calcul haute performance et de l'IA dans les simulateurs de trafic multi-agents. Nous démontrons l'impact de ces modèles et technologies sur la simulation de trafic, en abordant les défis et les limites de leur mise en œuvre. Notre travail met en évidence les avantages des architectures émergentes et des nouveaux concepts algorithmiques pour améliorer la robustesse et la performance des simulateurs de trafic, avec des résultats prometteurs
The need to reduce travel times and energy consumption in urban road networks is critical for improving collective well-being and environmental sustainability. Since the 1950s, traffic modeling has been a central research focus. With the rapid evolution of computing capabilities in the 21st century, sophisticated digital simulations have emerged, accurately depicting road traffic complexities. Mobility simulations are essential for assessing emerging technologies like cooperative systems and dynamic GPS navigation without disrupting real traffic.As transport systems become more complex with real-time information, simulation models must adapt. Multi-agent simulations, which analyze individual behaviors within a dynamic environment, are particularly suited for this task. These simulations help understand and manage urban traffic by representing interactions between travelers and their environment.Simulating large populations of travelers in cities, potentially millions of individuals, has historically been computationally demanding. Advanced computer technologies allowing distributed calculations across multiple computers have opened new possibilities. However, many urban mobility simulators do not fully exploit these distributed architectures, limiting their ability to model complex scenarios involving many travelers and extensive networks.The main objective of this research is to improve the algorithmic and computational performance of mobility simulators. We aim to develop and validate generic and reproducible distribution models that can be adopted by various multi-agent mobility simulators. This approach seeks to overcome technical barriers and provide a solid foundation for analyzing complex transport systems in dynamic urban environments.Our research leverages the MATSim traffic simulator due to its flexibility and open structure. MATSim is widely recognized in the literature for multi-agent traffic simulation, making it an ideal candidate to test our generic methods.Our first contribution applies the "Unite and Conquer" (UC) approach to MATSim. This method accelerates simulation speed by leveraging modern computing architectures. The multiMATSim approach involves replicating several MATSim instances across multiple computing nodes with periodic communications. Each instance runs on a separate node, utilizing MATSim's native multithreading capabilities to enhance parallelism. Periodic synchronization ensures data consistency, while fault tolerance mechanisms allow the simulation to continue smoothly even if some instances fail. This approach efficiently uses diverse computational resources based on each node's specific capabilities.The second contribution explores artificial intelligence techniques to expedite the simulation process. Specifically, we use deep neural networks to predict MATSim simulation outcomes. Initially implemented on a single node, this proof-of-concept approach efficiently uses available CPU resources. Neural networks are trained on data from previous simulations to predict key metrics like travel times and congestion levels. The outputs are compared to MATSim results to assess accuracy. This approach is designed to scale, with future plans for distributed neural network training across multiple nodes.In summary, our contributions provide new algorithmic variants and explore integrating high-performance computing and AI into multi-agent traffic simulators. We aim to demonstrate the impact of these models and technologies on traffic simulation, addressing the challenges and limitations of their implementation. Our work highlights the benefits of emerging architectures and new algorithmic concepts for enhancing the robustness and performance of traffic simulators, presenting promising results

Les architectures parallèles sont de plus en plus présentes dans notre environnement, que ce soit dans les ordinateurs personnels disposant des dizaines d’unités de calculs jusqu’aux super-calculateurs comptant des millions d’unités. Les architectures haute performance modernes sont généralement constituées de grappes de multiprocesseurs, elles même constituées de multi-cœurs, et sont qualifiées d’architecture hiérarchiques. La conception de langages pour de telles architectures est un sujet de recherche actif car il s’agit de simplifier la programmation tout en garantissant l’efficacité des programmes. En effet, écrire des programmes parallèles est, en général, plus complexe tant au point de vue algorithmique qu’au niveau de l’implémentation. Afin de répondre à cette problématique, plusieurs modèles structurés ont été proposés. Le modèle logico-materiel BSP définit une vision structurée pour les architectures parallèles dites plates. Afin d’exploiter les architectures actuelles, une extension adaptée aux architectures hiérarchiques a été proposée : Multi-BSP. Tout en préservant la philosophie BSP, ce modèle garanti efficacité, sécurité d’exécution, passage à l’échelle et prédiction de coût.Cette thèse s’articule donc autour de cette idée et propose de définir Multi-ML, un langage basé sur le modèle logico-materiel Multi-BSP, garantissant les propriétés énoncées ci-dessus. Afin de pouvoir garantir la sécurité d’exécution des programmes Multi-ML, nous proposons une sémantique formelle ainsi qu’un système de type afin d’accepter uniquement des programmes bien formés. De plus, nous proposons une machine abstraite permettant de décrire formellement l’évaluation d’un programme Multi-ML sur une machine Multi-BSP. Une implantation du langage, développé dans le cadre de cette thèse, permet de générer un code exécutable. Il est donc possible d’exécuter, efficacement, des algorithmes Multi-BSP écrits à l’aide de Multi-ML sur diverses machines hiérarchiques
From personal computers using an increasing number of cores, to supercomputers having millions of computing units, parallel architectures are the current standard. The high performance architectures are usually referenced to as hierarchical, as they are composed from clusters of multi-processors of multi-cores. Programming such architectures is known to be notoriously difficult. Writing parallel programs is, most of the time, difficult for both the algorithmic and the implementation phase. To answer those concerns, many structured models and languages were proposed in order to increase both expressiveness and efficiency. Among other models, Multi-BSP is a bridging model dedicated to hierarchical architecture that ensures efficiency, execution safety, scalability and cost prediction. It is an extension of the well known BSP model that handles flat architectures.In this thesis we introduce the Multi-ML language, which allows programming Multi-BSP algorithms “à la ML” and thus, guarantees the properties of the Multi-BSP model and the execution safety, thanks to a ML type system. To deal with the multi-level execution model of Multi-ML, we defined formal semantics which describe the valid evaluation of an expression. To ensure the execution safety of Multi-ML programs, we also propose a typing system that preserves replicated coherence. An abstract machine is defined to formally describe the evaluation of a Multi-ML program on a Multi-BSP architecture. An implementation of the language is available as a compilation toolchain. It is thus possible to generate an efficient parallel code from a program written in Multi-ML and execute it on any hierarchical machine

Cette these vise a la resolution performante de problemes non-lineaires d'advection-diffusion et de navier-stokes discretises par un nouveau schema volumes finis a l'ordre 4, cfv4, inspire du principe des methodes compactes. Son efficacite est demontree pour les methodes iteratives de type krylov avec des preconditionnements multi-domaines et multi-niveaux. Sur une equation de burgers visqueux 2d, un preconditionneur base sur un schema volumes finis d'ordre 2, accelere par une methode multigrille, donne de tres bons resultats en matiere de convergence, du rapport cout de calcul/precision et des performances paralleles sur machines a memoire distribuee (ibm sp2 et cray t3d/t3e). Le gain par rapport au solveur partitionne s'accentue encore pour des maillages plus fins puisque la convergence du solveur preconditionne ne depend plus du pas de discretisation. Dans les cas faiblement visqueux, elle ne depend quasiment plus du nombre de sous-domaines. On etend le schema cfv4 a la discretisation sur un maillage decale des equations de navier-stokes en regime incompressible et instationnaire. Le systeme couple en vitesse-pression est resolu par un solveur de krylov preconditionne par une methode multigrille avec pour lisseur un algorithme de gauss-seidel par blocs maille a maille sur le meme probleme discretise a l'ordre 2. Les gains en precision et en temps de calcul sont comparables a ceux observes pour le probleme de burgers. L'etude se termine sur la resolution du probleme de la cavite entrainee pour des nombres de reynolds allant jusqu'a 5000.

L'arrivée des supercalculateurs post-petascales and exascales offre la perspective d'accélérer la résolution des problèmes d'ingénierie et aux modélisations hautement complexes. Cependant, ces futurs systèmes posent des problèmes aux informaticiens pour construire de telles machines. De nombreux problèmes doivent être résolus comme la tolérance aux pannes, la consommation énergétique et la programmation de ces systèmes complexes composés de milliard de coeurs.Dans cette thèse, nous nous sommes concentrés sur l'aspect programmation et proposons un paradigme de programmation multi-niveaux composé de trois niveaux. Pour le bas niveau, un paradigme data parallèle est proposé pour programmer les processeurs à nombreux coeurs pour sa focalisation sur la distribution et le mouvement des données. Nous avons implémenté et évalué le produit matrice vecteur creux suivant différents formats de matrice creuse sur un GPU pour illustrer ce point. Pour le niveau intermédiaire, nous proposons un paradigme à passage de messages de manière à optimiser les communications inter-processeurs et inter-noeuds. Pour le haut niveau, un paradigme de description de graphe est proposé pour programmer et gérer le parallélisme entre les noeuds.Avec une méthode d'inversion matricielle dense développée en YML, nous soulignons l'intérêt des graphes pour la réduction du temps à la solution et pour le support des communications asynchrones de facon transparente. L'intérêt des graphes est également démontré pour les optimisations d'entrées/sorties et leur support dans un modèle de programmation. Nous concluons finalement en analysant une telle proposition de paradigme de programmation pour les machines exascale et présentons la direction des travaux futurs
The coming of post-petscale and exascale supercomputers offers the perspective to accelerate the solving of engineering problems and to highly complex modeling. However, these future systems challenge computer scientists to built such machines. Many issues must be faced such as fault-tolerance, energy consumption and the programming of these complex systems composed of billion cores.In this thesis, we have focused on the programming aspect and propose a multi-level programming paradigm composed of three levels. For the low level, a data parallel paradigm is proposed to program many-cores processors for its focus on data mapping and movements. We have implemented and evaluated the SpMV with various sparse matrix formats on GPU to illustrate this point. For the intermediate level, we propose a message passing paradigm in order to optimize inter-sockets and inter-nodes communications. For the high level, a graph description paradigm is proposed to program and manage the parallelism between nodes.With a dense matrix inversion method developed in YML, we underline the interest of graph for the Time-To-Solution reduction and for the support of asynchronous communications in a transparent way. The interest of graph is also demonstrated for I/O optimizations and for their direct support into the programming model. We finally conclude by analyzing a such proposition of programming paradigm for exascale machines and outlines the future work direction

L'utilisation massive des plateformes multi-cœurs et multi-processeurs a pour effet de favoriser la programmation parallèle à mémoire partagée. Néanmoins, exploiter efficacement et de manière correcte le parallélisme sur ces plateformes reste un problème de recherche ouvert. De plus, leur modèle d'exécution sous-jacent, et notamment les modèles de mémoire "relâchés", posent de nouveaux défis pour les outils d'analyse statiques et dynamiques. Dans cette thèse nous abordons deux aspects importants dans le cadre de la programmation sur plateformes multi-cœurs et multi-processeurs: l'optimisation de sections critiques implémentées selon l'approche pessimiste, et l'analyse dynamique de flots d'informations. Les sections critiques définissent un ensemble d'accès mémoire qui doivent être exécutées de façon atomique. Leur implémentation pessimiste repose sur l'acquisition et le relâchement de mécanismes de synchronisation, tels que les verrous, en début et en fin de sections critiques. Nous présentons un algorithme générique pour l'acquisition/relâchement des mécanismes de synchronisation, et nous définissons sur cet algorithme un ensemble de politiques particulier ayant pour objectif d'augmenter le parallélisme en réduisant le temps de possession des verrous par les différentes threads. Nous montrons alors la correction de ces politiques (respect de l'atomicité et absence de blocages), et nous validons expérimentalement leur intérêt. Le deuxième point abordé est l'analyse dynamique de flot d'information pour des exécutions parallèles. Dans ce type d'analyse, l'enjeu est de définir précisément l'ordre dans lequel les accès à des mémoires partagées peuvent avoir lieu à l'exécution. La plupart des travaux existant sur ce thème se basent sur une exécution sérialisée du programme cible. Ceci permet d'obtenir une sérialisation explicite des accès mémoire mais entraîne un surcoût en temps d'exécution et ignore l'effet des modèles mémoire relâchées. A contrario, la technique que nous proposons permet de prédire l'ensemble des sérialisations possibles vis-a-vis de ce modèle mémoire à partir d'une seule exécution parallèle ("runtime prediction"). Nous avons développé cette approche dans le cadre de l'analyse de teinte, qui est largement utilisée en détection de vulnérabilités. Pour améliorer la précision de cette analyse nous prenons également en compte la sémantique des primitives de synchronisation qui réduisent le nombre de sérialisations valides. Les travaux proposé ont été implémentés dans des outils prototype qui ont permit leur évaluation sur des exemples représentatifs.

Depuis le milieu des années 1990, les bibliothèques de transmission de messages sont les technologies les plus utilisées pour développer des applications parallèles et distribuées. Des modèles de programmation basés sur des tâches peuvent être utilisés, par exemple, pour éviter les communications collectives sur toutes les ressources comme les réductions, les diffusions ou les rassemblements en les transformant en multiples opérations avec des tâches. Ensuite, ces opérations peuvent être planifiées par l'ordonnanceur pour placer les données et les calculs de manière à optimiser et réduire les communications de données.L'objectif principal de cette thèse est d'étudier ce que doit être la programmation basée sur des tâches pour des applications scientifiques et de proposer une spécification de cette programmation distribuée et parallèle, en expérimentant avec plusieurs représentations simplifiées d'applications scientifiques importantes pour TOTAL, et de méthodes linéaire classique dense et creuses. Au cours de la thèse, plusieurs langages de programmation et paradigmes sont étudiés. Des méthodes linéaires denses pour résoudre des systèmes linéaires, des séquences de produit matrice vecteur creux et la migration sismique en profondeur pré-empilement de Kirchhoff sont étudiées et implémentées en tant qu'applications basées sur des tâches.Une taxonomie, basée sur plusieurs de ces langages et paradigmes est proposée. Des logiciels ont été développés en utilisant ces modèles de programmation pour chaque application simplifiée. À la suite de ces recherches, une méthodologie pour la programmation de tâches parallèles est proposée, optimisant les mouvements de données en général et, en particulier, pour des applications scientifiques ciblées
Since the middle of the 1990s, message passing libraries are the most used technology to implement parallel and distributed applications. However, they may not be a solution efficient enough on exascale machines since scalability issues will appear due to the increase in computing resources. Task-based programming models can be used, for example, to avoid collective communications along all the resources like reductions, broadcast or gather by transforming them into multiple operations on tasks. Then, these operations can be scheduled by the scheduler to place the data and computations in a way that optimize and reduce the data communications. The main objective of this thesis is to study what must be task-based programming for scientific applications and to propose a specification of such distributed and parallel programming, by experimenting for several simplified representations of important scientific applications for TOTAL, and classical dense and sparse linear methods.During the dissertation, several programming languages and paradigms are studied. Dense linear methods to solve linear systems, sequences of sparse matrix vector product and the Kirchhoff seismic pre-stack depth migration are studied and implemented as task-based applications. A taxonomy, based on several of these languages and paradigms is proposed.Software were developed using these programming models for each simplified application. As a result of these researches, a methodology for parallel task programming is proposed, optimizing data movements, in general, and for targeted scientific applications, in particular

Les méthodes itératives de Krylov sont utilisées sur les plate-formes de Calcul Haute Performance (CHP) pour résoudre les grands systèmes linéaires issus des domaines de la science et de l’ingénierie. Avec l’augmentation du nombre de cœurs et de l’hétérogénéité des superordinateurs, le temps consacré à la communication et synchronisation globales nuit gravement aux leurs performances parallèles. La programmation tend à être distribuée et parallèle. Le développement d’algorithmes devrait prendre en compte les principes: 1) parallélisme avec multi-granularité; 2) mémoire hiérarchique; 3) minimisation de la communication globale; 4) promotion de l’asynchronicité; 5) proposition de stratégies d’ordonnancement et de moteurs de gestion pour gérer les trafics et la tolérance aux pannes. En réponse à ces objectifs, nous présentons un paradigme de programmation multi-niveaux distribués et parallèles pour les méthodes de Krylov sur les plates-formes de CHP. La première partie porte sur la mise en œuvre d’un générateur de matrices avec des valeurs propres prescrites pour la référence des méthodes itératives. Dans la deuxième partie, nous étudions les performances numériques et parallèles de la méthode itérative proposée. Son implémentation avec un moteur de gestion peut gérer la communication, la tolérance aux pannes et la réutilisabilité. Dans la troisième partie, un schéma de réglage automatique est introduit pour la sélection intelligente de ses paramètres lors de l’exécution. Enfin, nous étudions la possibilité d’implémenter ce paradigme dans un environnement d’exécution de flux de travail
Krylov iterative methods are frequently used on High-Performance Computing (HPC) systems to solve the extremely large sparse linear systems and eigenvalue problems from science and engineering fields. With the increase of both number of computing units and the heterogeneity of supercomputers, time spent in the global communication and synchronization severely damage the parallel performance of iterative methods. Programming on supercomputers tends to become distributed and parallel. Algorithm development should consider the principles: 1) multi-granularity parallelism; 2) hierarchical memory; 3) minimization of global communication; 4) promotion of the asynchronicity; 5) proposition of multi-level scheduling strategies and manager engines to handle huge traffic and improve the fault tolerance. In response to these goals, we present a distributed and parallel multi-level programming paradigm for Krylov methods on HPC platforms. The first part of our work focuses on an implementation of a scalable matrix generator to create test matrices with customized eigenvalue for benchmarking iterative methods on supercomputers. In the second part, we aim to study the numerical and parallel performance of proposed distributed and parallel iterative method. Its implementation with a manager engine and runtime can handle the huge communication traffic, fault tolerance, and reusability. In the third part, an auto-tuning scheme is introduced for the smart selection of its parameters at runtime. Finally, we analyse the possibility to implement the distributed and parallel paradigm by a graph-based workflow runtime environment

L'accroissement régulier de la fréquence des micro-processeurs et des importants gains de puissance qui en avaient résulté ont pris fin en 2005. Les autres techniques matérielles d'amélioration de performance se sont largement essouflées. Les fabricants de micro-processeurs ont donc choisi d'exploiter le nombre croissant de transistors disponibles en plaçant plusieurs cœurs de processeurs sur une même puce. Dans cette thèse, nous préparons l'arrivée de processeurs multi-cœur à grand nombre de cœurs par des recherches dans trois directions. Premièrement, nous améliorons l'environnement de parallélisation CAPSULE (parallélisation conditionnelle) en lui adjoignant des primitives de synchronization de tâches robustes. Nous montrons les gains obtenus par rapport aux approches usuelles en terme de rapidité et de stabilité du temps d'exécution. Deuxièmement, nous adaptons CAPSULE à des machines à mémoire distribuée en présentant un modèle de données qui permet au système de déplacer automatiquement les données en fonction des accès effectués par les programmes. De nouveaux algorithmes répartis et locaux permettent de décider de la création effective des tâches et de leur répartition. Troisièmement, nous développons un nouveau simulateur d'évènements discrets, SiMany, qui peut prendre en charge des centaines à des milliers de cœurs. Il est plus de 100 fois plus rapide que les meilleurs simulateurs flexibles actuels. Après validation, nous montrons que SiMany permet l'exploration d'un plus large champ d'architectures ainsi que l'étude des grandes lignes du comportement des logiciels sur celles-ci.