Le modèle de programmation à base d'acteurs a été intensivement utilisé pour le développement de grandes applications et systèmes. On citera par exemple la fonction chat de Facebook ou bien encore WhatsApp. Ces systèmes peuvent avoir plusieurs milliers d'utilisateurs connectés simultanément avec des contraintes fortes de performance et d'interactivité. Ces systèmes s"appuient sur des infrastructures informatiques basées sur des processeurs multi-cœurs. Ces infrastructures disposent en général d'un espace mémoire partagé et hiérarchique NUMA (Non-Uniform Memory Access). Notre analyse de l'état de l'art montre que peu d'études ont été menées sur l'adéquation des environnements d'exécution à base d'acteurs avec des plates-formes à mémoire hiérarchique. Ces environnements d'exécution font en général l'hypothèse que l'espace de mémoire est complètement plat, ce qui pose ensuite de sérieux problèmes de performance. Dans cette thèse, nous étudions les défis posés par les plates-formes multi-cœurs à mémoire hiérarchiques pour des environnements à base d'acteurs. Nous étudions plus particulièrement les problèmes de gestion mémoire, d'ordonnancement et d'équilibrage de charge.Dans la première partie de la thèse, nous avons analysé et caractérisé les applications basées sur le modèle d'acteurs. Cela a permis de mettre en évidence le fait que les exécutions des applications et benchmarks faisaient ressortir des structures de communication particulières que les environnements d'exécution se doivent de prendre en compte pour optimiser les performances. La prise en compte du graphe de communication et la mise en œuvre ont été effectuées dans un environnement d'exécution réel, la machine virtuelle (VM) du langage de programmation Erlang. Le langage de programmation Erlang s'appuie sur le modèle d'acteurs avec une syntaxe claire et cohérente pour la gestion des acteurs. Les modifications que nous avons intégrées à la machine virtuelle Erlang permettent d'améliorer significativement les performances grâce à une meilleure prise en compte de l'affinité entre des acteurs qui interagissent beaucoup. L'ordonnancement et la régulation de charge de l'application sont également améliorées grâce à une meilleure connaissance de l'application et de la topologie de la plate-forme. Une des perspectives serait d'intégrer ces contributions à d'autres environnements d'exécution à base d'acteurs, comme par exemple ceux des Kilim et Akka. / The actor model is present in several mission-critical systems, such as those supporting WhatsApp and Facebook Chat. These systems serve thousands of clients simultaneously, therefore demanding substantial computing resources usually provided by multi-processor and multi-core platforms. Non-Uniform Memory Access (NUMA) architectures account for an important share of these platforms. Yet, research on the the suitability of the current actor runtime environments for these machines is very limited. Current runtime environments, in general, assume a flat memory space, thus not performing as well as they could. In this thesis we study the challenges hierarchical shared memory multi-core platforms present to actor runtime environments. In particular, we investigate aspects related to memory management, scheduling, and load-balancing.In this document, we analyze and characterize actor based applications to, in light of the above, propose improvements to actor runtime environments. This analysis highlighted the existence of peculiar communication structures. We argue that the comprehension of these structures and the knowledge about the underlying hardware architecture can be used in tandem to improve application performance. As a proof of concept, we implemented our proposal using a real actor runtime environment, the Erlang Virtual Machine (VM). Concurrency in Erlang is based on the actor model and the language has a consistent syntax for actor handling. Our modifications to the Erlang VM significantly improved the performance of some applications thanks to better informed decisions on scheduling and on load-balancing. As future work we envision the integration of our approach into other actor runtime environments such as Kilim and Akka.

Les techniques de programmations pour le calcul de haute performanceont adopté les modèles basés sur parallélisme de tâche qui sontcapables de s’adapter plus facilement à des superordinateurs avec desarchitectures hybrides. La performance des applications basées surtâches dépende fortement des heuristiques d'ordonnancement dynamiqueset de sa capacité à exploiter les ressources de calcul et decommunication.Malheureusement, les stratégies d'analyse de performancetraditionnelles ne sont pas convenables pour comprendre les supportsd'exécution dynamiques et les applications basées sur tâches. Cesstratégies prévoient un comportement régulier avec des phases decalcul et de communication, par contre, des applications basées surtâches ne manifestent pas de phases précises. Par ailleurs, la granularitéplus fine des applications basées sur tâches typiquement provoque descomportements stochastiques qui donnent lieu aux structuresirrégulières qui sont difficiles à analyser.Dans cette thèse, nous proposons des stratégies d'analyse deperformance qui exploitent la combinaison de la structure del'application, d'ordonnancement et des informations de laplate-forme. Nous présentons comment nos stratégies peuvent aider àcomprendre des problèmes de performance dans des applications baséesur tâches qui exécutent dans des plates-formes hybrides. Nosstratégies d'analyse de performance sont construites avec des outilsmodernes pour l'analyse de données, ce que permettre la création despanneaux de visualisation personnalisés. Ces panneaux permettent lacompréhension et l'identification de problèmes de performancesoccasionnés par de mauvaises décisions d'ordonnancement etconfiguration incorrect du support d'exécution et de laplate-forme. Grâce à combinaison de simulation et débogage nouspouvons aussi construire une représentation visuelle de l'état interneet des estimations calculées par l'ordonnancer durant l'ordonnancementd'une nouvelle tâche.Nous validons notre proposition parmi de l'analyse de tracesd'exécutions d'une factorisation de Cholesky implémenté avec lesupport d'exécution StarPU et exécutée dans une plate-forme hybride(CPU/GPU). Nos études de cas montrent comment améliorer la partitiondes tâches entre le multi-(GPU, coeur) pour s'approcher des bornesinférieures théoriques, comment améliorer le pipeline des opérationsMPI entre le multi-(noeud, coeur, GPU) pour réduire le démarrage lentedans les noeuds distribués et comment optimiser le support d'exécutionpour augmenter la bande passante MPI. Avec l'emploi des stratégies desimulation et débogage, nous fournissons un workflow pourl'examiner, en détail, les décisions d'ordonnancement. Cela permet deproposer des changements pour améliorer les mécanismes d'ordonnancementet prefetch du support d'exécution. / Programming paradigms in High-Performance Computing have been shiftingtoward task-based models that are capable of adapting readily toheterogeneous and scalable supercomputers. The performance oftask-based applications heavily depends on the runtime schedulingheuristics and on its ability to exploit computing and communicationresources.Unfortunately, the traditional performance analysis strategies areunfit to fully understand task-based runtime systems and applications:they expect a regular behavior with communication and computationphases, while task-based applications demonstrate no clearphases. Moreover, the finer granularity of task-based applicationstypically induces a stochastic behavior that leads to irregularstructures that are difficult to analyze.In this thesis, we propose performance analysis strategies thatexploit the combination of application structure, scheduler, andhardware information. We show how our strategies can help tounderstand performance issues of task-based applications running onhybrid platforms. Our performance analysis strategies are built on topof modern data analysis tools, enabling the creation of customvisualization panels that allow understanding and pinpointingperformance problems incurred by bad scheduling decisions andincorrect runtime system and platform configuration.By combining simulation and debugging we are also able to build a visualrepresentation of the internal state and the estimations computed bythe scheduler when scheduling a new task.We validate our proposal by analyzing traces from a Choleskydecomposition implemented with the StarPU task-based runtime systemand running on hybrid (CPU/GPU) platforms. Our case studies show howto enhance the task partitioning among the multi-(GPU, core) to getcloser to theoretical lower bounds, how to improve MPI pipelining inmulti-(node, core, GPU) to reduce the slow start in distributed nodesand how to upgrade the runtime system to increase MPI bandwidth. Byemploying simulation and debugging strategies, we also provide aworkflow to investigate, in depth, assumptions concerning the schedulerdecisions. This allows us to suggest changes to improve the runtimesystem scheduling and prefetch mechanisms.

Les développeurs des systèmes informatiques, y compris critiques, font souvent appel à des systèmes d'exploitation sur étagère. Cependant, un mauvais fonctionnement d'un système d'exploitation peut avoir un fort impact sur la sûreté de fonctionnement du système global, d'où la nécessité de trouver des moyens efficaces pour caractériser sa sûreté de fonctionnement. Dans cette thèse, nous étudions l'étalonnage de la sûreté de fonctionnement des systèmes d'exploitation par rapport aux comportements défectueux de l'application. Nous spécifions les propriétés qu'un étalon de sûreté de fonctionnement doit satisfaire. Après, nous spécifions les mesures et la mise en oeuvre des trois étalons destinés à comparer la sûreté de fonctionnement de différents systèmes d'exploitation. Ensuite, nous développons les prototypes des trois étalons. Ces prototypes servent à comparer les différents systèmes d'exploitation des familles Windows et Linux, et pour montrer la satisfaction des propriétés identifiées.

Cette thèse étudie la faisabilité de la diffusion de contenu sur un réseau tolérant aux délais (DTN) dans une zone urbaine. L'application cible est la distribution de la version électronique d'un journal dans une grande ville. Bien que des contraintes de temps ne s'appliquent pas de manière stricte, il est tout de même attendu que la diffusion d'information se fasse dans un délai raisonnable. Deux métriques de performance sont considérés~: le délai de message et le temps de propagation. Le délai de message est le délai nécessaire pour transmettre un contenu à partir d'un n{\oe}ud mobile à un autre n{\oe}ud, tandis que le temps de propagation est le délai nécessaire pour diffuser un contenu sur un ensemble de n{\oe}uds du réseau. Premièrement, notre objectif est de mesurer de manière analytique les performances d'un environnement DTN simple lorsqu'un contenu est distribué exclusivement à travers des contacts entre les n{\oe}uds mobiles. Nos contributions résultent de la prise en compte de la probabilité d'intérêt/acceptation dans l'expression en forme fermée et l'expression asymptotique du délai moyen de message. La probabilité d'intérêt/acceptation représente la probabilité qu'un contenu soit accepté par un n{\oe}ud qui manifeste de l'intérêt pour ce contenu lors d'un contact. L'expression asymptotique permet de déterminer des moyens efficaces d'améliorer le délai moyen de messages dans une zone où la densité des n{\oe}uds mobiles est basse ou haute. Nous montrons aussi une relation entre le délai moyen de message et le temps moyen de propagation dans de tels environnements. Deuxièmement, si le délai est jugé excessif, nous suggérons un déploiement de kiosques de données dans l'environnement afin d'améliorer les performances de la diffusion de contenu. Les kiosques de données sont des dispositifs simples qui reçoivent les contenus directement depuis leur source, le plus souvent en utilisant des réseaux filaires ou cellulaires. Un des problèmes posés pour concevoir efficacement un tel réseau est le nombre de kiosques de données qu'il faut déployer pour satisfaire aux objectifs de performance. Pour répondre à ce problème, nous déterminons les valeurs de la borne supérieure et de la borne inférieure du nombre de kiosques de données nécessaires pour distribuer le contenu dans une zone géographique en optimisant un temps moyen de propagation pris comme objectif. Nous montrons aussi une propriété importante que ces bornes varient linéairement avec le taux de contact entre un n{\oe}ud mobile et un kiosque de données. Enfin, nous considérons le problème de l'emplacement optimal des kiosques de données dans un scénario plus réaliste où les utilisateurs se déplacent en utilisant un système de transport (comme le métro ou le train de banlieue) qui relie plusieurs régions. Nous analysons le choix des stations de métro où installer un kiosque de données pour optimiser le temps moyen de propagation. Les résultats de l'analyse confirment que l'emplacement optimal des kiosques de données n'est pas seulement influencé par les caractéristiques d'une région, mais aussi par le nombre d'utilisateurs mobiles qui recevront le contenu. Nous validons nos résultats analytiques par des simulations en prenant différents modèles de mobilité ainsi que des données de mobilité résultant de mesures réelles.

Les systèmes à commutation constituent un cas particulier des systèmes dynamiques hybrides. Ils sont composés d'une famille de systèmes et d'une loi de commutation qui détermine quel mode est activé à chaque instant. Ces systèmes représentent une large gamme de systèmes concrets. L'étude de la stabilité de ceux-ci a déjà été longuement abordée. Les travaux de cette thèse portent sur l'analyse de performance des systèmes à commutation linéaires en temps discret et sur la synthèse de différentes lois de commande pour ces systèmes en tenant compte de contraintes de performances. L'analyse de stabilité de ces systèmes a été étendue pour tenir compte de l'aspect performance qui a été modélisée par un critère quadratique. La valeur du critère dépendant des commutations, l'analyse porte sur le coût garanti des performances. Grâce à la résolution d'un problème d'optimisation sous des contraintes sous la forme d'inégalités matricielles linéaires, un majorant du coût garanti est déterminé. Une approche est proposée pour évaluer la qualité du majorant trouvé. Un deuxième point abordé est la conception de contrôleurs qui tient compte de l'aspect performance. Des méthodes de synthèse de différents contrôleurs (retour d'état, retour d'état reconstruit par observateur et retour de sortie dynamique) sont proposées dans ce cadre. Enfin, nos résultats ont été appliqués au cas des systèmes contrôlés en réseau.

Les systèmes distribués, tels que les grilles, sont utilisés aujourd'hui pour l'exécution des grandes applications parallèles. Quelques caractéristiques de ces systèmes sont l'interconnexion complexe de ressources qui pourraient être présent et de la facile passage à l'échelle. La complexité d'interconnexion vient, par exemple, d'un nombre plus grand de directives de routage pour la communication entre les processus et une latence variable dans le temps. La passage à l'échelle signifie que des ressources peuvent être ajoutées indéfiniment simplement en les reliant à l'infrastructure existante. Ces caractéristiques influencent directement la façon dont la performance des applications parallèles doit être analysée. Les techniques de visualisation traditionnelles pour cette analyse sont généralement basées sur des diagrammes de Gantt que disposent la liste des composants de l'application verticalement et metent la ligne du temps sur l'axe horizontal. Ces représentations visuelles ne sont généralement pas adaptés à l'analyse des applications exécutées en parallèle dans les grilles. La première raison est qu'elles n'ont pas été conçues pour offrir aux développeurs une analyse qui montre aussi la topologie du réseau des ressources. La deuxième raison est que les techniques de visualisation traditionnels ne s'adaptent pas bien quand des milliers d'entités doivent être analysés ensemble. Cette thèse tente de résoudre les problèmes des techniques traditionnelles dans la visualisation des applications parallèles. L'idée principale est d'exploiter le domaine de la visualisation de l'information et essayer d'appliquer ses concepts dans le cadre de l'analyse des programmes parallèles. Portant de cette idée, la thèse propose deux modèles de visualisation: les trois dimensions et le modèle d'agrégation visuelle. Le premier peut être utilisé pour analyser les programmes parallèles en tenant compte de la topologie du réseau. L'affichage lui-même se compose de trois dimensions, où deux sont utilisés pour indiquer la topologie et la troisième est utilisée pour représenter le temps. Le second modèle peut être utilisé pour analyser des applications parallèles comportant un très grand nombre de processsus. Ce deuxième modèle exploite une organisation hiérarchique des données utilisée par une technique appelée Treemap pour représenter visuellement la hiérarchie. Les implications de cette thèse sont directement liées à l'analyse et la compréhension des applications parallèles exécutés dans les systèmes distribués. Elle améliore la compréhension des modes de communication entre les processus et améliore la possibilité d'assortir les motifs avec cette topologie de réseau réel sur des grilles. Bien que nous utilisons abondamment l'exemple de la topologie du réseau, l'approche pourrait être adapté, avec presque pas de changements, à l'interconnexion fourni par un middleware d'une interconnexion logique. Avec la technique d'agrégation, les développeurs sont en mesure de rechercher des patterns et d'observer le comportement des applications à grande échelle.

Depuis le développement du GPS, les systèmes de navigation par satellites (GNSS) se sont largement diversifiés : maintenance, modernisation et déploiement de nouveaux systèmes, comme l’européen Galileo. De plus, le nombre d’applications basées sur l’utilisation de signaux GNSS ne cesse d’augmenter. Pour répondre à ces nouveaux challenges et besoins, les récepteurs GNSS ne cessent d’évoluer. Un nouvel axe est le développement du récepteur logiciel qui présente la particularité d’un traitement logiciel des signaux contrairement au récepteur matériel, équipant nos véhicules, smartphones par exemple. Cette thèse de doctorat s’inscrit dans le projet commun d’un laboratoire et d’une PME consistant au développement d’un récepteur logiciel poursuivant les signaux GPS L1 C/A et Galileo E1 OS. L’objectif plus spécifique de la thèse est d’étudier l’acquisition, première étape du traitement du signal GNSS qui doit fournir une estimation grossière des paramètres du signal entrant. Ce travail vise particulièrement les signaux à faible puissance, un seuil d’acquisition est fixé à 27 dB-Hz pouvant s’apparenter à l’acquisition en milieu urbain ou dégradé. Il est important de noter qu’une des contraintes est de réussir l’acquisition de tels signaux au moins 9 fois sur 10, sans aucune aide extérieure ou connaissance des almanachs ou éphémérides. Dans un premier temps, une solide étude théorique portant sur les performances de l’acquisition et les sources de dégradations est menée. Parmi elles, peuvent être citée, les transitions de bits dues à la présence du message de navigation et du code secondaire sur la voie pilote des nouveaux signaux. Est ainsi mis en lumière la nécessité d’avoir recours à une méthode d’acquisition insensible aux inversions de signe du message de navigation. Dans un deuxième temps, une méthode innovante, le Double-Block Zero-Padding Transition-Insensitive (DBZPTI), est donc développée pour permettre l’acquisition du signal Galileo E1 OS de façon efficiente. Elle prend part au développement de la stratégie globale d’acquisition dont l’objectif est d’avoir en sortie une estimation de la fréquence Doppler et du retard de code du signal entrant, assez fine et fiable pour une satisfaisante poursuite du signal. / Since the development of the GPS, the global navigation satellite systems (GNSS) have been widely diversified: maintenance, modernization and deployment of new systems such as the European Galileo. In addition, the number of GNSS signals applications, based on the use of GNSS signals, is increasing. To meet these new challenges and requirements, GNSS receivers are constantly evolving. A new trend is the development of software receiver which processes the GNSS signal in a software way unlike hardware receiver, equipping our vehicles, smartphones, for example. This thesis is part of a common project between a laboratory and a company, consisting of the development of a software receiver tracking GPS L1 C/A and Galileo E1 OS. The more specific aim of the thesis is to study the acquisition, first signal processing which provides a rough estimation of the incoming signal parameters. This work focuses particularly the low power signals, an acquisition threshold is set at 27 dB-Hz considered as a representative of urban or degraded environments. It is important to note that the success of the acquisition of such signals should be at least 9 times out of 10, without any aid or knowledge of almanac or ephemeris. Initially, a solid theoretical study of the acquisition performance and sources of degradation is conducted. One of them is the bit transitions due to the presence of the navigation message and the secondary code on pilot component of the new signals. It is thus highlighted the need to use a Transition-Insensitive acquisition method. Secondly, an innovative method, the Double-Block Zero-Padding Transition-Insensitive (DBZPTI) is developed to permit efficiently the acquisition of Galileo E1 OS signal. It takes part in the development of the global acquisition strategy, which should provide an estimate of the Doppler frequency and code delay, fine and reliable, for a satisfactory signal tracking.

Comprendre les performances d'une application multi-thread est difficile. Les threads interfèrent quand ils accèdent à la même ressource, ce qui ralentit leur exécution. Malheureusement, les outils de profiling existants se focalisent sur l'identification des causes de l'interférence, et non pas sur ses effets.Le développeur ne peut donc pas conclure si l'optimisation d'une interférence identifiée par un outil de profiling peut mener à une meilleure performance. Dans cette thèse, on propose de compléter les outils existants par un outil orienté-effet capable de quantifier l'impact de l'interférence sur la performance, indépendamment de la cause de l'interférence. Avec une évaluation de 27 applications, on montre que notre outil réussit à identifier 12 bottlenecks causés par 6 types d'interférence différents / Understanding the performance of a multi-threaded application is difficult. The threads interfere when they access the same resource, which slows their execution down. Unfortunately, current profiling tools focus on identifying the interference causes, not their effects.The developer can thus not know if optimizing the interference reported by a profiling tool can lead to better performance. In this thesis, we propose to complete the profiling toolbox with an effect-oriented profiling tool able to indicate how much interference impacts performance, regardless of the interference cause. With an evaluation of 27 applications, we show that our tool successfully identifies 12 performance bottlenecks caused by 6 different kinds of interference

Cette thèse porte sur l'étude du positionnement optimale des réseaux de capteurs pour la localisation de sources. Nous avons étudié deux approches: l'approche basée sur les performances de l'estimation en termes d'erreur quadratique moyenne et l'approche basée sur le seuil statistique de résolution (SSR).Pour le première approche, nous avons considéré les bornes inférieures de l'erreur quadratique moyenne qui sont utilisés généralement pour évaluer la performance d'estimation indépendamment du type d'estimateur considéré. Nous avons étudié deux types de bornes: la borne Cramér-Rao (BCR) pour le modèle où les paramètres sont supposés déterministes et la borne Weiss-Weinstein (BWW) pour le modèle où les paramètres sont supposés aléatoires. Nous avons dérivé les expressions analytiques de ces bornes pour développer des outils statistiques afin d'optimiser la géométrie des réseaux de capteurs. Par rapport à la BCR, la borne BWW peut capturer le décrochement de l'EQM des estimateurs dans la zone non-asymptotique. De plus, les expressions analytiques de la BWW pour un modèle Gaussien général à moyenne paramétré ou à covariance matrice paramétré sont donnés explicitement. Basé sur ces expressions analytiques, nous avons étudié l'impact de la géométrie des réseaux de capteurs sur les performances d'estimation en utilisant les réseaux de capteurs 3D et 2D pour deux modèles des observations concernant les signaux sources: (i) le modèle déterministe et (ii) le modèle stochastique. Nous en avons ensuite déduit des conditions concernant les propriétés d'isotropie et de découplage.Pour la deuxième approche, nous avons considéré le seuil statistique de résolution qui caractérise la séparation minimale entre les deux sources. Dans cette thèse, nous avons étudié le SSR pour le contexte Bayésien moins étudié dans la littérature. Nous avons introduit un modèle des observations linéarisé basé sur le critère de probabilité d'erreur minimale. Ensuite, nous avons présenté deux approches Bayésiennes pour le SSR, l'une basée sur la théorie de l'information et l'autre basée sur la théorie de la détection. Ces approches pourront être utilisée pour améliorer la capacité de résolution des systèmes.

non disponible