Mes recherches concernent les outils de développement pour le calcul intensif. Une application sera dite intensive s'il faut fortement l'optimiser pour obtenir la puissance de calcul requise pour répondre aux contraintes, d'une part, de temps d'exécution et, d'autre part, de ressources de la plateforme d'exécution. De telles applications se retrouvent aussi bien dans le domaine du calcul scientifique que dans le domaine du traitement de signal intensif (télécommunications, traitement multimédia). Les difficultés de développement de telles applications sont principalement l'exploitation du parallélisme des architectures d'exécution (des supercalculateurs aux systèmes sur silicium en passant par les grappes de stations de travail), l'hétérogénéité de ces mêmes architectures et le respect des contraintes de temps et de ressources. Le but de mes recherches est de proposer des outils permettant la programmation efficace des applications de calcul intensif. Ceux-ci peuvent être des compilateurs, des paralléliseurs ou des environnements de spécification. Mes travaux ont commencé par les compilateurs paralléliseurs et s'orientent de plus en plus vers les environnements de spécification. Ces environnements comportent des compilateurs paralléliseurs. Cette évolution consiste donc à remplacer le langage de programmation et la phase d'analyse des programmes par une spécification des algorithmes de plus haut niveau et facilitant la phase d'analyse de dépendances. En effet, le but de cette analyse est de retrouver l'essence de l'algorithme codé par le programme analysé. La spécification de l'algorithme par les seules dépendances de données permet d'éliminer l'analyse de dépendances et d'avoir toute l'information nécessaire pour les optimisations du compilateur paralléliseur. Quatre principes dirigent mes recherches : 1. Programmer au plus haut niveau possible. Il ne devrait pas être de la responsabilité du programmeur de gérer les détails de l'exécution de son application. Idéalement, il devrait exprimer son algorithme et les compilateurs devraient générer le code le plus efficace possible sur l'architecture visée. 2. Promouvoir le parallélisme de données. Ce paradigme de programmation permet justement une programmation de haut niveau dans bien des cas. Il est bien adapté au calcul intensif où les traitements sont souvent réguliers et la quantité de données manipulées importante. 3. Optimiser au plus tôt dans la chaîne de développement. Je suis convaincu que plus les informations de performances et les optimisations sont faites tôt dans le développement d'une application, plus ce développement sera rapide et l'application efficace. L'environnement de conception doit donc faire apparaître ces informations si elles sont disponibles, y compris avant compilation de l'application. 4. Restreindre le domaine d'application. Il est très difficile d'optimiser tous les programmes en général. Le domaine du calcul intensif lui-même est déjà ambitieux. En se focalisant sur un domaine d'application précis, on peut espérer réduire la variété des applications et ainsi proposer des optimisations adaptées. C'est la voie que j'ai suivie dans mes recherches les plus récentes en restreignant le domaine d'application au traitement de signal intensif.

La tendance des constructeurs pour le calcul scientifique est à l'imbrication de technologies permettant un degré de parallélisme toujours plus fort au sein d'une même machine : architecture NUMA, puces multicœurs, SMT. L'efficacité de l'exécution d'une application parallèle irrégulière sur de telles machines hiérarchiques repose alors sur la qualité de l'ordonnancement des tâches et du placement des données, pour éviter le plus possible les pénalités NUMA et les défauts de cache. Les systèmes d'exploitation actuels, pris au dépourvu car trop généralistes, laissent les concepteurs d'application contraints à « câbler » leurs programmes pour une machine donnée.<br /><br />Dans cette thèse, pour garantir une certaine portabilité des performances, nous définissons la notion de /bulle/ permettant d'exprimer la nature structurée du parallélisme du calcul, et nous modélisons l'architecture de la machine cible par une hiérarchie de listes de tâches. Une interface de programmation et des outils de débogage de haut niveau permettent alors de développer simplement des ordonnanceurs dédiés, efficaces et portables. Différents ordonnanceurs mettant en œuvre des approches variées ont été développés, en partie notamment par des stagiaires encadrés au sein de l'équipe, ce qui montre à la fois la puissance et la simplicité de l'interface. C'est ainsi une véritable plate-forme de développement et d'expérimentation d'ordonnanceurs à bulles qui a été intégrée au sein de la bibliothèque de threads utilisateur marcel. Le support OpenMP du compilateur GCC, GOMP, a été étendu pour utiliser cette bibliothèque et exprimer la nature structurée des sections parallèles imbriquées à l'aide de bulles. Avec la couche de compatibilité POSIX de marcel, ces supports ont permis de tester les différents ordonnanceurs à bulles développés, sur différentes applications. Les gains obtenus, de l'ordre de 20 à 40%, montrent l'intérêt de notre approche.

De nombreuses applications scientifiques utilisent et génèrent d'énormes quantités de données. Ces applications qui exploitent des modèles d'accès parallèles spécifiques (principalement des accès disjoints) sont souvent pénalisées par des systèmes de stockage inadaptés. Pour éviter les dégradations de performances, les bibliothèques d'Entrées/Sorties parallèles telles que ROMIO sont généralement utilisées pour agréger les petites requêtes séparées en de plus grosses contiguës habituellement plus performantes. Toutefois, les optimisations apportées pour un programme ne tiennent pas compte de l'ensemble des interactions avec d'autres applications s'exécutant en concurrence sur la grappe. La conséquence est que ces routines spécifiques visant à optimiser les accès d'une application vont s'avérer inutiles, car leur effet va être perturbé par les autres applications !<br /><br />Ce document décrit une nouvelle approche, appelée aIOLi, permettant le<br />contrôle, le réordonnancement et la régulation de l'ensemble des interactions générées par les différentes applications s'exécutant simultanément sur une grappe et ce, en s'appuyant uniquement sur l'interface POSIX.<br /><br />Dans un tel contexte, la performance, l'interactivité et l'équité sont des critères pour lesquels il est important de trouver un bon compromis. Pour y parvenir, une stratégie d'ordonnancement globale prenant en compte également les problématiques d'Entrées/Sorties parallèles locales aux applications a été définie. Le service aIOLi consiste en un support d'ordonnancement générique pouvant être rattaché à différentes parties d'un système de fichiers. L'exécution concurrente de jeux de tests IOR sur un serveur NFS traditionnel ont montré des améliorations particulièrement significatives pour les accès en lecture en comparaison aux performances pouvant être atteintes avec les routines POSIX ou MPI I/O.

La tendance actuelle des constructeurs pour le calcul scientifique est à l'utilisation de grappes de machines dont les noeuds comportent un nombre de coeurs toujours plus grand. Le modèle basé uniquement sur MPI laisse peu à peu la place à des modèles mélangeant l'utilisation de threads et de MPI. Ce changement de modèle entraîne de nombreuses problématiques car les implémentations MPI n'ont pas été conçues pour supporter les applications multi-threadées. Dans cette thèse, afin de garantir le bon fonctionnement des communications, nous proposons un module logiciel faisant interagir l'ordonnanceur de threads et la bibliothèque de communication. Ce module, en collaborant avec l'ordonnanceur de threads, permet de faire progresser les communications en arrière-plan et d'assurer un haut niveau de réactivité, même lorsque la machine est surchargée.

Thèse de doctorat : Informatique : Tours : 2008. / Titre provenant de l'écran-titre.

Le déminage mécanique consiste à scarifier le sol avec une " charrue ", outil formé d'une lame en V munie de plusieurs dents, poussée par un engin : les dents déstructurent le sol et le font remonter devant la lame qui l'évacue sur le côté avec les mines qu'il contient. L'objectif de nos travaux est de mettre en œuvre la simulation numérique par éléments finis du problème fortement non linéaire issu de la modélisation de la scarification du sol. Le code d'éléments finis implicite Forge3®, dédié à la mise en forme des métaux, a été choisi comme support numérique. Il permet de prendre en compte les grandes déformations, en particulier à l'aide de son remaillage automatique. Nous avons dans un premier temps implanté dans ce code deux modèles élastoplastiques de comportement, l'un incompressible réservé aux sols fins saturés, purement cohésifs, l'autre compressible, fondé sur la notion d'état critique, pour les matériaux purement frottants ou cohésifs et frottants. Ces modèles adoucissants sont intégrés par un schéma de retour radial généralisé, au sein d'une formulation implicite du problème aux limites. Nous montrons que la matrice de raideur est non symétrique dans le cas compressible et que la symétrisation du système ne conduit pas à une approche robuste. Nous avons donc importé et testé un solveur itératif non-symétrique : Bi-CGSTAB. Nous avons validé la programmation de ces modèles sur des essais triaxiaux. Pour les comportements adoucissants, on constate des oscillations dans la relation contrainte/déformation passé le pic de contrainte. Ces difficultés numériques sont traitées par linéarisation et régularisation. Dans un deuxième temps, nous avons mis en œuvre des simulations de scarification pour différents niveaux de complexité : une dent seule, une dent + une tranche de lame, plusieurs dents, en faisant suffisamment avancer l'outil pour atteindre le régime stationnaire ; cela se révèle d'autant plus long que l'outil est large, ce qui nous amène au calcul très intensif. L'influence de paramètres géométriques comme l'inclinaison de la dent ou l'angle d'étrave du système a été mise en évidence, elle est qualitativement conforme aux observations expérimentales. L'étude de l'influence des paramètres des modèles de comportement montre la prépondérance de ceux liés à l'état critique, i.e. aux propriétés mécaniques après de grandes déformations. Enfin nous avons validé qualitativement le code en termes de modes d'écoulements et de répartition des efforts pour des outils multi-dents. La comparaison quantitative des efforts reste à affiner en revenant sur le comportement choisi et son implémentation.

Cette thèse définit un nouveau modèle de calcul et de communication, dénommé graphe à routage k-périodique (KRG). Ce modèle, de la famille des réseaux de processus flots de données, admet des aiguillages réguliers des données, explicités par des séquences binaires k-périodiques. Nous étudions les propriétés mathématiques intrinsèques au modèle. Le routage explicite et l'absence de conflit nous permettent d'exprimer algébriquement les dépendances de données, de même que des transformations topologiques préservant le comportement du graphe. Nous montrons ensuite comment ordonnancer le KRG, en associant aux nœuds des horloges k-périodiques. Nous positionnons ensuite notre modèle au sein d'un flot de conception dédié aux applications de traitement intensif de données. Nous montrons en particulier la capacité des KRG à représenter explicitement le parallélisme d'instruction extrait du modèle polyédrique. Nous pouvons alors appliquer un ensemble d'optimisations de bas niveau, sortant du cadre affine du modèle polyédrique. Nous présentons enfin une méthodologie pour l'implantation des KRG, basée sur la conception insensible aux latences.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Nous abordons ici la thématique des opérateurs et processeurs flot de données dédiés au traitement d'images et orientés vers la morphologie mathématique. L'objectif principal est de proposer des architectures performantes capables de réaliser les opérations simples de ce corpus mathématique afin de proposer des opérateurs morphologiques avancés. Ces dernières années, des algorithmes astucieux ont été proposés avec comme objectif de réduire la quantité des calculs nécessaires à la réalisation de transformations telle que la ligne de partage des eaux. Toutefois, les mises en œuvre proposées font souvent appel à des structures de données complexes qui sont difficiles à employer sur des machines différentes des processeurs généralistes monocœurs. Les processeurs standard poursuivant aujourd'hui leur évolution vers une augmentation du parallélisme, ces implémentations ne nous permettent pas d'obtenir les gains de performance escomptés à chaque nouvelle génération de machine. Nous proposons alors des mises en œuvre rapides des opérations complexes de la morphologie mathématique par des machines exploitant fortement le parallélisme intrinsèque des opérations basiques. Nous étudions dans une première partie les processeurs de voisinage travaillant directement sur un flot de pixels et nous proposons différentes méthodologies de conception rapide de pipelines dédiés à une application. Nous proposons également une structure de pipeline programmable via l'utilisation de processeurs vectoriels avec différentes possibilités de chaînage. Enfin, une étude avec des machines est proposée afin d'observer la pertinence de notre approche.

Les méthodes et les environnements de programmation adaptés aux machines mono-processeur traditionnelles s'avèrent inutilisables avec les machines parallèles à mémoire distribuée, car ils ne permettent pas d'en maîtriser le parallélisme. À ce jour, l'utilisation de ces machines demeure donc très limitée, car les programmeurs sont en général assez réticents à l'idée de devoir y porter manuellement leurs applications. De nombreuses recherches actuelles visent à simplifier le développement des applications parallèles pour ce type de machine. Le travail effectué au cours de cette thèse s'inscrit dans le cadre du développement et de l'expérimentation de l'environnement EPEE (Environnement Parallèle d'exécution de Eiffel). EPEE constitue un cadre conceptuel pour la conception et la mise en oeuvre de composants logiciels parallèles réutilisables à l'aide des mécanismes de la programmation par objets. Nous avons caractérisé les objets pouvant être distribués et exploités en parallèle dans lénvironnement EPEE, et proposé des schémas conceptuels permettant de développer de tels objets en insistant sur les points clés mis en avant dans les techniques modernes de génie logiciel, à savoir la maîtrise de la complexité (résolue par la modularisation, l'encapsulation, l'héritage), et la maintenabilité (corrective et évolutive). Nous avons ensuite appliqué ces schémas conceptuels pour développer une bibliothèque parallèle de démonstration. Cette bibliothèque expérimentale, baptisée Paladin, est dédiée au calcul d'algèbre linéaire sur machines parallèles à mémoire distribuée. Elle est en outre extensible, d'un emploi aisé, performante et portable. Ces caractéristiques confirment la viabilité de l'approche consistant à utiliser les mécanismes de la programmation par objets pour construire des bibliothèques pour machines parallèles.