Mémoires de Fin d’Etudes
Etablissement
Université de Béjaia - Abderrahmane Mira
Affiliation
Département d’Informatique
Auteur
KEMCHA, Rebiha
Directeur de thèse
Pr. KECHADI M.-T. (Professeur)
Co-directeur
Dr. TARI A.-K. (Docteur)
Filière
Informatique
Diplôme
Magister
Titre
All-to-All Personalised Exchange in self-routable MCRB Interconnection Networks
Mots clés
Multistage Interconnection Networks, Multiprocessor Systems, Conflict-Free Memory Access, Distributed and Parallel Systems.
Résumé
Multiprocessor systems are widely studied during the last two decades and different architectures and designs were developed and implemented. They consist of processing elements linked together by a network. However, networks become a limiting factor to the performance of modern multiprocessor systems. Recently, the interconnection networks have gained a great attention from the industry sector. This will continue as digital system technology improves. The routing in a multi-stage interconnection network (MIN) must be carefully handled for various reasons including the simplicity of the design, speed, uniformity, and mainly must handle the conflict that may occur during message delivering. It was always the case that a trade-off between hardware cost and network capability has to be made. The network capability can be measured in terms of permutation capability (the size of the subset of permutations that are implemented by the network). For example, baseline and omega networks have hardware cost of O(nlog n). Their routing for permutations is very efficient (in O(log n) time complexity), but they can only implement a small subset of all n! permutations. Therefore increasing the number of feasible permutations may usually imply an increase in hardware complexity. In this project, we consider an interconnection network called Multi-stage Chordal Ring-Based interconnection network (MCRB). The main objective in this project is to study its performance, and more precisely we study the behaviour of the MCRB interconnection network while routing some message-permutations. Note that in a permutation operation, every processing element sends a message to one processing-element and every processing-element receives from only one other processing-element. Moreover, there are tow types of conflict-free routings in a MIN: routing with link-disjoint paths and routing with node-disjoint paths. Link-disjoint paths means that no two different message paths share the same link in the network at a time, which is a mandatory requirement for routing.
Statut
Vérifié