Parallélisme et architectures parallèles

♣ Contenu du memoire

Table des matières
LISTE DES FIGURES
LISTE DES TABLEAUX
LISTE DES ABREVIATIONS
Chapitre 1 : Introduction
1.1. Introduction
1.2. Protocole IP et adressage
1.2.1. Protocole IP
1.2.2. Evolution d’adressage IP
1.2.2.1. L’adressage avec classes
1.2.2.1.1. Structure de l’adresse IP
1.2.2.1.2. Classes d’adresses IP
1.2.2.1.3. Adresses IPv4
1.2.2.1.4. Adresses IPv6
1.2.2.1.5. Sous-réseaux
1.2.2.2. Structuration des adresses et agrégation
1.2.2.2.1. Evolution des tailles des tables de routage
1.2.2.2.2. CIDR (Classless Inter-Domain Routing)
1.3. Recherche d’information de routage dans un routeur IP
1.3.1. Routeurs IP
1.3.2. Table de routage
1.3.3. Consultation d’adresses IP (Notre contribution)
1.3.3.1. Consultation d’adresses IP dans le cas d’adressage en classes
1.3.3.2. Consultation d’adresses IP dans le cas d’adressage sans-classes
1.4. Difficulté de recherche des informations de routage
1.5. Contributions
1.6. Plan de la thèse
1.7. Conclusion
Chapitre 2 : Travaux dans le domaine
2.1. Introduction
2.2. Solutions logicielles et structures de données utilisées
2.2.1. Recherche linéaire
2.2.1.1. Recherche linéaire basée sur les longueurs en utilisant les tables de hachage
2.2.2. Algorithmes de recherche binaires basés sur des structures arborescentes
2.2.2.1. Algorithmes de recherche binaires basés sur les bits des préfixes
2.2.2.2. Algorithmes de recherche binaires basés sur les points d’extrémités des plages d’adresses IP (Ranges search)
2.2.2.3. Algorithmes de recherche binaires basés sur les valeurs des préfixes
2.3. Solutions matérielles 1. Mémoire adressable par contenu CAMs et Ternary CAMs
2.3.1.1. Utilisation des CAMs et TCAMs dans les routeurs Internet
2.3.1.2. Architecture des CAMs / TCAMs
2.3.1.3. Recherche dans les CAMs / TCAMs
2.3.1.4. Architectures des CAMs / TCAMs proposées pour l’opération de lookup
2.3.2. Mémoires cache
2.3.3. Architectures multiprocesseurs
2.3.3.1. Manipulation des tables de routage en parallèle
3.4. Conclusion
Chapitre 3 : Parallélisme et architectures parallèles
3.1. Introduction
3.2. Origine du parallélisme
3.3. Sources de parallélisme
3.4. Limites du parallélisme
3.5. Architectures parallèles
3.5.1. Classifications des architectures parallèles
3.5.1.1. Classification de Flynn
3.5.1.1.1. Architecture SISD (Single Instruction stream, Single Data stream)
3.5.1.1.2. Architecture SIMD (Single Instruction stream, Multiple Data stream)
3.5.1.1.3. Architecture MISD (Multiple Instruction stream, Single Data stream)
3.5.1.1.4. Architecture MIMD (Multiple Instructions stream, Multiple Data stream)
3.5.1.2. Classification de Duncan
3.5.2.1. Architectures synchrones
3.5.2.2. Architectures asynchrones
3.5.2.3. Architectures mixtes
3.6. Modèles de programmation parallèle
3.6.1. Parallélisme de données
3.6.2. Parallélisme de contrôle
3.7. Etapes de développement d’une application exécutée sur une architecture parallèle
3.8. Conclusion
Chapitre 4 : L’architecture parallèle « PARIR »
4.1. Introduction
4.2. Conception assisté par ordinateur
4.3. Modèles
4.4. Synthèse et Simulation
4.4.1. Validation et vérification de description HDL
4.4.1.1. Simulation fonctionnelle
4.4.2. Synthèse
4.5. Langages de description de matériel
4.6. Parallélisation des données par la décomposition de la table de routage
4.6.1. Terminologie et définitions
4.6.2. Algorithme de décomposition de la table de routage
4.6.3. Procédure d’expansion des préfixes
4.6.4. Analyse des résultats
4.7. Structure de données et algorithme parallèle
4.7.1. Structure de données
4.7.2. Algorithme parallèle
4.8. L’architecture parallèle « PARIR »
4.8.1. Description de l’architecture « PARIR »
4.8.2. Expérimentations et résultats
4.9. Modélisation de notre système
4.9.1. Décomposition du système en modules
4.9.2. Le langage VHDL
4.9.2.1. Flot de conception basé sur le VHDL
4.9.2.2. Organisation d’un modèle VHDL
4.9.2.2.1. Unités de conception
4.9.2.2.2. Entité de conception
4.9.3. Modélisation et simulations des modules de notre système
4.9.3.1. Le sélecteur
4.9.3.2. Le composant de recherche
4.9.3.3. Le système complet
4.10. Conclusion
Chapitre 5 : Solutions logicielles proposées
5.1. Introduction
5.2. Routeur avec une table de routage cache
5.2.1. Structure de la table de routage
5.2.1.1. Table de routage principale
5.2.1.2. Table de routage cache
5.2.2. Algorithme de remplacement des entrés de la table cache (la moins récemment utilisée)
5.2.3. Ordonnancement de la table cache
5.2.4. Expérimentation
5.3. Algorithme de recherche des informations de routage par arbre binaire à contenu dynamique (ABCD)
5.3.1. Description de l’arbre binaire à contenu dynamique (ABCD)
5.3.1.1. Structure des nœuds de l’arbre ABCD
5.3.1.2. Construction de l’arbre ABCD
5.3.2. Algorithme de recherche du plus long préfixe correspondant dans l’arbre ABCD
5.3.3. Expérimentation et résultats
5.4. Conclusion
Chapitre 6 : Conclusion et perspectives
Bibliographie