AccueilđŸ‡«đŸ‡·Chercher

Hypercube (graphe)

Les hypercubes, ou n-cubes, forment une famille de graphes. Dans un hypercube , chaque sommet porte une étiquette de longueur sur un alphabet , et deux sommets sont adjacents si leurs étiquettes ne diffÚrent que d'un symbole. C'est le graphe squelette de l'hypercube, un polytope n-dimensionnel, généralisant la notion de carré (n = 2) et de cube (n = 3). Dans les années 1980, des ordinateurs furent réalisés avec plusieurs processeurs connectés selon un hypercube : chaque processeur traite une partie des données et ainsi les données sont traitées par plusieurs processeurs à la fois, ce qui constitue un calcul parallÚle. 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.

Hypercube
Image illustrative de l’article Hypercube (graphe)
Q4

Notation Qn ou Hn
Nombre de sommets 2n
Nombre d'arĂȘtes 2n-1n
Distribution des degrés n-régulier
DiamĂštre n
Maille 4
Coefficient de clustering 0
Automorphismes 2nn!
Nombre chromatique 2
Propriétés Hamiltonien
Distance-unité
Graphe de Cayley
Symétrique
Distance-régulier
Utilisation Machines parallĂšles

Construction

L'hypercube consiste en deux sommets d'Ă©tiquettes et ; les Ă©tiquettes de ces sommets Ă©tant diffĂ©rentes par un seul symbole, ils sont donc reliĂ©s. Pour passer Ă  la dimension supĂ©rieure, on fabrique une copie du graphe : Ă  la partie d'origine, on rajoute le symbole , et sur la partie copiĂ©e le symbole ; chaque sommet de la partie d'origine est ensuite reliĂ© Ă  son Ă©quivalent dans la copie. Ainsi, consiste en quatre sommets Ă©tiquetĂ©s , , et . L'illustration ci-dessous montre en rouge les arĂȘtes connectant les sommets d'origine Ă  leurs Ă©quivalents dans la copie, et l'exemple se poursuit jusqu'Ă  et . Cette mĂ©thode de construction est rĂ©cursive, puisque pour construire on se fonde sur .

→ → →

On peut aussi définir comme le produit cartésien[A 1] de graphes complets , soit :

Enfin, on peut construire le graphe directement en appliquant sa dĂ©finition. On dispose sommets, et chacun a une Ă©tiquette unique dans l'espace vectoriel[D 1] , c'est-Ă -dire une Ă©tiquette de la forme . 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 :

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

Propriétés

Fondamentales

Un cycle dans un hypercube constituĂ© de deux hypercubes . En rouge, un chemin dans le premier hypercube , en bleu les arĂȘtes le reliant Ă  sa copie et en vert le chemin dans la copie. Le cycle est de longueur 2 + 2 + 2 = 6, qui est pair.
  • DegrĂ©. Deux sommets sont connectĂ©s s'ils diffĂšrent exactement sur un symbole de leurs Ă©tiquettes. Comme l'Ă©tiquette a symboles, chaque sommet est connectĂ© Ă  exactement voisins : tout sommet a donc degrĂ© , autrement dit le graphe est -rĂ©gulier.
  • Nombre de sommets. Par la construction rĂ©cursive, on voit que pour passer de Ă  , il faut faire une copie du graphe, autrement dit le nombre de sommets est doublĂ©. Si est le nombre de sommets du graphe , on obtient ainsi , et le premier cas est ; en dĂ©roulant la rĂ©currence, on obtient , c'est-Ă -dire que le graphe a sommets.
  • DiamĂštre[A 1]. Une des propriĂ©tĂ©s du produit cartĂ©sien est que le diamĂštre de est Ă©gal Ă  . Comme est le produit cartĂ©sien de graphes complets , son diamĂštre est Ă©gal Ă  .
Les sommets de l'hypercube sont répartis en deux ensembles. Ceux en vert ont un nombre impair de 1 et ceux en rouge un nombre pair. Le voisin d'un sommet est nécessairement de couleur différente, donc le graphe est biparti.
  • Cycles. Par construction, le plus petit cycle correspond Ă  , qui est isomorphe au cycle (i.e. le cycle de longueur 4). Le graphe est formĂ© par deux graphes : si l'on souhaite un cycle de longueur supĂ©rieur Ă  4 dans , alors on choisit arĂȘtes dans un des deux graphes , arĂȘtes dans l'autre et 2 arĂȘtes supplĂ©mentaires pour naviguer entre les deux graphes, ce qui porte le total d'arĂȘtes Ă  ; ce mĂ©canisme est illustrĂ© dans la figure ci-contre avec un cycle de longueur 6, et permet de prouver que les cycles dans un hypercube sont toujours de longueur paire.
  • Nombre chromatique. Un graphe est biparti si et seulement s'il ne contient pas de cycle impair, et il dĂ©coule donc de la propriĂ©tĂ© prĂ©cĂ©dente que l'hypercube est biparti. Un graphe biparti est celui pouvant ĂȘtre coloriĂ© avec deux couleurs, et ainsi le nombre chromatique de l'hypercube est . Pour voir qu'un graphe est biparti, il suffit de trouver un schĂ©ma afin de ranger chaque sommet dans un ensemble ou , de façon telle que tout sommet d'un ensemble ait comme voisins uniquement des sommets de l'autre ensemble. Dans le cas de l'hypercube[D 2], l'ensemble peut ĂȘtre constituĂ© des sommets dont l'Ă©tiquette a un nombre pair de 1, et est l'ensemble de sommets dont l'Ă©tiquette a un nombre impair de 1. Un sommet Ă©tant connectĂ© Ă  tous ceux dont l'Ă©tiquette diffĂšre exactement d'un symbole, il en dĂ©coule que le nombre de 1 des voisins d'un sommet est soit supĂ©rieur soit infĂ©rieur : ainsi, un sommet pair sera connectĂ© Ă  des sommets impairs, et vice-versa.
  • Planaire. L'hypercube est planaire (c'est-Ă -dire pouvant se dessiner sur un plan sans croiser deux arĂȘtes) uniquement pour . Pour , plusieurs arĂȘtes vont se croiser mais dĂ©terminer le nombre minimum d'arĂȘtes qui vont se croiser est un problĂšme NP-complet[D 2] ; on sait par exemple qu'il y en a 8 pour .
  • EulĂ©rien. Un graphe a un chemin eulĂ©rien si et seulement si tout sommet est de degrĂ© pair. Comme est -rĂ©gulier, il en rĂ©sulte qu'il n'y a un chemin eulĂ©rien que pour pair.
  • Hamiltonien. Ă©tant un cycle, il est aussi un circuit hamiltonien. Pour construire un circuit hamiltonien dans , on sait qu'il y a un circuit hamiltonien dans le graphe d'origine et dans sa copie : supprimons une arĂȘte dans chacun de ces circuits et raccordons les sommets ainsi libĂ©rĂ©s pour crĂ©er un circuit hamiltonien dans l'ensemble. Ce processus est illustrĂ© ci-dessous pour et . Le nombre exact de cycles hamiltoniens est donnĂ© ci-dessous[D 2] pour les premiers hypercubes ; au-delĂ , l'estimation la plus prĂ©cise quant au nombre de circuits hamiltoniens dans est donnĂ©e[D 3] par :
    .

Nombre de cycles hamiltoniens dans l'hypercube[D 2]
n Sans compter les cycles isomorphes En comptant tous les cycles
2 1 1
3 1 6
4 9 1344
5 275 065 906 545 760
  • Graphe de Hamming. Un graphe de Hamming est le graphe obtenu par produit cartĂ©sien de graphes complets . L'hypercube Ă©tant obtenu par produit cartĂ©sien de copies de , il dĂ©coule de la dĂ©finition que tout hypercube est isomorphe Ă  . Une dĂ©finition alternative d'un graphe de Hamming montre le rapport direct avec celle utilisĂ©e pour introduire l'hypercube : est le graphe dont les sommets sont , l'ensemble des mots de longueur sur un alphabet , oĂč . Deux sommets sont adjacents dans s'ils sont Ă  une distance de Hamming de 1, c'est-Ă -dire si leurs Ă©tiquettes ne diffĂšrent que d'un symbole.
  • Distance-rĂ©gulier. Un hypercube est un graphe distance-rĂ©gulier[B 1] et son vecteur d'intersection est .
  • Diagramme de Hasse. L'hypercube est isomorphe au diagramme de Hasse d'une algĂšbre de Boole Ă  n Ă©lĂ©ments.
  • Reconnaissance. Étant donnĂ© une liste d'adjacence, on peut savoir en temps et espace linĂ©aire si le graphe qu'elle reprĂ©sente est un hypercube[A 2].
  • Code de Gray[C 1]. Les Ă©tiquettes ordonnĂ©es des sommets dans un cycle hamiltonien sur dĂ©finissent le code de Gray sur bits. De plus, ce code suit une construction similaire Ă  celle de l'hypercube : les mots de bits sont dĂ©terminĂ©s en copiant les mots de puis en rajoutant 0 devant l'original, 1 devant la copie, et en inversant les mots de la copie.
  • Distance-unitĂ©. L'hypercube est un graphe distance-unitĂ© : il peut s'obtenir Ă  partir d'une collection de points du plan euclidien en reliant par une arĂȘte toutes les paires de points Ă©tant Ă  une distance de 1.

Groupe d'automorphisme

Le groupe d'automorphisme de l'hypercube est d'ordre . Il est isomorphe au produit en couronne des groupes symĂ©triques et : [D 4]. Le produit en couronne de A par B Ă©tant dĂ©fini comme le produit semi-direct oĂč est l'ensemble des fonctions de B dans A et oĂč B agit sur par dĂ©calage d'indice :

pour et .

L'hypercube est un graphe arc-transitif : son groupe d'automorphisme agit transitivement sur l'ensemble de ses arcs. Étant donnĂ© deux arĂȘtes e1 = u1v1 et e2 = u2v2 de G, il existe deux automorphismes et tels que , , et , , , .

L'hypercube est donc a fortiori symĂ©trique. Le groupe agit donc Ă©galement transitivement sur l'ensemble de ses sommets et sur l'ensemble de ses arĂȘtes. En d'autres termes, tous les sommets et toutes les arĂȘtes d'un hypercube jouent exactement le mĂȘme rĂŽle d'un point de vue d'isomorphisme de graphe.

Le graphe hexaédrique () est l'unique graphe cubique symétrique à 8 sommets[D 5]. Le graphe tesseract () est l'unique graphe symétrique régulier de degrés 4 à 16 sommets[A 3].

Graphe de Cayley

L'hypercube est un graphe de Cayley Cay(G, S) avec :

Cela découle d'une propriété plus générale statuant que tous les graphes de Hamming sont des graphes de Cayley[A 4].

Matrice d'adjacence et spectre

La matrice d'adjacence de l'hypercube est définie ci-dessous. Par la définition récursive de l'hypercube, pour passer à la dimension supérieure , on duplique et connecte les sommets d'origine à leur équivalent dans la copie.

0 1
0 0 1
1 1 0

On obtient ainsi la matrice d'adjacence ci-dessous :

00 01 10 11
00 0 1 1 0
01 1 0 0 1
10 1 0 0 1
11 0 1 1 0

Au niveau de la matrice, l'opĂ©ration passant de Ă  se comprend comme suit : les entrĂ©es correspondent Ă  la matrice d'origine, et se trouvent dupliquĂ©es en . Dans les autres entrĂ©es, on connecte chaque sommet Ă  sa copie. Ainsi, la forme gĂ©nĂ©rale de la matrice est donnĂ©e de la façon suivante[D 6], oĂč reprĂ©sente la matrice identitĂ© de dimension :

Pour comprendre l'Ă©volution du spectre de la matrice en fonction de , il faut revenir Ă  la dĂ©finition comme produit cartĂ©sien. Le spectre d'un produit cartĂ©sien est , oĂč est le spectre de et le spectre de ; autrement dit, le spectre est la somme de toutes les paires possibles[A 5]. Sachant que le spectre de est , on en dĂ©duit que le spectre de est : en effet, elles correspondent aux combinaisons , , . Si l'on passe au stade suivant, soit , on a d'un cĂŽtĂ© le spectre de , et de l'autre de : le rĂ©sultat du produit cartĂ©sien est .

On en déduit par récurrence la formule suivante pour le polynÎme caractéristique de la matrice d'adjacence (et donc du graphe):

. Ce polynÎme caractéristique n'admet que des racines entiÚres. Le graphe d'un hypercube est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.

Pour aller d'un sommet à un autre, on utilise à nouveau le fait que deux sommets sont connectés s'ils diffÚrent exactement sur un symbole de leurs étiquettes. Ainsi, un chemin est trouvé en faisant correspondre une à une les coordonnées du sommet de destination avec celui d'origine. Par exemple, pour aller de à , on obtient . Dans le cas général, pour aller de à on obtient :

Notons deux choses. PremiÚrement, la longueur d'un chemin entre deux sommets est le nombre de symboles sur lesquels leurs étiquettes diffÚrent : ainsi, si les étiquettes sont complÚtement différentes, le chemin sera de longueur , ce qui est une autre explication quant au diamÚtre du graphe. DeuxiÚmement, le chemin choisi n'est pas unique : au lieu d'aller de en , on aurait tout d'abord pu passer par avant d'aller en . Le nombre de chemins différents pour aller entre deux sommets est un problÚme de combinatoire : considérons que les sommets diffÚrent sur symboles, combien de façons a-t-on de générer des chemins ? On a choix pour le premier symbole à changer, puis choix pour le second symbole à changer, jusqu'à un seul choix quand il n'y a plus qu'un symbole à changer ; ainsi, le nombre de chemins entre deux sommets différant sur symboles est .

Hypercubes induits

Les chemins entre deux sommets ont d'autres propriĂ©tĂ©s intĂ©ressantes, particuliĂšrement pour les sous-graphes qu'ils dĂ©finissent. Ainsi, l'union des chemins entre deux sommets distants de (i.e. diffĂ©rant de symboles) donne[A 2] l'hypercube . Ceci est illustrĂ© par l'exemple ci-dessous : dans le cas de deux sommets voisins et , il n'y a qu'un chemin et on obtient l'hypercube ; dans le cas oĂč ils sont Ă  distance 2, il y a deux chemins entre eux qui dĂ©finissent , et s'ils sont Ă  distance 3 alors l'union des chemins reprĂ©sente l'ensemble de l'hypercube .

L'union des chemins entre des sommets Ă  distance 
        k
    {\displaystyle k}
 défini 
          Q
            k
    {\displaystyle Q_{k}}
.
L'union des chemins entre des sommets à distance défini .

Le nombre d'hypercubes compris dans est donné par la formule suivante[D 7] :

L'hypercube est aussi un graphe médian, et en particulier le seul graphe médian régulier. On peut donc appliquer la formule suivante des graphes médians[D 7] :

Spanners

Certains types de sous-graphe sont particuliĂšrement utiles en termes de communications. Par exemple, un spanner est un sous-graphe couvrant, c'est-Ă -dire qui contient tous les sommets, mais qui contient moins d'arĂȘtes. Contenir moins d'arĂȘtes peut augmenter les distances entre des sommets du graphe, et l'on distingue ainsi les spanners multiplicatifs, oĂč la distance peut ĂȘtre multipliĂ©e par un facteur , des spanners additifs oĂč la distance peut ĂȘtre augmentĂ©e d'un montant . Dans le cas d'un spanneur additif sur , des rĂ©sultats[D 8] concernent les degrĂ©s du spanneur :

  1. si et , alors le plus petit degré maximal est .
  2. si et est grand, il existe un spanneur de degré moyen au plus .
Pour avoir un spanner 2-additif de on sĂ©lectionne les arĂȘtes satisfaisant une des trois conditions.

De nombreuses Ă©tudes sur les spanners, et des constructions pour des modĂšles gĂ©nĂ©ralisĂ©s de l'hypercube, sont dues Ă  Arthur L. Liestman et Thomas C. Shermer[B 2]. Ils ont en particulier proposĂ© un spanner additif avec un montant oĂč les arĂȘtes sont celles dont les extrĂ©mitĂ©s sont donnĂ©es par les trois conditions suivantes :

Ce processus est illustrĂ© dans l'image ci-contre oĂč les arĂȘtes satisfaisant une des conditions sont surlignĂ©es ; l'ensemble de ces arĂȘtes constitue le spanner. Pour obtenir un chemin entre deux sommets, considĂ©rons que l'on dĂ©marre d'un sommet . On inverse d'abord ses coordonnĂ©es paires, car la condition (1) impose l'existence d'une arĂȘte sur tout sommet commençant par 0 avec une diffĂ©rence sur bit pair. On change ensuite la premiĂšre coordonnĂ©e en 1 grĂące Ă  la condition (3), Ă  partir de quoi on peut inverser toutes les coordonnĂ©es impaires par la condition (2). Si le sommet de destination est alors on est arrivĂ© car on commence par 1 et les coordonnĂ©es paires comme impaires ont pu ĂȘtre inversĂ© ; si le sommet de destination est on utilise une derniĂšre inversion par la condition (3). Le cas oĂč le sommet d'origine est est traitĂ© de façon similaire : inverser les coordonnĂ©es impaires, passer la premiĂšre coordonnĂ©e en 0, inverser les coordonnĂ©es paires, passer la premiĂšre coordonnĂ©e en 1 si nĂ©cessaire. Dans l'image ci-contre, on voit le dĂ©lai de 2 si on cherche un chemin de Ă  : ce qui se ferait normalement directement en une Ă©tape doit se faire en trois Ă©tapes, en passant par et .

Diffusions

Dans le problĂšme de la diffusion (anglais broadcast), un nƓud source souhaite diffuser une information Ă  tous les autres nƓuds. Dans le modĂšle classique, Ă  chaque Ă©tape un nƓud donnĂ© peut transmettre au plus une information, cette information utilisant une arĂȘte et Ă©tant transmise Ă  la fin de l'Ă©tape. Dans ce modĂšle, la diffusion la plus performante est celle oĂč, Ă  chaque Ă©tape, chaque nƓud en contacte un autre, c'est-Ă -dire que le nombre de nƓuds contactĂ©s est doublĂ©. Le nombre d'Ă©tapes minimal est donc ; un graphe pouvant finir une diffusion en Ă©tapes quelle que soit l'origine et en minimisant le nombre d'arĂȘtes est un graphe de diffusion minimale (anglais minimal broadcast graph). Dans le cas oĂč , le nƓud source doit avoir au moins voisins car il doit diffuser Ă  chaque Ă©tape pour faire doubler le nombre de voisins ; la source n'Ă©tant pas fixĂ©e, on obtient que chaque nƓud doit avoir au moins voisins d'oĂč arĂȘtes ( vient du partage de chaque arĂȘte dans un graphe non-orientĂ©), ce qui est prĂ©cisĂ©ment le cas d'un hypercube. Ainsi, l'hypercube est un graphe de diffusion minimale.

Parmi les problĂšmes proches se trouve le commĂ©rage (anglais gossip) oĂč chaque nƓud veut Ă©changer une information avec tous les autres, autrement dit chaque nƓud est la source d'une diffusion. Des cas particuliers s'intĂ©ressent aux variantes locales : par exemple, dans un commĂ©rage 'local', chaque nƓud veut apprendre les messages de ses voisins[D 9].

Utilisations

Architectures de machines parallĂšles

L'addition 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 nombres. Sur une machine sĂ©quentielle, on additionne le premier nombre avec le second, puis on rajoute le troisiĂšme, etc., Au total, Ă©tapes sont nĂ©cessaires. Sur une machine parallĂšle, chaque processeur rĂ©alise l'addition d'une paire de nombres en une Ă©tape, puis les rĂ©sultats de deux paires sont additionnĂ©s, etc. Au total, Ă©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[A 6].

Au dĂ©but des annĂ©es 1960, des idĂ©es furent proposĂ©es pour concevoir un ordinateur parallĂšle avec une architecture en hypercube : « il y a modules, chacun connectĂ© directement Ă  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 »[A 6]. Les justifications dans le choix de l'hypercube peuvent paraĂźtre faibles 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Ă© des sommets et la distance entre eux reste raisonnable, et la navigation 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 entre les processeurs peut ĂȘtre rapide (distance faible) en ayant besoin 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[D 10] 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 (en)[D 11] CM-1/CM-2, les nCUBE (en) et les iPSC d'Intel. De nombreuses études sur les performances des machines parallÚles utilisant une architecture en hypercube sont réalisées au laboratoire national d'Oak Ridge sous le contrat DE-AC05-84OR21400[D 12]. En effet, ce laboratoire créé à l'origine pour le Projet Manhattan (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[D 12]
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 d'horloge 40 MHz 16 MHz 8 MHz 20 MHz 8 MHz
MĂ©moire par nƓud 8M 4M (max 16M) 512K (max 4.5M) 4M (max 64M) 512K
DĂ©bit nominal 22 Mb/s 22 Mb/s 10 Mb/s 20 Mb/s 8 Mb/s
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 ait un coĂ»t en temps fixe 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 . 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.

Répartir les données sur un hypercube

Division de données sur un hypercube
On souhaite appliquer un filtre 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.
Pour ces 16 zones, on utilisera l'hypercube .
Chaque processeur de effectuera les opérations sur une partie de l'image.
Play Pause Stop Précédent Suivant Select

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[A 7] (« 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[D 13], 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Ă©e. 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 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[C 2] :

  • Congestion. Elle donne le ralentissement si plusieurs arĂȘ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. 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 Ă  deux dimensions a un plongement[C 1] 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 binaire complet Ă  nƓuds a un plongement de dilatation 1 sur .

Parallélisme automatique

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Ă©finit 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 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 modĂ©rĂ©e[D 14].

Variantes

L'hypercube Ă©tait trĂšs utilisĂ© pour les architectures de machines parallĂšles, et certaines de ses propriĂ©tĂ©s Ă©taient jugĂ©es perfectibles dans ce cadre. Le principal problĂšme est la croissance d'un hypercube, oĂč le nombre de sommets doit doubler d'une dimension Ă  l'autre : dans une machine, plus de flexibilitĂ© est dĂ©sirable afin de pouvoir ajouter quelques processeurs. Plusieurs aspects sont aussi liĂ©s Ă  sa rĂ©alisation par des circuits Ă©lectroniques. PremiĂšrement, l'hypercube n'est pas planaire et aura donc des chevauchements dans le circuit : en rĂ©duire le nombre simplifie le circuit. DeuxiĂšmement, l'hypercube est dĂ©fini comme un graphe non-orientĂ©, mais « un rĂ©seau basĂ© sur une orientation de utilise la moitiĂ© du nombre de broches et cĂąbles par rapport Ă  »[D 15] : il est donc intĂ©ressant de trouver une orientation conservant des performances similaires. Enfin, il peut ĂȘtre dĂ©sirable de rĂ©duire les distances dans l'hypercube pour les performances en termes de communications.

L'hypercube comme bloc de base

formé de hypercubes , chacun constituant un cluster dont le numéro est encadré.

Un hierarchical cubic network[D 16] est formĂ© de -cubes, oĂč chaque cube est dĂ©signĂ© comme un cluster. Chacun de ces clusters est utilisĂ© comme un bloc de base, et chaque nƓud d'un cluster a un lien supplĂ©mentaire le reliant Ă  un autre cluster ; ces liens sont dĂ©terminĂ©s par l'algorithme suivante pour le graphe composĂ© de -cubes, oĂč dĂ©signe le sommet du cluster et est le complĂ©ment bit Ă  bit de :

Les auteurs montrĂšrent que, Ă  tailles Ă©gales, ce graphe a un diamĂštre d'un quart plus faible que celui de l'hypercube, et la moitiĂ© du nombre de liens. Cependant, dans certaines situations la diffusion est plus lente que sur un hypercube, et avoir un graphe moins dense revient Ă  ĂȘtre plus exposĂ© lorsque des pannes surviennent sur les liens.

Cubes de Fibonacci

Une autre variante ayant Ă©tĂ© depuis particuliĂšrement Ă©tudiĂ©e est le Cube de Fibonacci[D 17]. Les conditions fondamentales du cube de Fibonacci de dimension , notĂ© , sont les mĂȘmes que celles de l'hypercube : chaque sommet porte une Ă©tiquette de longueur sur un alphabet , et deux sommets sont adjacents si leurs Ă©tiquettes ne diffĂ©rent que d'un symbole. Cependant, on rajoute une contrainte : une Ă©tiquette valide ne peut avoir deux consĂ©cutif. Ainsi, ci-dessous, on voit que les cubes de Fibonacci peuvent se retrouver comme sous-graphes des hypercubes en Ă©liminant les Ă©tiquettes contenant deux consĂ©cutifs.

Les cubes de Fibonacci 
        F
          C
            1
        ,
        F
          C
            2
        ,
        F
          C
            3
        ,
        F
          C
            4
    {\displaystyle FC_{1},FC_{2},FC_{3},FC_{4}}
 comme sous-graphes des hypercubes 
          Q
            1
        ,
          Q
            2
        ,
          Q
            3
        ,
          Q
            4
    {\displaystyle Q_{1},Q_{2},Q_{3},Q_{4}}
.
Les cubes de Fibonacci comme sous-graphes des hypercubes .

La construction par rĂ©currence [D 18] peut ĂȘtre dĂ©finie par une grammaire formelle en Ă©nonçant les Ă©tiquettes valides pour les sommets, puis en considĂ©rant le graphe comme le sous-graphe de l'hypercube induit par les sommets valides :

Hypercubes recùblés

Dans le cas oĂč rĂ©duire la distance soit le principal objectif, il est courant d'utiliser des procĂ©dures de recĂąblage comme on le voit encore dans le cas de l'effet petit monde. De nombreuses procĂ©dures ont Ă©tĂ© proposĂ©es, et les plus significatives sont rĂ©sumĂ©es dans le tableau ci-dessous avec leurs performances sur la distance maximale (i.e. le diamĂštre) et moyenne ainsi que le nombre de recĂąblages nĂ©cessaire. Le nom de chacune des procĂ©dures est conservĂ© Ă  partir des articles d'origines, oĂč twisted signifie recĂąblĂ©, et suivi de l'annĂ©e Ă  laquelle la procĂ©dure fut publiĂ©e.

Listes de variantes de l'hypercube par recĂąblage[D 1]. Le temps de routage est toujours en O(n).
Nom DiamĂštre Distance moyenne Nombre d'arĂȘtes recĂąblĂ©es
Hypercube 0
Twisted cube (1987)
Twisted hypercube (1991)
Twisted N-cube (1991)
Generalized twisted cube (1993)
0-Möbius Cube (1995)

Graphe libre d'Ă©chelle par contraction

L'hypercube a été contracté dans et deux coordonnées remplacées par « _ ».

Dans les années 2000, de nombreux modÚles furent proposés pour prendre en compte des caractéristiques communes à de nombreux réseaux. Deux des principales caractéristiques sont l'effet petit monde et l'effet libre d'échelle. Il est possible de modifier un hypercube afin d'obtenir l'effet libre d'échelle, tout en continuant à bénéficier de sa propriété de routage local[C 3]. Pour cela, des sommets sont contractés à la condition qu'ils ne diffÚrent que sur une coordonnée qui sera remplacé par un joker « _ ». AprÚs une séquence de contractions, c'est-à-dire plusieurs contractions successives, il est toujours possible de trouver un chemin d'un sommet à un sommet en utilisant leurs coordonnés et en remplaçant les jokers « _ » par les coordonnées de .

La condition de ne différer que sur une coordonnée tout en opérant une séquence de contractions conduit à ce qu'un sous-hypercube soit contracté, et le degré du sommet résultant de la contraction d'un hypercube dans , est :

En rĂ©sumĂ©, l'effet libre d'Ă©chelle est obtenu par contraction de sous-hypercubes de grande taille et les algorithmes de navigation n'ont pas besoin d'ĂȘtre modifiĂ©s.

Galerie

  • Q
            3
    {\displaystyle Q_{3}}
  • Q
            4
    {\displaystyle Q_{4}}
  • Q
            5
    {\displaystyle Q_{5}}
  • Q
            6
    {\displaystyle Q_{6}}
  • Q
            7
    {\displaystyle Q_{7}}
  • Q
            8
    {\displaystyle Q_{8}}
  • Q
            9
    {\displaystyle Q_{9}}
  • Q
            10
    {\displaystyle Q_{10}}

Références

A - Ouvrages généraux et actes de conférence
  1. J-C. Bermond, P. Fraigniaud, A. Germa, M-C. Heydemann, E. Lazard, P. Michallon, A. Raspaud, D. Sotteau, M. Syska et D. Trystram - Communications dans les réseaux de processeurs, Masson, 1994, (ISBN 2225844100). Paru sous le pseudonyme Jean de Rumeur.
  2. (en) Wilfriend Imrich et Sandi Klavzar - Product Graphs: Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization, 2000, (ISBN 0471370398).
  3. suite A087101 de l'OEIS
  4. (en) Cai Heng Li - Cayley graph in Encyclopaedia of Mathematics, Springer, (ISBN 1402006098). on-line
  5. (en) Dragos M. Cvetkovic et Michael Doob et Horst Sachs - Spectra of Graphs, Heidelberg, Leipzig, 1994, (ISBN 3335004078).
  6. (en) Jon S. Squire et Sandra M. Palais - Programming and design considerations of a highly parallel computer, Proceedings of the joint computer conference, pages 395-400, 1963.
  7. (en) Geoffrey Fox (Ă©diteur) - Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues, volumes 1 et 2, Pasadena, Californie, 19-20 janvier 1988.
B - ThÚses et mémoires
  1. Rafaï Mourad Madani - Généralisations d'hypercubes et de (0,2)-graphes, ThÚse de doctorat, Université Joseph Fournier - Grenoble 1, 1992, sous la direction de Jean-Marie Laborde.
  2. (en) Vipul Kumar Mehra - Spanners for some networks derived from hypercubes, thÚse de Master, Université Simon Fraser, sous la direction d'Arthur L. Liestman, 2006.
C - Chapitres
  1. (en) Miltos D. Grammatikakis, D. Frank Hsu et Miro Kraetzl - Parallel system interconnections and communications, CRC Press, chapitre 4 : « Hypercube Networks », 2001, (ISBN 0849331536).
  2. (en) Behrooz Parhami, Introduction to Parallel Processing : Algorithms and Architectures, Springer, coll. « Plenum Series in Computer Science » (no 1), , 532 p. (ISBN 0-306-45970-1, lire en ligne), chap. 13 (« Hypercube and Their Algorithms »), p. 259–278 [lire en ligne].
  3. (en) Philippe J. Giabbanelli - Self-improving Immunization Policies for Complex Networks, thÚse de Master, Université Simon Fraser, sous la direction de Joseph G. Peters, chapitre 6 : « Conclusion and future work », 2009.
D - Articles et rapports
  1. (en) Paul Cull et Shawn M. Larson, « Smaller diameters in hypercube-variant networks », Telecommunication Systems, vol. 10, nos 1-2,‎ , p. 175–184 (DOI 10.1023/A:1019167000458).
  2. Harary, Hayes et Wu 1988.
  3. (en) TomĂĄs Feder et Carlos Subi, « Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations », Information Processing Letters, vol. 109, no 5,‎ , p. 267–272 (DOI 10.1016/j.ipl.2008.10.015).
  4. (en) Frank Harary, « The Automorphism Group of a Hypercube », Journal of Universal Computer Science, vol. 6, no 1,‎ , p. 136-138 (DOI 10.3217/jucs-006-01-0136).
  5. (en) Marston Conder et Peter DobcsĂĄnyi, « Trivalent symmetric graphs on up to 768 vertices », Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 40,‎ , p. 41–63 (lire en ligne).
  6. (en) Michael Cook et William Wolfe, « The Hypercube Graph and the Inhibitory Hypercube Network », .
  7. (en) Sandi KlavĆŸar, « Counting hypercubes in hypercubes », Discrete Mathematics, vol. 306, no 22,‎ , p. 2964–2967 (DOI 10.1016/j.disc.2005.10.036).
  8. (en) Nana Arizumi, Peter Hamburger et Alexandr Kostochka, « On k-detour subgraphs of hypercubes », Journal of Graph Theory, vol. 57, no 1,‎ , p. 55–64 (DOI 10.1002/jgt.20281).
  9. (en) Satoshi Fujita, StĂ©phane Perennes et Joseph G. Peters, « Neighbourhood Gossiping in Hypercubes », Parallel Processing Letters, vol. 8, no 2,‎ , p. 189–195 (DOI 10.1142/S0129626498000201).
  10. (en) Charles L. Seitz, « The cosmic cube », Communications of the ACM, vol. 28, no 1 « Special section on computer architecture »,‎ , p. 22–33 (DOI 10.1145/2465.2467).
  11. (en) L. W. Tucker et G. G. Robertson, « Architecture and applications of the connection machine », Computer, IEEE Computer Society, vol. 21, no 8,‎ , p. 26–38 (DOI 10.1109/2.74).
  12. (en) Thomas H. Dunigan Jr. - rapports 10881 (Performance of a Second Generation Hypercube), 10685 (Hypercube Simulation on a Local Area Network), 11068 (A Remote Host Facility for Intel Hypercubes), 11790 (Performance of the Intel iPSC/860 and Ncube 6400 hypercubes) et 11744 (Hypercube clock synchronization). 1988 Ă  1992. Oak Ridge National Laboratory.
  13. (en) Trevor N. Mudge et Tarek Saad Abdel-Rahman, « Vision Algorithms for Hypercube Machines », Journal of Parallel and Distributed Computing, vol. 4, no 1,‎ , p. 79–94 (DOI 10.1016/0743-7315(87)90009-8).
  14. (en) Vincenzo Auletta, Alberto Negro et Vittorio Scarano, « Fast execution of irregularly structured programs with low communication frequency on the hypercube », Lecture Notes in Computer Science, vol. 980,‎ , p. 59–73 (ISBN 978-3-540-60321-4, DOI 10.1007/3-540-60321-2_4).
  15. (en) Pierre Fraigniaud, Jean-Claude König et Emmanuel Lazard, « Oriented hypercubes », Networks, vol. 39, no 2,‎ , p. 98–106 (DOI 10.1002/net.10012).
  16. (en) Kanad Ghose et Kiran R. Desai, « Hierarchical cubic networks », IEEE Transactions on Parallel and Distributed Systems, vol. 6, no 4,‎ , p. 427–435 (DOI 10.1109/71.372797).
  17. (en) W. -J. Hsu, « Fibonacci cubes: A new interconnection topology », IEEE Transactions on Parallel and Distributed Systems, vol. 4, no 1,‎ , p. 3–12 (DOI 10.1109/71.205649).
  18. (en) Rostislav Caha et Petr Gregor, « Embedding Fibonacci Cubes into Hypercubes with Faulty Nodes », Lecture Notes in Computer Science, vol. 1893,‎ , p. 253-263 (ISBN 978-3-540-67901-1, DOI 10.1007/3-540-44612-5_21).

    Voir aussi

    Bibliographie

    Articles connexes

    Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.