Hypercube (graphe) - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

Hypercube
Hypercubecubes.svg

Notation Qn ou Hn
Nombre de sommets 2n
Nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'arêtes 2n-1n
Distribution des degrés n-régulier
Diamètre (Dans un cercle ou une sphère, le diamètre est un segment de droite passant par le centre et limité par les points du cercle ou de la sphère. Le diamètre est aussi...) n
Maille 4
Coefficient (En mathématiques un coefficient est un facteur multiplicatif qui dépend d'un certain objet, comme une variable (par exemple, les coefficients d'un polynôme),...) de clustering 0
Automorphismes 2nn!
Nombre chromatique 2
Propriétés Hamiltonien
Distance-unité
Graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) de Cayley
Symétrique
Distance-régulier
Utilisation Machines parallèles

Les hypercubes, ou n-cubes, forment une famille de graphes. Dans un hypercube (En géométrie, un hypercube est un analogue n-dimensionnel d'un carré (n = 2) et d'un cube (n = 3). C'est une figure fermée, compacte, convexe constituée de...) Qn, chaque sommet porte une étiquette de longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus éloignées. Lorsque l’objet est filiforme ou en forme de lacet, sa longueur est celle de l’objet complètement...) n sur un alphabet A = {0,1}, et deux sommets sont adjacents si leurs étiquettes ne diffèrent que d'un symbole. C'est le graphe squelette (Le squelette est une charpente animale rigide servant de support pour les muscles. Il est à la base de l'evolution des vertébrés. Celui ci leur a fourni un avantage...) de l'hypercube, un polytope (En géométrie, un polytope est la généralisation à toutes dimensions de la notion de polygone pour deux dimensions et de polyèdre pour trois...) n-dimensionnel, généralisant la notion de carré (Un carré est un polygone régulier à quatre côtés. Cela signifie que ses quatre côtés ont la même longueur et ses quatre angles la même mesure. Un carré est à la...) (n = 2) et de cube (En géométrie euclidienne, un cube est un prisme dont toutes les faces sont carrées. Les cubes figurent parmi les solides les plus...) (n = 3). Dans les années 1980, des ordinateurs furent réalisés avec plusieurs processeurs connectés selon un hypercube : chaque processeur (Le processeur, ou CPU (de l'anglais Central Processing Unit, « Unité centrale de traitement »), est le composant de l'ordinateur qui...) traite une partie des données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) et ainsi les données sont traitées par plusieurs processeurs à la fois, ce qui constitue un calcul parallèle (En informatique, le calcul parallèle consiste en l'exécution simultanée d'une même tâche, partitionnée et adaptée afin de pouvoir être répartie entre plusieurs processeurs...). L'hypercube est couramment introduit pour illustrer des algorithmes parallèles, et de nombreuses variantes ont été proposées, soit pour des cas pratiques liés à la construction de machines parallèles, soit comme objets théoriques.

Construction

L'hypercube Q1 consiste en deux sommets d'étiquettes 0 et 1 ; les étiquettes de ces sommets étant différentes par un seul symbole, ils sont donc reliés. Pour passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques Brisson (1723-1806) en 1760.) à la dimension (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur, ou bien son diamètre si c'est une pièce de...) supérieure, on fabrique une copie du graphe : à la partie d'origine, on rajoute le symbole 1, et sur la partie copiée le symbole 0 ; chaque sommet de la partie d'origine est ensuite relié à son équivalent dans la copie. Ainsi, Q2 consiste en quatre sommets étiquetés 00, 01, 10 et 11. L'illustration ci-dessous montre en rouge (La couleur rouge répond à différentes définitions, selon le système chromatique dont on fait usage.) les arêtes connectant les sommets d'origine à leurs équivalents dans la copie, et l'exemple se poursuit jusqu'à Q3 et Q4. Cette méthode de construction est récursive, puisque pour construire Qn on se fonde sur Qn − 1.

Hypercube-dim1.PNGHypercube-dim2.PNGHypercube-dim3.PNGHypercube-dim4.PNG

On peut aussi définir Qn comme le produit cartésien (En mathématiques, le produit cartésien de deux ensembles X et Y est l'ensemble de tous les couples, dont la première composante appartient à X et la seconde à Y. On généralise facilement la notion de produit cartésien binaire à celle...) de n graphes complets K2, soit :

Q_n = Q_{n-1} \square K_2 = Q_{n-2} \square K_2 \square K_2 = ... = \underbrace{K_2 \square K_2 \square ... \square K_2}_{n \text{ fois}}

Enfin, on peut construire le graphe directement en appliquant sa définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.). On dispose 2n sommets, et chacun a une étiquette unique dans l'espace vectoriel (En algèbre linéaire, un espace vectoriel est un ensemble muni d'une structure permettant d'effectuer des combinaisons linéaires.) {Z2}n, c'est-à-dire une étiquette de la forme (x_1,x_2,...,x_n), x_i \in \{0,1\}. Deux sommets sont reliés par une arête s'ils diffèrent exactement sur un symbole de leurs étiquettes, soit formellement pour le graphe G = (V,E) :

\exists e_{uv} \in E \Longleftrightarrow u = \{x_1, ..., x_{i-1}, x_i, x_{i+1}, ..., x_n\}, v = \{x_1, ..., x_{i-1}, \bar{x_i}, x_{i+1}, ..., x_n\}

Le graphe hypercube Q3 est le graphe hexaédrique et Q4 est le graphe tesseract.

Utilisations

Architectures de machines parallèles

L'addition (L'addition est une opération élémentaire, permettant notamment de décrire la réunion de quantités ou l'adjonction de grandeurs extensives de...) de 8 nombres en séquentiel (haut) et en parallèle (bas). Les étapes sont numérotées en rouge.

Pour avoir une idée du gain en performances en utilisant des machines parallèles, considérons l'addition de N nombres. Sur une machine séquentielle, on additionne le premier nombre avec le second, puis on rajoute le troisième, etc., Au total ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire une somme. Exemple : "Le total des dettes". En...), N − 1 étapes sont nécessaires. Sur une machine parallèle, chaque processeur réalise l'addition d'une paire (On dit qu'un ensemble E est une paire lorsqu'il est formé de deux éléments distincts a et b, et il s'écrit alors :) de nombres en une étape, puis les résultats de deux paires sont additionnés, etc. Au total, 1 + log2N étapes sont nécessaires. Ainsi, pour 1 000 nombres, une machine séquentielle utilisera 999 étapes tandis qu'il n'en faut que 11 sur une machine parallèle ; un autre exemple est illustré ci-contre. Le gain est encore plus significatif pour d'autres opérations, par exemple une instance d'inversion de matrice peut nécessiter 40 000 étapes sur une machine séquentielle contre 61 sur une machine parallèle.

Au début des années 1960, des idées furent proposées pour concevoir un ordinateur (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques permettant de manipuler des données sous forme binaire, ou...) parallèle avec une architecture (Architectures est une série documentaire proposée par Frédéric Campain et Richard Copans, diffusé sur Arte depuis 1995.) en hypercube : « il y a 2n modules, chacun connecté directement à n autres ; en particulier, chaque module est placé sur le sommet d'un cube n-dimension, et les arêtes de ce cubes sont les câbles ». Les justifications dans le choix de l'hypercube peuvent paraître faible au regard des connaissances actuelles sur les familles de graphes, mais il s'avère que l'hypercube a de nombreuses propriétés utiles : il est arc-transitif et distance-transitif, ce qui implique que toutes ses arêtes jouent le même rôle et que tous ses sommets ont les mêmes propriétés de distance. Par ailleurs, le compromis entre le degré (Le mot degré a plusieurs significations, il est notamment employé dans les domaines suivants :) des sommets et la distance entre eux reste raisonnable, et la navigation (La navigation est la science et l'ensemble des techniques qui permettent de :) peut se faire de façon délocalisée, ce qui est une des principales raisons citées à l'origine. En résumé, les propriétés de transitivité permettent d'obtenir une égalité entre les processeurs, et la communication (La communication concerne aussi bien l'homme (communication intra-psychique, interpersonnelle, groupale...) que l'animal (communication intra- ou inter- espèces) ou la...) entre les processeurs peut-être rapide (distance faible) en ayant besoin (Les besoins se situent au niveau de l'interaction entre l'individu et l'environnement. Il est souvent fait un classement des besoins humains en trois grandes catégories : les besoins primaires, les besoins secondaires et les besoins...) de peu d'informations (délocalisé).

Vingt ans se sont écoulés entre les idées du début des années 1960 et la première production, avec le Cosmic Cube de Caltech (64 processeurs Intel 8086/86 embarquant chacun 128Kb de mémoire) en 1983. De nombreuses autres machines sont alors produites, comme les Ametek série 2010, les Connection Machine CM-1/CM-2, les nCUBE et les iPSC d'Intel. De nombreuses études sur les performances des machines parallèles utilisant une architecture (L’architecture peut se définir comme l’art de bâtir des édifices.) en hypercube sont réalisées au laboratoire national d'Oak Ridge sous le contrat DE-AC05-84OR21400. En effet, ce laboratoire créé à l'origine pour le Projet (Un projet est un engagement irréversible de résultat incertain, non reproductible a priori à l’identique, nécessitant le concours et...) Manhattan (Manhattan est l'une des cinq circonscriptions (borough) de la ville de New York (les quatre autres étant The Bronx, Queens, Brooklyn et Staten Island). La circonscription de Manhattan se...) (conception de la première bombe atomique) s'est reconverti sur des sujets tels que la sécurité nationale et les supercalculateurs. Parmi les modèles étudiés figurent les Intel iPSC/860, iPSC/1 et iPSC/2, ainsi que les nCUBE 3200 et 6400 ; les caractéristiques de ces machines sont résumées ci-dessous.

Configurations de supercalculateurs avec architectures en hypercube
iPSC/860 iPSC/2 iPSC/1 N6400 N3200
Nombre de nœuds 128 64 (max 128) 64 (max 128) 64 (max 8192) 64 (max 1024)
Processeur du nœud Intel i860 Intel 80286/387 Intel 80386/287 64-bit 32-bit
Fréquence (En physique, la fréquence désigne en général la mesure du nombre de fois qu'un phénomène périodique se reproduit par...) d'horloge 40 MHz 16 MHz 8 MHz 20 MHz 8 MHz
Mémoire (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir d'une information.) par nœud 8M 4M (max 16M) 512K (max 4.5M) 4M (max 64M) 512K
Débit (Un débit permet de mesurer le flux d'une quantité relative à une unité de temps au travers d'une surface quelconque.) nominal 22 Mbps 22 Mbps 10 Mbps 20 Mbps 8 Mbps
Système d'exploitation NX V3.2 XENIX XENIX Vertex v2.0 Vertex 2.3

Les performances précises de ces processeurs peuvent être trouvées dans les rapports d'Oak Ridge. Au niveau de l'analyse des performances pour la communication, il est préférable d'utiliser un modèle à coût linéaire plutôt qu'à coût constant. Autrement dit, on ne peut pas considérer qu'envoyer un message (La théorie de l'information fut mise au point pour déterminer mathématiquement le taux d’information transmis dans la communication d’un message par un canal de communication, notamment en présence de parasites...) m ait un coût en temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) fixe C(m) = k quelle que soit la longueur du message : on considère plutôt que le coût en temps est fonction de la longueur du message, et qu'initier la transmission a également un coût α, ce qui entraîne le modèle C(m) = α + β * | m | . Le coût α est significatif par rapport à β : cela prend par exemple prend 697µs pour établir la communication dans un iPSC/2, mais seulement 0.4µs pour chaque bit transmit.

Algorithmes parallèles

Répartir les données sur un hypercube

Division (La division est une loi de composition qui à deux nombres associe le produit du premier par l'inverse du second. Si un nombre est non nul, la fonction "division par ce nombre" est la réciproque de la fonction "multiplication...) de données sur un hypercube
On souhaite appliquer un filtre (Un filtre est un système servant à séparer des éléments dans un flux.) sur une image.
L'image est découpée en zones égales.
On assigne à chaque zone le processeur de l'hypercube qui la prendra en charge (La charge utile (payload en anglais ; la charge payante) représente ce qui est effectivement transporté par un moyen de transport donné, et qui donne lieu à un paiement ou un bénéfice non pécuniaire pour être transporté.).
Pour ces 16 zones, on utilisera l'hypercube Q4.
Chaque processeur de Q4 effectuera les opérations sur une partie de l'image.

De nombreuses informations sur les algorithmes pour des architectures en hypercubes à la fin des années 80 furent publiées dans la troisième conférence Hypercube Concurrent Computers and Applications (« Ordinateurs concurrents en hypercube et applications »). Utiliser une machine parallèle n'augmente pas automatiquement la performance d'un algorithme : non seulement les algorithmes doivent être conçus de façon à tirer profit de l'architecture, mais les données ne peuvent pas toujours être partitionnées pour être traitées par différents processeurs, et ces processeurs ont également besoin de communiquer. Dans l'exemple de l'addition, le coût de communication était considéré comme négligeable, et ceci est l'hypothèse que nous conserverons par la suite : en effet, les propriétés de la machine (temps de communication, lecture/écriture, ...) sont généralement ignorés dans l'analyse des algorithmes, et on se concentre sur les dépendances entre les données et les façons de rendre le calcul parallèle sur un hypercube.

Une des opérations les plus courantes en traitement d'image consiste à utiliser un filtre linéaire, c'est-à-dire à appliquer une matrice de convolution. Pour bénéficier de l'architecture en hypercube, l'image doit être divisée en zones égales, et chaque zone assignée à un processeur. Mudge et Abdel-Rahman ont suggéré de considérer l'image comme étant une table de Karnaugh utilisant le code de Gray, ainsi que sur l'exemple ci-contre : si on considère une zone de l'image et ses coordonnées dans la table, alors on obtient directement le processeur auquel l'assigner. Par ailleurs, l'utilisation du code de Gray conserve l'adjacence : deux zones adjacentes dans l'image seront placées sur deux processeurs adjacents, sauf pour les coins. Le filtre, tel que celui de Sobel, est appliqué par chaque processeur à la zone qui lui est assigné. Si le filtre a besoin de certains pixels dépassant la zone disponible à un processeur, il peut la demander au processeur voisin en utilisant les propriétés d'adjacence ; pour des coûts plus faibles en communication, chaque processeur peut également avoir une zone de l'image dont la taille correspond à celle nécessaire pour le traitement plutôt qu'à une partition stricte.

Réutilisation d'algorithmes par plongements

Un plongement permet à ce qu'un réseau (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des informations. Par analogie avec un filet (un réseau est un « petit rets »,...) soit simulé par un autre : aux sommets du réseau d'origine sont associés des sommets dans le réseau simulant, et deux sommets voisins sont séparés par un chemin. Ainsi, un algorithme conçu spécialement pour un réseau peut être réutilisé dans un autre grâce à un plongement. On s'intéresse donc à deux cas : réutiliser des algorithmes sur des hypercubes (1), ou utiliser des algorithmes pour l'hypercube dans d'autres réseaux (2). Autrement dit, l'hypercube est soit un réseau simulant (1), soit un réseau simulé (2). La qualité d'un plongement permet de savoir quelles sont les différentes pertes en performance de l'algorithme. Pour cela, on considère plusieurs facteurs :

  • Congestion ( La congestion est l'augmentation subite de la quantité de sang contenue dans les vaisseaux d'un organe ou d'une partie d'organe. La congestion d'un réseau informatique est la condition dans laquelle une augmentation du...). Elle donne le ralentissement (Le signal de ralentissement (de type SNCF) annonce une aiguille (ou plusieurs) en position déviée qui ne peut être franchie à la vitesse normale de la ligne.) si plusieurs arrêtes du réseau simulé sont utilisées simultanément : elle mesure le nombre d'arêtes du réseau simulé qui sont associées à une seule arête dans le réseau simulant, et ainsi une congestion de 2 indique que le réseau simulant aura besoin de 2 étapes pour transporter les messages que le réseau simulé pouvait avoir en une étape.
  • Dilatation (La dilatation est l'expansion du volume d'un corps occasionné par son réchauffement, généralement imperceptible. Dans le cas d'un gaz, il y a dilatation à pression constante ou maintien du volume et augmentation de la pression.). Elle peut-être considérée comme le ralentissement des communications : elle mesure l'augmentation de la distance entre deux sommets dans le réseau simulant par rapport au simulé, et ainsi une dilatation de 2 signifie que toute communication qui se faisait en une étape en prendra maintenant 2.
  • Charge. Elle indique le ralentissement pour le calcul sur un processeur : elle donne le nombre de sommets du réseau simulé associés à un seul sommet dans le réseau simulant

Pour l'hypercube comme réseau simulant, toute grille ( Un grille-pain est un petit appareil électroménager. Une grille écran est un élément du tube de télévision. Une grille d'arrêt est un élément du...) à deux dimensions a un plongement avec une dilatation d'au plus 2 et une expansion minimale, une grille à trois dimensions a une dilatation entre 2 et 5, et l'arbre (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en général au delà de sept mètres. Les arbres acquièrent une structure rigide...) binaire complet à 2n − 1 nœuds a un plongement de dilatation 1 sur Qn + 1.

Parallélisme automatique (L'automatique fait partie des sciences de l'ingénieur. Cette discipline traite de la modélisation, de l'analyse, de la commande et, de la régulation des systèmes dynamiques. Elle a pour fondements théoriques les mathématiques, la théorie du...)

Si un programme utilise plusieurs tâches et que l'on a des informations sur la façon dont ces tâches communiquent, alors il peut être possible de faire bénéficier le programme d'une machine parallèle. En effet, la structure de la communication des tâches définie un graphe, et celui-ci peut être simulé entre autres par un hypercube en cherchant un plongement, tel qu'étudié dans la section précédente. Dans l'autre cas extrême, si toute tâche communique fréquemment avec toutes les autres, alors les communications sont données par un graphe complet (Un graphe complet est un graphe dont les sommets sont tous reliés deux à deux par une arête. Dans un graphe G, on nomme clique un sous-graphe complet de G, c'est-à-dire une...) et la simulation par une machine parallèle est peu performante. Des solutions intermédiaires ont été développées s'il n'y a pas d'informations sur la communication des tâches mais qu'elle se fait à fréquence est modérée.

Page générée en 0.102 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique