Mise en Oeuvre, Evaluation des Performances et Vérification de la Validité de Topologies et de Schémas de Routage pour l'Aide a la Conception de Réseaux d'Interconnexion pour Architectures Parallèles

A. Bouaraoua

LIP6 1998/035: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 LIP6 / LIP6 research reports
113 pages - Mai/May 1998 - French document.

PostScript : 422 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Architecture des Systèmes Intégrés et Micro-Électronique

Titre français : Mise en Oeuvre, Evaluation des Performances et Vérification de la Validité de Topologies et de Schémas de Routage pour l'Aide a la Conception de Réseaux d'Interconnexion pour Architectures Parallèles
Titre anglais : Design, Performance Evaluation and Validity Verification of Topologies and Routing Schemes for Interconnection Networks for Parallel Architectures Aided Design

Résumé : permettant la conception de réseaux d'interconnexion pour des machines parallèles qui sont des réseaux de stations de travail. Plus particulierement, cette thèse tourne autour de deux axes: le routeur RCube et la machine Multi-PC respectivement developpé et en cours de developpement au sein de l'equipe ASIM du laboratoire LIP6.
L'étiquetage de plusieurs topologies regulières utilisant RCube et conformes aux spécifications de Multi-PC sont présentées. Les résultats de l'évaluation des performances de ces topologies pour plusieurs tailles et sous differentes charges sont également présentes ici. Le coût de l'adaptativite est discuté au vu des résultats obtenus.
L'évaluation des performances de différentes topologies a permi d'effectuer une évaluation du routeur RCube. Cette thèse propose une extension de RCube par l'ajout d'une structure de mémorisation centralisée.
Le support de topologies non régulières est rendu possible par la fourniture d'un algorithme de configuration automatique de topologies quelconques. Cet algorithme est une modification de l'algorithme de Van-Leeuwen dont le but est de produire un adressage linéaire des seuls processeurs dans des réseaux où il est possible que certains routeurs ne comportent aucun processeur.
Finalement, une théorie de vérification formelle de la validité d'un schéma de routage est présentée. Une méthode de vérification automatique, dérivée de cette théorie, et les principes de son implémentation logicielle sont également présentés.

Abstract : This thesis presents several works targeting to provide a set of tools that will allow a proper design of interconnection networks for parallel machines that are networks of workstations. More particularly, this thesis turns around two axis: the RCube router and the Multi-PC machine respectively developed and in development within the ASIM team of the LIP6 laboratory.
The labelling of several standard topologies using RCube and compliant with the Multi-PC machine specifications are presented. The results of performance evaluation of these topologies for several sizes and under different workloads are presented too. The adaptivity cost is discussed as a consequence of the obtained results.
The performance evaluation of different topologies allowed to make an evaluation of the RCube router. This thesis suggests an extension of RCube with a central buffering structure.
Supporting non-standard topologies is made possible by providing an automatic configuration algorithm working on any given topology. This algorithm is a modification of the Van-Leeuwen algorithm. Its main goal is producing a linear adressing of processors only in networks where it is possible that some routers have no attached processor.
Finally, a complete theory of formal verification of the validity of a routing scheme is presented. An automatic verification method, derived from this theory, and the principles of its software implementation are presented too.

Mots-clés : Réseaux d'interconnexion, topologies, schémas de routage, évaluation des performances, interblocage

Key-words : Interconnection networks, topologies, routing schemes, performance evaluation, deadlock

Publications internes LIP6 1998 / LIP6 research reports 1998

Responsable Éditorial / Editor
webmaster@lip6.fr