DEA, Doctorat et ATER

Dès mon DEA, je me suis intéressé au domaine de l’algorithmique distribué. J’ai travaillé sur un micro-noyau embarqué, temps-réel et distribué. Plus particulièrement, mon travail a consisté en la gestion des communications entre des capteurs (considérés comme des objets intelligents communicants) modélisés par des processus tolérant aux fautes.

Durant mon doctorat j’ai travaillé sur des problèmes d’algorithmique du texte. Les algorithmes de recherche d’informations doivent être efficaces même si la vitesse et la capacité de mémoire des ordinateurs augmentent régulièrement. Aussi, des algorithmes parallèles sur un modèle à grains fins (en particulier le modèle systolique) ont été développés.

Mon travail a consisté à créer une passerelle entre le modèle à grains fins et un modèle à gros grains (en particulier le modèle CGM – Coarse Grained Multicomputers) afin de pouvoir utiliser des grappes d’ordinateurs. Le modèle CGM, proposé par F. Dehne et al., possède des propriétés qui le rendent très intéressant d’un point de vue pratique car il est parfaitement adapté à la modélisation des architectures existantes pour lesquelles le nombre de processeurs peut être de plusieurs milliers et la taille des données peut atteindre plusieurs milliards d’octets. Un algorithme développé pour ce modèle est constitué de calculs locaux utilisant, si possible, des algorithmes séquentiels optimaux et de rondes de communication dont le nombre doit être indépendant de la taille des données à traiter. Ce modèle est économique car il est indépendant des architectures réelles et permet de réutiliser des algorithmes séquentiels efficaces, ce qui le rend très portable. Ainsi, nous avons pu exécuter par exemple une approche programmation dynamique du problème de la recherche de la plus longue sous-suite commune à deux mots sur des grappes d’ordinateurs et améliorer l’efficacité de l’algorithme utilisé.

Il a été proposé des solutions CGM aux problèmes de recherche de la plus longue sous-suite croissante, de la plus longue sous-suite commune à deux mots, du plus long suffixe répété en chaque caractère d’un mot et de répétitions. Pour cela, on a utilisé des solutions systoliques existantes qui ont été adaptée au modèle CGM. Tous les problèmes traités ont été implantés en langage C en utilisant la librairie de communication MPI, et testés sur des clusters multiprocesseur fonctionnant sous LINUX. Lors de ces tests, il a été constaté que la charge de travail n’est pas la même sur chaque processeur lors du traitement des solutions CGM. Ce déséquilibre de charge est intrinsèquement lié aux problèmes étudiés et il a été proposé une solution d’équilibrage de charges.

Nous avons aussi tenté de faire une extrapolation des résultats de nos travaux afin de prédire quelles sont les adaptations envisageables des architectures systoliques au modèle CGM. Le travail présenté n’est que le début d’un travail sur le modèle CGM car de nombreuses voies restent à explorer.