| Titre : | Plongement d'une bonne qualité du quad tree dans une architecture parallèle PANCAKE |
| Auteurs : | MOHAMED LAMINE HACHANI, Auteur ; Mohamed Faouzi Zerarka, Directeur de thèse |
| Type de document : | Monographie imprimée |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2015 |
| Format : | 1 vol. (76 p.) / 30 cm |
| Langues: | Français |
| Résumé : |
Plongement de bonne qualité du Quad tree dans une architecture parallèle Pancake Introduction généraleLes structures de données hiérarchiques sont séduisantes à cause de leur clarté conceptuelle, de la simplicité de leur implantation ainsi que des algorithmes inhérents à leur manipulation. Et comme le sont les arbres quaternaires, deviennent de plus en plus comme moyen de représentations des techniques importantes dans les domaines du graphisme sur ordinateur, la manipulation d’images, la géométrie computationnelle, les systèmes d’information géographiques et la robotique, pour n’en nommer que quelques- unes. Toutes sont basées sur la décomposition hiérarchique, c’est-à-dire récursive, de l’entité à décrire, à stocker, à questionner et à manipuler. Nous nous proposons d’étudier cette classe spécifique de structures de données hiérarchiques. On parlera plus spécifiquement d’arbre quaternaire. Avec la complexité toujours croissante des besoins en calculs, ont se mit à rechercher des moyens de les automatiser avec laquelle la puissance des machines s’accroit. Cette explosion de la puissance des processeurs a ouvert la porte à de nouveaux horizons de recherche, dont le parallélisme en informatique est une conséquence directe. Le parallélisme apporte une nouvelle réponse en termes de performance.il permet souvent de traiter des problèmes plus gourmands en calcul, plus rapidement. Pour la résolution d’un seul problème avec une grande performance plusieurs processeurs doivent coopérer entre eux même, afin d’assurer une bonne communication ces processeurs doivent utiliser un réseau d’interconnexion. Les ordinateurs parallèles à base de réseaux d’interconnexion ont une topologie simple, hybride ou hypercube, ainsi que leurs variations. Les graphes de Cayley sont considérer dans la littérature comme des topologies très populaire et attractive par leurs propriétés : de symétrie, d’hamiltonicité, de connectivité, de tolérance aux pannes….etc. Le pancake est une variation du star graphe appartenant à la classe de Cayley disposant lui aussi de propriétés très attractives et d’un diamètre très réduit. Plusieurs algorithmes qui résolvent un ensemble de problèmes ont été conçus pour une topologie A au lieu de concevoir d’autres algorithmes qui résolvent ces mêmes problèmes pour une autre topologie B, il serait souhaitable Introduction générale Plongement de bonne qualité du Quad tree dans une architecture parallèle Pancake de trouver un moyen de traduire ces algorithmes. Ceci est accompli par le plongement de A vers B. L’objectif principal de notre travail est de développé cette idée dans le cas d’une topologie source arbre quaternaire et d’une topologie hôte Pancake. Ce mémoire est composé de cinq chapitres, En premier, un survol sur les notions d’architectures parallèle et les réseaux d’interconnexion simples et hybrides. Dans le second chapitre nous étudierons les principales topologies des architectures Source et Hôte basant sur l’architecture arbres quaternaires et Pancake. Le troisième chapitre consiste à étudier les définitions du plongement et ces mesures de qualité. Le chapitre quatre concerne la conception du système. Dans ce chapitre, nous focalisons sur la conception de l'application, dont on propose une architecture globale et détaillé. Le chapitre cinq contient la phase de test et mise en œuvre du système. Dans ce chapitre, nous décrivons les différents outils et langages de programmation utilisés, et de présenter quelques résultats expérimentaux. En fin, Nous clôturons ce mémoire par une conclusion générale dans laquelle nous résumons notre solution et exposant quelques perspectives futures. |
| Sommaire : |
Sommaire
Introduction générale Chapitre I. Machines parallèles et Réseaux d’interconnexions Partie I : Machines parallèles 1 I.1 Introduction 1 I.2 Classification d’architecture parallèle 1 I.2.1. Le modèle SISD 2 I.2.2. Le modèle SIMD 2 I.2.3. Le modèle MISD. 2 I.2.4. Le modèle MIMD 2 I.2.4.1 MIMD avec mémoire partagé 3 I.2.4.2 MIMD avec mémoire distribué 4 I.3 Les systèmes à réseaux de communication 4 I.3.1 Le réseau d’interconnexion 4 I.3.2 Matrice de point de croisement 5 I.4Conclusion 6 Partie 2 : Architecture des machines à base de réseau d’interconnexion 7 II.1 réseaux d’interconnexion simple 7 II.1.1 Introduction 7 II.1.2 Architecture vectorielle 7 1.2.1 Les vecteurs 7 1.2.2. Réseaux d’interconnexions linéaires et anneaux 8 1.2.3 Maille (composition de vecteurs) 9 1.2.3.1 Propriété de la maille 9 II.1.3 Architecture arbre 10 1.3.1 Les structures de données 10 1.3.1.1 Structures de données statiques 10 1.3.1.2 Structures de données dynamiques 10 1.3.2 Les arbres 11 1.3.2.1 Les arbres particuliers 11 2.1.1 Définition d’un arbre 11 2.1.2 Arité d’un arbre 11 1.3.2.2 Types des arbres 12 2.2.1 Arbre binaire 12 2.2.2 Arbre binaire complet 12 2.2.3 Arbre non enraciné 13 2.2.4 Arbres enracinés 13 II.2 réseaux d’interconnexion hybride 14 II.2.1. Introduction 14 II.2.2. La maille d’arbres 14 II.2.3. Les maille d’arbres de dimension R 16 2.3.1 Propriétés des mailles d’arbres de dimension R 17 2.3.2 Variation de la maille d’arbres 17 II.2.4 Star Graph 18 2.4.1 Définition 18 2.4.2 Construction de star graph 19 2.4.3 Propriétés du star graph 20 2.4.4 Les avantages de la star graph 21 2.4.5 Les inconvénients de la star graph 21 III Conclusion 22 Chapitre II : Étude sur l’architecture source et hôte Partie I : Architecture source Arbre quaternaire (Quadtree) 23 I.1 Introduction 23 I.2 Arbre quaternaire 23 I.2.1 Définition 23 I.2.2 Terminologie 24 I.2.3 Arbre quaternaire à point 25 I.2.4 Arbre quaternaire à région 26 I.2.5 Arbre quaternaire à arêtes 27 I.2.6 Arbre B 27 I.2.7 L'arbre k-d 27 I.2.8 Arbre R 28 I.2.9 Propriétés et Représentation de l'arbre quadtree 28 2.9.1 Nombre minimum de nœuds 28 2.9.2 Nombre maximal de nœuds 29 I.3 L’arbre hyperquaternaire 29 I.3.1 Les arbres hyperquaternaires de points 29 I.3.2 Arbre hyperquaternaire de points plein 30 I.3.3 Un arbre hyperquaternaire de points complet 30 I.3.4 Arbre hyperquaternaire avec nœuds externes 31 I.4 Synthèse sur les arbres étudiés 34 I.5 Conclusion 34 Partie II : Architecture Hôte Pancake 35 II.1 introduction 35 II.2 Définition 35 II.3 Propriété du Pancake 37 II.3 Conclusion Chapitre III : Le plongement 41 I.1 Introduction 42 I.2 Définitions 43 I.3 Type de plongement 43 3.1 Plusieurs pour un (many by one) 43 3.2 Un pour plusieurs (one by many) 43 3.3 Un pour un (one by one) 43 I.4 Les mesures de qualité d’un plongement 44 4.1 La dilation 44 4.2 La congestion 44 4.3 L’expansion 44 4.4 Le facteur de charge 45 I.5 Les étapes de plongement 45 5.1 Calcul de la cardinalité du graphe source 45 5.2 Plongement des nœuds 45 5.3 Plongement des arêtes 45 I.6 Etat de l’art de plongement 45 6.1 Plongement d’un anneau dans un pancake 46 6.2 Plongement d’une grille dans un pancake 46 6.3 Plongement d’un arbre binaire complet dans un pancake 46 6.4 Plongement d’un arbre quaternaire dans un pancake 47 I.7 Conclusion 48 Chapitre IV : Conception I Introduction 49 II Conception globale du système 49 III Architecture globale de système 51 IV Conception détaillée 52 IV.1 Les composants du système 52 1.1 Modélisation de L’architecture source arbre quaternaire 52 1.2 Modélisation du graphe de l’architecture hôte Pancake 53 1.2.1 Modélisation de l’architecture hôte pancake 54 1.3 Le modèle de plongement « One By One » 55 1.3.1Plongements one by one des nœuds du quadtree dans pancake 55 1.3.2 Plongements one by one des arêtes du quadtree dans pancake 58 1.4 Les fonctions des mesures de qualité 60 V Conclusion 61 Chapitre V : Implémentation I. Introduction 62 II Choix du langage de programmation 62 II.1 Présentation du logiciel de programmation Visual Studio 2013 62 II.2 Langage de programmation C# 62 III Réalisation de système 63 III.1simulation des architectures 63 III.1.1 architecture source arbre 63 III.1.2 Architecture hôte pancake 65 III.2 Émulation du plongement 68 III.2.1Plongement des nœuds 68 III.2.2 Plongement des arêtes 71 III.3 Mesure de qualité 71 IV Présentation de l’application 72 IV.1 Environnement de développement 72 IV.2 présentation des fenêtres 72 2.1 Fenêtre de bienvenue 72 2.2 Fenêtre Principale (Simulation des architectures) 73 2.3 Fenêtre Émulation du plongement 74 2.4 Fenêtre des résultats (mesures de la qualité) 75 V Conclusion 76 Conclusion Générale |
| Type de document : | Mémoire master |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| MINF/15 | Mémoire master | bibliothèque sciences exactes | Consultable |
