• Langue : Français
• Discipline : Informatique
• Identifiant : Thèse : 1998LIL10216
• Type de thèse : Doctorat
• Date de soutenance : 01/01/1998

Résumé en langue originale

Executer un algorithme parallele sur un reseau de processeurs, emuler une architecture par une autre, representer des structures de donnees ou realiser physiquement en vlsi un reseau logique sont des problemes qui sont en general modelises par des problemes de plongement de graphes. En effet, un algorithme parallele peut etre represente par un graphe dans lequel les sommets representent les taches et les aretes les communications necessaires aux calculs. De la meme maniere, une architecture parallele distribuee peut etre representee par un graphe. L'objectif de la these est de proposer des algorithmes de plongements d'arbres quelconques et dynamiques dans les architectures communement utilisees telles que les grilles, les hypercubes et les reseaux de stations de travail. La these est composee des trois parties suivantes : - plongement d'arbres binaires complets et statiques : nous presentons des algorithmes de plongement d'arbres binaires dans une grille bidimensionnelle. Ces methodes de plongements concernent les arbres complets et statiques, c'est a dire dont on connait a priori la taille et la forme. - plongement deterministe d'arbres quelconques et dynamiques : nous presentons des algorithmes de plongement d'arbres quelconques et dynamiques. En d'autres termes, le plongement d'un arbre est effectue sans connaitre a priori ni sa forme ni sa taille. - plongement aleatoire d'arbres quelconques et dynamiques : les algorithmes de plongement proposes dans cette partie sont probabilistes. Afin d'analyser le comportement aleatoire de ces algorithmes, nous avons utilise des outils mathematiques issus de la theorie des chaines de markov et des resultats d'analyse numerique sur les iterations des matrices carrees. Cette analyse nous a permis la mise en uvre d'algorithmes de plongement d'arbres quelconques dans des topologies arbitraires.