Techniques de réécriture pour le traitement de problème de routage dans les graphes de Cayley - Université de Lorraine Access content directly
Theses Year : 1996

Techniques de réécriture pour le traitement de problème de routage dans les graphes de Cayley

Polina Strogova
  • Function : Author
  • PersonId : 757086
  • IdRef : 03531334X

Abstract

Non disponible / Not available
Cette thèse traite des problèmes de routage dans les réseaux d'interconnexion de machines massivement parallèles, dont les processeurs sont relies entre eux suivant une topologie de graphe de Cayley (connue pour de bonnes propriétés quant au routage). Dans notre modèle chaque processeur, représente par un sommet, possède une mémoire individuelle qui permet d'effectuer un calcul local. Il ne partage avec d'autres processeurs que des canaux de communications, qui sont modélisés par des arcs. Nous étudions le problème de routage simultané qui se pose lors de la programmation, pour une application donnée, d'un schéma de communication entre les processeurs. Le problème de routage simultané consiste à trouver les chemins disjoints par lesquelles les messages, émis par les processeurs-sources, circuleront avant d'arriver aux processeurs-destinataires de messages. Nous traitons ce problème en toute généralité, en supposant que le graphe de Cayley est défini par un ensemble de générateurs du groupe qu'il représente. Notre but est de diviser le problème de routage simultané initial en sous-problèmes de routage simultané pour les sous-graphes de Cayley indépendants, afin de réduire la complexité du problème initial et pouvoir traiter les sous-problèmes en parallèle. Nous introduisons dans la thèse une nouvelle décomposition récursive d'un graphe de Cayley fini en une union arc-disjointe de graphes de Cayley d'un sous-groupe et de graphe dit frontière de décomposition. En utilisant cette décomposition, nous divisons le problème de routage simultané initial en sous-problèmes de routage simultané pour les sous-graphes de Cayley et pour la frontière. Nous formulons un problème d'optimisation combinatoire, dont la résolution permet de faire un choix global optimal de sommets intermédiaires dans les sous-graphes de décomposition. La formulation du problème d'optimisation combinatoire utilise un nouvel algorithme de calcul de cout minimal d'un chemin entre deux sommets d'un graphe de Cayley. Cet algorithme utilise les techniques de réécriture. L?inefficacité des outils de déduction automatique existant dans le cas de grands groupes (i.e. de taille supérieure a 10 000 éléments) nous a poussé à introduire une nouvelle structure de données pour la complétion de groupes finiment présentés, appelée graphes patch. Les graphes patch représentent d'une façon compacte des systèmes de réécriture pour les groupes. L?application des règles d'inférence pour la complétion des groupes, utilisant les graphes patch, accélère le processus de complétion et permet d'économiser de l'espace mémoire, en évitant de copier les mots et d'engendrer certaines équations redondantes. Toutes les nouvelles méthodes et procédures de la thèse sont illustrées par de nombreux exemples.
No file

Dates and versions

tel-01747207 , version 1 (29-03-2018)

Identifiers

  • HAL Id : tel-01747207 , version 1

Intranet access

Cite

Polina Strogova. Techniques de réécriture pour le traitement de problème de routage dans les graphes de Cayley. Autre [cs.OH]. Université Henri Poincaré - Nancy 1, 1996. Français. ⟨NNT : 1996NAN10352⟩. ⟨tel-01747207⟩
13 View
0 Download

Share

Gmail Facebook X LinkedIn More