Cette thèse présente nos travaux de recherche qui ont comme principal objectif d'assurer la portabilité des performances et le passage à l'échelle des applications scientifiques complexes exécutées sur des plates-formes multi-coeurs parallèles et hiérarchiques. La portabilité des performances est obtenue lorsque l'ordonnancement des tâches d'une application permet de réduire les périodes d'inactivité des coeurs de la plate-forme. Cette portabilité des performances peut être affectée par différents problèmes tels que des déséquilibres de charge, des communications coûteuses et des surcoûts provenant de l'ordonnancement des tâches. Le déséquilibre de charge est la conséquence de comportements de charges irrégulières et dynamiques, où le volume de calcul varie dynamiquement en fonction de la tâche et de l'étape de simulation. Les communications coûteuses sont provoquées par un ordonnancement qui ne prend pas en compte les différents temps de communication entre tâches sur une plate-forme hiérarchique. Cela est accentué par des communications non uniformes et asymétriques au niveau mémoire et réseau. Enfin, ces surcoûts peuvent être générés par des algorithmes de placement trop complexes dont les coûts ne seraient pas compensés par les gains de performance.Pour atteindre cet objectif de portabilité des performances, notre approche repose sur une récolte d'informations précises sur la topologie de la machine qui vont aider les algorithmes d'ordonnancement de tâches à prendre les bonnes décisions. Dans ce contexte, nous avons proposé une modélisation générique de la topologie des plates-formes parallèles. Le modèle comprend des latences et des bandes passantes mesurées de la mémoire et du réseau qui mettent en évidence des asymétries. Ces informations sont utilisées par nos trois algorithmes d'équilibrage de charge nommés NucoLB, HwTopoLB, et HierarchicalLB. De plus, ces algorithmes utilisent des informations provenant de l'exécution de l'application. NucoLB se concentre sur les aspects non uniformes de plates-formes parallèles, alors que HwTopoLB considère l'ensemble de la hiérarchie pour ses décisions, et HierarchicalLB combine ces algorithmes hiérarchiquement pour réduire son surcoût d'ordonnancement de tâches. Ces algorithmes cherchent à atténuer le déséquilibre de charge et des communications coûteuses tout en limitant les surcoûts de migration des tâches.Les résultats expérimentaux avec les trois régulateurs de charge proposés ont montré des améliorations de performances sur les meilleurs algorithmes de l'état de l'art: NucoLB a présenté jusqu'à 19% d'amélioration de performances sur un noeud de calcul; HwTopoLB a amélioré les performances en moyenne de 19%, et HierarchicalLB a surclassé HwTopoLB de 22% en moyenne sur des plates-formes avec plus de dix noeuds de calcul. Ces résultats ont été obtenus en répartissant la charge entre les ressources disponibles, en réduisant les coûts de communication des applications, et en gardant les surcoûts d'équilibrage de charge faibles. En ce sens, nos algorithmes d'équilibrage de charge permettent la portabilité des performances pour les applications scientifiques tout en étant indépendant de l'application et de l'architecture du système. / This thesis presents our research to provide performance portability and scalability to complex scientific applications running over hierarchical multicore parallel platforms. Performance portability is said to be attained when a low core idleness is achieved while mapping a given application to different platforms, and can be affected by performance problems such as load imbalance and costly communications, and overheads coming from the task mapping algorithm. Load imbalance is a result of irregular and dynamic load behaviors, where the amount of work to be processed varies depending on the task and the step of the simulation. Meanwhile, costly communications are caused by a task distribution that does not take into account the different communication times present in a hierarchical platform. This includes nonuniform and asymmetric communication costs at memory and network levels. Lastly, task mapping overheads come from the execution time of the task mapping algorithm trying to mitigate load imbalance and costly communications, and from the migration of tasks.Our approach to achieve the goal of performance portability is based on the hypothesis that precise machine topology information can help task mapping algorithms in their decisions. In this context, we proposed a generic machine topology model of parallel platforms composed of one or more multicore compute nodes. It includes profiled latencies and bandwidths at memory and network levels, and highlights asymmetries and nonuniformity at both levels. This information is employed by our three proposed topology-aware load balancing algorithms, named NucoLB, HwTopoLB, and HierarchicalLB. Besides topology information, these algorithms also employ application information gathered during runtime. NucoLB focuses on the nonuniform aspects of parallel platforms, while HwTopoLB considers the whole hierarchy in its decisions, and HierarchicalLB combines these algorithms hierarchically to reduce its task mapping overhead. These algorithms seek to mitigate load imbalance and costly communications while averting task migration overheads.Experimental results with the proposed load balancers over different platform composed of one or more multicore compute nodes showed performance improvements over state of the art load balancing algorithms: NucoLB presented improvements of up to 19% on one compute node; HwTopoLB experienced performance improvements of 19% on average; and HierarchicalLB outperformed HwTopoLB by 22% on average on parallel platforms with ten or more compute nodes. These results were achieved by equalizing work among the available resources, reducing the communication costs experienced by applications, and by keeping load balancing overheads low. In this sense, our load balancing algorithms provide performance portability to scientific applications while being independent from application and system architecture.

Dans les environnements d'exécution parallèle, la régulation de charge (ou l'ordonnancement applicatif) est le module responsable du contrôle de l'exécution d'un programme sur les ressources de l'architecture distribuée (processeurs et modules mémoire). En pratique, le choix de la stratégie de régulation la plus performante dépend non seulement de l'application mais doit aussi être adapté en fonction de l'architecture cible. Dès lors, la portabilité d'un code ne peut être assurée que si l'on peut modifier cette stratégie. Dans cette thèse, nous proposons l'utilisation de la description dynamique du flot de données comme l'élément central permettant de séparer le code applicatif de la régulation de charge. Sur cette proposition est basée la construction d'un environnement logiciel, modulaire et générique, qui rend possible la modification ou l'ajustement de la stratégie de régulation de charge. La spécification de cet environnement repose sur l'identification des interfaces de la régulation avec d'une part l'application et d'autre part l'architecture. Cette identification, centrée sur l'exploration macroscopique du flot de données, est originale: nous montrons qu'elle étend d'autres systèmes classiques de régulation de charge. Enfin, la validation expérimentale de cet environnement est réalisée grâce à son intégration dans l'interface de programmation Athapascan-1 de l'environnement Athapascan, du projet APACHE. Différentes stratégies d'ordonnancement, statiques, dynamiques et hybrides, ont ainsi été implantés. Nous présentons les performances de quelques unes de ces stratégies appliquées à des programmes Athapascan-1 sur différentes architectures.

Dans cette thèse, nous nous intéressons à l'adaptation de l'algorithmique aux architectures parallèles. Les plateformes hautes performances actuelles disposent de plusieurs niveaux de parallélisme et requièrent un travail considérable pour en tirer parti. Les superordinateurs possèdent de plus en plus d'unités de calcul et sont de plus en plus hétérogènes et hiérarchiques, ce qui complexifie d'autant plus leur utilisation.Nous nous sommes intéressés ici à plusieurs aspects permettant de tirer parti des architectures parallèles modernes. Tout au long de cette thèse, plusieurs problèmes de natures différentes sont abordés, de manière plus théorique ou plus pratique selon le cadre et l'échelle des plateformes parallèles envisagées.Nous avons travaillé sur la modélisation de problèmes dans le but d'adapter leur formulation à des solveurs existants ou des méthodes de résolution existantes, en particulier dans le cadre du problème de la factorisation en nombres premiers modélisé et résolu à l'aide d'outils de programmation linéaire en nombres entiers.La contribution la plus importante de cette thèse correspond à la conception d'algorithmes pensés dès le départ pour être performants sur les architectures modernes (processeurs multi-coeurs, Cell, GPU). Deux algorithmes pour résoudre le problème du compressive sensing ont été conçus dans ce cadre : le premier repose sur la programmation linéaire et permet d'obtenir une solution exacte, alors que le second utilise des méthodes de programmation convexe et permet d'obtenir une solution approchée.Nous avons aussi utilisé une bibliothèque de parallélisation de haut niveau utilisant le modèle BSP dans le cadre de la vérification de modèles pour implémenter de manière parallèle un algorithme existant. A partir d'une unique implémentation, cet outil rend possible l'utilisation de l'algorithme sur des plateformes disposant de différents niveaux de parallélisme, tout en ayant des performances de premier ordre sur chacune d'entre elles. En l'occurrence, la plateforme de plus grande échelle considérée ici est le cluster de machines multiprocesseurs multi-coeurs. De plus, dans le cadre très particulier du processeur Cell, une implémentation a été réécrite à partir de zéro pour tirer parti de celle-ci.

Le contexte des applications de communication visuelle évolue vers l'introduction de fonctionnalités qui dépassent la simple compression d'images: accès universel, interactivité basée-contenu, intégration de contenus hybrides synthétiques-naturels. Une brève introduction au codage avancé d'images permet d'entrevoir l'évolution de la puissance de calcul et de la généricité requises pour l'implémentation de ces systèmes de "deuxième génération". Une synthèse sur l'évolution des circuits VLSI dédiés à l'analyse, la compression et le rendu d'images permet une réflexion sur les limitations architecturales des "processeurs multimédia". Cette thèse propose de combiner le parallélisme massif et l'asynchronisme à grain fin pour apporter de nouvelles perspectives de conception conjointe d'algorithmes et d'architectures VLSI numériques. Une introduction aux différentes notions d'asynchronisme, aux niveaux langage, algorithme, architecture, circuit VLSI, permet de mieux cerner leur sens et les potentiels qu'elles offrent. L'application d'un asynchronisme fonctionnel au filtrage morphologique d'images a abouti à la réalisation d'un réseau VLSI cellulaire asynchrone spécifique comprenant 800.000 transistors en technologie CMOS 0.5µ. La combinaison du parallélisme et de l'asynchronisme est finalement généralisée à travers la définition d'une architecture de coprocesseur programmable pour l'analyse-rendu d'images. L'évaluation de plusieurs primitives algorithmiques originales, basées sur un contrôle mixte SPMD-cellulaire-associatif-flot de données, illustre l'utilisation conjointe de l'asynchronisme à différents niveaux. Ce travail démontre que le relâchement des contraintes de synchronisation et de séquencement, de la spécification à la réalisation matérielle, favorise l'exploitation du parallélisme inhérent aux algorithmes et des potentiels des technologies VLSI.

Les travaux de cette thèse portent sur l'amélioration et l'optimisation de l'algorithme de suivi d'objet couleur Mean-Shift à la fois d’un point de vue robustesse du suivi et d’un point de vue architectural pour améliorer la vitesse d’exécution. La première partie des travaux a consisté en l'amélioration de la robustesse du suivi. Pour cela, l'impact des espaces de représentation couleur a été étudié, puis une méthode permettant la sélection de l'espace couleur représentant le mieux l'objet à suivre a été proposée. L'environnement de la cible changeant au cours du temps, une stratégie est mise en place pour resélectionner un espace couleur au moment opportun. Afin d'améliorer la robustesse dans le cas de séquences particulièrement difficile, le Mean-Shift avec stratégie de sélection a été couplé avec un autre algorithme plus coûteux en temps d'exécution : le suivi par covariance. L’objectif de ces travaux est d’obtenir un système complet fonctionnant en temps réel sur processeurs multi-cœurs SIMD. Une phase d’étude et d'optimisation a donc été réalisée afin de rendre les algorithmes paramétrables en complexité pour qu’ils puissent s’exécuter en temps réel sur différentes plateformes, pour différentes tailles d’images et d’objets suivi. Dans cette optique de compromis vitesse / performance, il devient ainsi possible de faire du suivi temps-réel sur des processeurs ARM type Cortex A9. / The work of this thesis focuses on the improvement and optimization of the Mean-Shift color object tracking algorithm, both from a theoretical and architectural point of view to improve both the accuracy and the execution speed. The first part of the work consisted in improving the robustness of the tracking. For this, the impact of color space representation on the quality of tracking has been studied, and a method for the selection of the color space that best represents the object to be tracked has been proposed. The method has been coupled with a strategy determining the appropriate time to recalculate the model. Color space selection method was also used in collaboration with another object tracking algorithm to further improve the tracking robustness for particularly difficult sequences : the covariance tracking which is more time consuming. The objective of this work is to obtain an entire real time system running on multi-core SIMD processors. A study and optimization phase has been made in order to obtain algorithms with a complexity that is configurable so that they can run in real time on different platforms, for various sizes of images and object tracking. In this context of compromise between speed and performance, it becomes possible to do real-time tracking on processors like ARM Cortex A9.

Cette thèse aborde un ensemble de problèmes lies a la conception et a la mise en œuvre d'un noyau de communication faisant partie de Parx, un noyau de système d'exploitation pour machines multiprocesseurs sans mémoire, développe dans le cadre du projet de recherche européen esprit supernode. Le noyau réalisé une machine virtuelle, vis-a-vis des communications, dans laquelle l'ensemble de processeurs est complètement connecte indépendamment de la topologie du réseau d'interconnexion sous-jacent. La machine virtuelle offre une interface qui facilite l'exploitation correcte du haut degre de parallélisme physique des machines visées. Après un état de l'art des architectures d'ordinateurs massivement parallèles, il est propose un modèle de processus et une structure de noyau de système parallèle. Le modèle est base sur un ensemble d'entités bien adaptées au contrôle de l'exécution des programmes parallèles composes de processus communicants. Ces entités, qui étendent la notion traditionnelle de processus, intègrent des concepts nouveaux visant la meilleure exploitation de l'architecture physique. Dans le modèle de processus communicants, ceux-ci ne coopèrent que par échange de messages. Le contrôle, correct et efficace, de la communication et la synchronisation entre processus s'exécutant sur une architecture multi-processeurs sans mémoire commune est le thème central de cette thèse. Notre étude s'oriente vers la conception d'un noyau de communication, pour lequel les problèmes concernant essentiellement le routage de messages sans interblocage dans le réseau de processeurs et les protocoles de communication entre processus adéquats au modèle de programmation utilisé

L'émergence d'une robotique médicale en chirurgie laparoscopique destinée à automatiser et améliorer la précision des interventions nécessite la mise en Suvre d'outils et capteurs miniaturisés intelligents dont la vision 3D temps réel est un des enjeux. Bien que les systèmes de vision 3D actuels représentent un intérêt certain pour des manipulations chirurgicales endoscopiques précises, ils ont l'inconvénient de donner une image 3D qualitative plutôt que quantitative, laquelle nécessite un appareillage spécifique rendant l'acte chirurgical inconfortable et empêche le couplage avec un calculateur dans le cadre d'une chirurgie assistée. Nous avons développé dans la cadre du projet interne « PICASO » (Plate-forme d'Intégration de CAméras multiSenOrielles) dont les enjeux scientifiques concernent le conditionnement de capteurs intégrés et le traitement et la fusion d'images multi spectrales, un dispositif de vision 3D compatible avec les temps d'exécution des actes chirurgicaux. Ce système est basé sur le principe de la stéréoscopie humaine et met en Suvre des algorithmes de stéréovision passive dense issus de la robotique mobile. Dans cette thèse nous présentons des architectures massivement parallèles, implémentées dans un circuit FPGA, et capables de fournir des images de disparité à la cadence de 130 trames/sec à partir d'images de résolution 640x480 pixels. L'algorithme utilisé est basé sur la corrélation Census avec une fenêtre de calcul de 7 x 7 pixels. Celui-ci a été choisi pour ses performances en regard de sa simplicité de mise en Suvre et la possibilité de paralléliser la plupart des calculs. L'objectif principal de cet algorithme est de rechercher, pour chaque point, la correspondance entre deux images d'entrées (droite et gauche) prises de deux angles de vue différents afin d'obtenir une "carte de disparités" à partir de laquelle il est possible de reconstruire la scène 3D. Pour mettre en Suvre cet algorithme et tenir les contraintes « temps réel » nous avons développé des architectures en « pipeline » (calcul des moyennes, transformation Census, recherche des points stéréo-correspondants, vérification droite-gauche, filtrage...). L'essentiel des différentes parties qui composent l'architecture est décrit en langage VHDL synthétisable. Enfin nous nous sommes intéressés à la consommation en termes de ressources FPGA (mémoires, macro-cellules) en fonction des performances souhaitées.

Les applications de Réalité Virtuelle requièrent une puissance de calcul importante qui peut être apportée par les grappes de PC, des ensembles d'ordinateurs connectés par des réseaux performants. Afin d'exploiter la puissance de ces architectures, une approche consiste à décomposer les applications en plusieurs composants qui sont ensuite déployés sur les différentes machines. Les performances de telles applications dépendent alors du matériel ainsi que des synchronisations entre les différents composants. Evaluer les performances d'une application de RV suivant un déploiement donné consiste à observer si son exécution permet l'interactivité. Cependant, cette phase de test rend la recherche d'un déploiement répondant à ce critère longue et fastidieuse et monopolise l'architecture. Nous proposons donc de définir un modèle permettant l'évaluation des performances à partir de la modélisation de l'architecture, de l'application et de son déploiement. Nous proposons ensuite d'utiliser la programmation par contraintes pour résoudre les contraintes extraites de notre modèle et permettre ainsi d'automatiser la génération de déploiements capables de fournir le niveau d'interactivité souhaité. Cette approche permet ainsi de répondre aux nombreuses questions que peut se poser un développeur : Existe t'il un ou plusieurs déploiements de mon application permettant l'interactivité sur mon architecture ? Si oui, quels sont ils ? L'ajout de machines supplémentaires permet il un gain de performances ?

Dans les architectures parallèles à mémoire distribuée, la communication entre processus est un des facteurs de performance les plus importants pour les applications. Le système qui en a la charge, i.e, le noyau de communication, doit intégrer une fonctionnalité essentielle pour de telles architectures : le routage des messages. Cette fonctionnalité est assurée par une composante spécifique du noyau de communication: le noyau de routage, dont le rôle est l'acheminement d'un message d'un noeud émetteur vers un noeud récepteur. L'acheminement des messages nécessite une stratégie de routage qui spécifie les chemins de communication pour toute paire de processeurs (source, destination) du réseau d'interconnexion. Une telle stratégie de routage doit satisfaire d'une part, des critères de correction et d'autres part, des critères d'efficacité. Le but de cette thèse est la conception de stratégies de routage pour les réseaux de processeurs qui satisfont à la fois, les critères de correction et les critères d'efficacité. Nous proposons une méthode de conception de stratégies de routage, permettant par une démarche incrément-ale, de satisfaire les deux types de critère: la communication multi-niveaux et le schéma de communication primaire associé. Pour mesurer l'efficacité de la méthode, nous l'appliquons à un réseau particulier : la grille torique. Les différents algorithmes de routage obtenus sont corrects et très efficaces. Nous proposons également une technique d'implantation de notre méthode de routage, permettant le calcul des tables de routage directement sur le réseau de processeurs. Cette technique permet ainsi l'obtention d'un système autoconstructif.

Les processeurs graphiques (GPU) actuels offrent une importante puissance de calcul disponible à faible coût. Ce fait a conduit à détourner leur emploi pour réaliser du calcul non graphique, donnant naissance au domaine du calcul généraliste sur processeur graphique (GPGPU). Cette thèse considère d'une part des techniques logicielles pour tirer parti de l'ensemble des opérateurs arithmétiques spécifiques aux GPU dans le cadre du calcul scientifique, et d'autre part des adaptations matérielles aux GPU afin d'exécuter plus efficacement les applications généralistes. En particulier, nous identifions la régularité parallèle comme une opportunité d'optimisation des architectures parallèles, et exposons son potentiel par la simulation d'une architecture GPU existante. Nous considérons ensuite deux alternatives permettant d'exploiter cette régularité. D'une part, nous mettons au point un mécanisme matériel dynamique afin d'améliorer l'efficacité énergétique des unités de calcul. D'autre part, nous présentons une analyse statique opérée à la compilation permettant de simplifier le matériel dédié au contrôle dans les GPU.