Hypercube (Graphe)

Hypercube (graphe)

Pour les articles homonymes, voir Hypercube (homonymie).

  Cette page se comprend mieux après la lecture de Théorie des graphes.

Hypercube
Q4
Notation	Qn ou Hn
Nombre de sommets	2n
Nombre d'arêtes	2n − 1n
Distribution des degrés	n-régulier
Coefficient de clustering	0
Diamètre	n
Propriétés	Hamiltonien, distance-unité
Utilisation	Machines parallèles

Les hypercubes, ou n-cubes, forment une famille de graphes. Dans un hypercube Q_n, chaque sommet porte une étiquette de longueur 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 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.

Construction

L'hypercube Q₁ 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 à la dimension 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, Q₂ consiste en quatre sommets étiquetés 00, 01, 10 et 11. 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'à Q₃ et Q₄. Cette méthode de construction est récursive, puisque pour construire Q_n on se fonde sur Q_{n − 1}.

→ → →

On peut aussi définir Q_n comme le produit cartésien^{[A 1]} de n graphes complets K₂, 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. On dispose 2ⁿ sommets, et chacun a une étiquette unique dans l'espace vectoriel^{[D 1]} {Z₂}ⁿ, 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\}$

Propriétés

Fondamentales

Un cycle dans un hypercube Q₃ constitué de deux hypercubes Q₂. En rouge, un chemin dans le premier hypercube Q₂, 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 n symboles, chaque sommet est connecté à exactement n voisins : tout sommet a donc degré n, autrement dit le graphe est n-régulier.
• Nombre de sommets. Par la construction récursive, on voit que pour passer de Q_{n − 1} à Q_n, il faut faire une copie du graphe, autrement dit le nombre de sommets est doublé. Si V_n est le nombre de sommets du graphe Q_n, on obtient ainsi V_n = 2 * V_{n − 1}, et le premier cas est V₁ = 2 ; en déroulant la récurrence, on obtient V_n = 2 * V_{n − 1} = 2² * V_{n − 2} = ... = 2ⁿ, c'est-à-dire que le graphe a 2ⁿ sommets.
• Diamètre^{[A 1]}. Une des propriétés du produit cartésien est que le diamètre D(C) de $C = A \square B$ est égal à D(A) + D(B). Comme Q_n est le produit cartésien de n graphes complets K₂, son diamètre est égal à n * D(K₂) = n * 1 = n.

Les sommets de l'hypercube Q₄ sont répartis en deux ensemble. 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 à Q₂, qui est isomorphe au cycle C₄ (i.e. le cycle de longueur 4). Le graphe Q₃ est formé par deux graphes Q₂ : si l'on souhaite un cycle de longueur supérieur à 4 dans Q₃, alors on choisit p arêtes dans un des deux graphes Q₂, p arêtes dans l'autre Q₂ et 2 arêtes supplémentaires pour naviguer entre les deux graphes, ce qui porte le total d'arêtes à $2 \times p + 2 = 2(p+1)$ ; 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 si 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 χ(Q_n) = 2. Pour voir qu'un graphe est biparti, il suffit de trouver un schéma afin de ranger chaque sommet dans un ensemble G₁ ou G₂, 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 G₁ peut être constitué des sommets dont l'étiquette a un nombre pair de 1, et G₂ 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 $n \le 3$. Pour n > 3, 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 Q₄.
• Eulérien. Un graphe a un chemin eulérien si et seulement si tout sommet est de degré pair. Comme Q_n est n-régulier, il en résulte qu'il n'y a un chemin eulérien que pour n pair.
• Hamiltonien. Q₂ étant un cycle, il est aussi un circuit hamiltonien. Pour construire un circuit hamiltonien dans Q₃, 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 Q₃ et Q₄. 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 k de circuits hamiltoniens dans Q_n est donnée^{[D 3]} par : $\left(\frac{n*\log2}{e \log \log n}*(1 - o(1))\right)^{2^n} \le k \le \frac{(2^n)!^{\frac{2^n}{2n}}((n-1)!)^{\frac{2^n}{2(n-1)}}}{2}$ .

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 H(d,q) est le graphe obtenu par produit cartésien de d graphes complets K_q. L'hypercube Q_d étant obtenu par produit cartésien de d copies de K₂, il découle de la définition que tout hypercube Q_d est isomorphe à H(d,2). Une définition alternative d'un graphe de Hamming montre le rapport direct avec celle utilisée pour introduire l'hypercube : H(d,q) est le graphe dont les sommets sont S^d, l'ensemble des mots de longueur d sur un alphabet S, où | S | = q. Deux sommets sont adjacents dans H(d,q) 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 {n,n − 1,n − 2,...,1,1,2,3,...,n}.
• Diagramme de Hasse. L'hypercube Q_n 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 Q_n définissent le code de Gray sur n bits. De plus, ce code suit une construction similaire à celle de l'hypercube : les mots de n bits sont déterminés en copiant les mots de n − 1 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é.

Aspects algébriques

Groupe d'automorphisme

Le groupe d'automorphisme Γ(Q_d) de l'hypercube Q_d est d'ordre 2^dd!. Il est isomorphe au produit en couronne des groupes symétriques S₂ et S_d : $S_2 \wr S_d$^{[D 4]}. Le produit en couronne de A et B étant défini comme le produit semi-direct $A \wr B = A^B \rtimes B$ où A^B est l'ensemble des fonctions de A dans B et où A agit sur A^B par décalage d'indice :

(g.λ)(s) = λ(g ^{− 1}s) pour $g \in A$ et $\lambda \in A^B$.

L'hypercube Q_d est un graphe arc-transitif : son groupe d'automorphisme Γ(Q_d) agit transitivement sur l'ensemble de ses arcs. Étant donné deux arêtes e₁ = u₁v₁ et e₂ = u₂v₂ de G, il existe deux automorphismes $(f_V,f_E) : Q_n \rightarrow Q_n$ et $(g_V,g_E) : Q_n \rightarrow Q_n$ tels que f_E(e₁) = e₂, g_E(e₁) = e₂, et f_V(u₁) = u₂, f_V(v₁) = v₂, g_V(u₁) = v₂, g_V(v₁) = u₂.

L'hypercube Q_d est donc a fortiori symétrique. Le groupe Γ(Q_d) 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 Q₃ est l'unique graphe cubique symétrique à 8 sommets^{[D 5]}. Le graphe Q₄ est l'unique graphe régulier de degrés 4 à 16 sommets^{[A 3]}.

Graphe de Cayley

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

$G = \underbrace{{\frac { \mathbb Z} {2 \mathbb Z}} \times {\frac { \mathbb Z} {2 \mathbb Z}} \times ... \times {\frac { \mathbb Z} {2 \mathbb Z}}}_{d\text{ fois}}$ S = {(1,0,0,...,0),(0,1,0,...,0),...,(0,0,...,1,0),(0,0,...,0,1)}

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 A(Q₂) de l'hypercube Q₁ est définie ci-dessous. Par la définition récursive de l'hypercube, pour passer à la dimension supérieure Q₂, on duplique Q₁ 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 A(Q₃) 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 Q₁ à Q₂ se comprend comme suit : les entrées {A_{00 − 00},A_{00 − 01},A_{01 − 00},A_{01 − 01}} correspondent à la matrice d'origine, et se trouvent dupliquées en {A_{10 − 10},A_{10 − 11},A_{11 − 10},A_{11 − 11}}. 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ù $I_{2^n-1}$ représente la matrice identité de dimension 2ⁿ − 1 :

$A(Q_n) = \begin{pmatrix} Q_{n-1} & I_{2^n-1}\\ I_{2^n-1} & Q_{n-1}\\ \end{pmatrix}$

Pour comprendre l'évolution du spectre de la matrice en fonction de n, il faut revenir à la définition comme produit cartésien. Le spectre d'un produit cartésien $A \square B$ est {α_i + β_j}, où {α_i} est le spectre de A et {β_j} le spectre de B ; autrement dit, le spectre est la somme de toutes les paires possibles^{[A 5]}. Sachant que le spectre de Q₁ = K₂ est { + 1, − 1}, on en déduit que le spectre de Q₂ est { + 2,0, − 2} : en effet, elles correspondent aux combinaisons 1 + 1 = 2, 1 − 1 = 0, − 1 − 1 = − 2. Si l'on passe au stade suivant, soit Q₃, on a d'un côté le spectre { + 2,0, − 2} de Q₂, et de l'autre { − 1, + 1} de K₂ : le résultat du produit cartésien est { + 3, + 1, − 1, − 3}.

Chemins et sous-graphes

Navigation

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 0010 à 1011, on obtient $0010 \rightarrow 1010 \rightarrow 1011$. Dans le cas général, pour aller de (x₁,x₂,...,x_n) à (y₁,y₂,...,y_n) on obtient :

$(x_1,x_2,...,x_n) \rightarrow (y_1,x_2,...,x_n) \rightarrow (y_1,y_2,x_3,...,x_n) \rightarrow (y_1,y_2,y_3,...,y_n)$

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 n, 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 0010 en 1010, on aurait tout d'abord pu passer par 0011 avant d'aller en 1011. 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 k symboles, combien de façons a-t-on de générer des chemins ? On a k choix pour le premier symbole à changer, puis k − 1 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 k symboles est k!.

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 k (i.e. différant de k symboles) donne^{[A 2]} l'hypercube Q_k. Ceci est illustré par l'exemple ci-dessous : dans le cas de deux sommets voisins u et v, il n'y a qu'un chemin et on obtient l'hypercube Q₁ ; dans le cas où ils sont à distance 2, il y a deux chemins entre eux qui définissent Q₂, et s'ils sont à distance 3 alors l'union des chemins représente l'ensemble de l'hypercube Q₃.

Le nombre α_d d'hypercubes Q_d compris dans Q_n est donné par la formule suivante^{[D 7]} :

$\alpha_d(Q_n) = \binom{n}{d} \times 2^{n-d}$

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]} :

$\sum_{k \ge 0} (-1)^k \times \alpha_k(Q_n) = 1$

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 k, des spanners additifs où la distance peut être augmentée d'un montant k. Dans le cas d'un spanneur additif sur Q_n, des résultats^{[D 8]} concernent les degrés du spanneur :

1. si $k \ge 2$ et $n \le 21$, alors le plus petit degré maximal Δ(k,n) est $e^{-2k}*\frac{n}{\ln n} \le \Delta(k,n) \le 20*\frac{n \ln \ln n}{\ln n}$.
2. si $k \ge 4$ et n est grand, il existe un spanneur de degré moyen au plus $2 + 2^{4-\frac{k}{2}} + o(1)$.

Pour avoir un spanner 2-additif de Q₃ 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 2 où les arêtes sont celles dont les extrémités $u, v \in V$ sont données par les trois conditions suivantes :

1. $u = (0, x_2, ..., x_i, ..., x_n), v = (0, x_2, ..., \bar{x_i}, ..., x_n), \forall \text{ i pair}$
2. $u = (1, x_2, ..., x_i, ..., x_n), v = (1, x_2, ..., \bar{x_i}, ..., x_n), \forall \text{ i } > 1 \text{ impair}$
3. u = (0,x₂,...,x_n),v = (1,x₂,...,x_n)

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 (0,x₂,...,x_n). 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 (1,y₂,...,y_n) 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 (0,y₂,...,y_n) on utilise une dernière inversion par la condition (3). Le cas où le sommet d'origine est (1,x₂,...,x_n) 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 001 à 000 : ce qui se ferait normalement directement en une étape doit se faire en trois étapes, en passant par 101 et 100.

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 log₂n ; un graphe pouvant finir une diffusion en log₂n é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ù n = 2^k, le nœud source doit avoir au moins k 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 k voisins d'où $\frac{1}{2}(n*2^k) = k*2^{k-1}$ arêtes ($\frac{1}{2}$ 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 N nombres. Sur une machine séquentielle, on additionne le premier nombre avec le second, puis on rajoute le troisième, etc., Au total, N − 1 é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, 1 + log₂N é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^{[D 10]}.

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 2ⁿ 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 »^{[D 10]}. 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é 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 11]} 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^{[D 12]} CM-1/CM-2, les nCUBE 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 13]}. 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 13]}

	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 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 m ait un coût en temps 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 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 Q₄.

Chaque processeur de Q₄ 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^{[A 6]} (« 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 14]}, 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 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 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. 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 à 2ⁿ − 1 nœuds a un plongement de dilatation 1 sur Q_{n + 1}.

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é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 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^{[D 15]}.

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 $\vec{G}$ de G utilise la moitié du nombre de broches et câbles par rapport à G »^{[D 16]} : 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

HCN(2,2) formé de 2² = 4 hypercubes Q₂, chacun constituant un cluster dont le numéro est encadré.

Un hierarchical cubic network ^{[D 17]} HCN_n,n est formé de 2ⁿ n-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 G = (V,E) composé de 2ⁿ n-cubes, où (I,J) désigne le sommet J du cluster I et $\bar{i}$ est le complément bit à bit de i :

$\begin{array}{crl} \rm \text{pour } i = 0..2^n-1 & \rm & \rm \\ & \text{pour } j = 0..2^n-1 & \\ & & \text{si } i \neq j, E(G) \leftarrow E(G) \uplus \{e_{ij},e_{ji}\} \\ & & \text{sinon}, E(G) \leftarrow E(G) \uplus \{e_{i \bar{i} }, e_{j \bar{j} }\} \end{array}$

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 18]}. Les conditions fondamentales du cube de Fibonacci de dimension n, noté FC_n, sont les mêmes que celles de l'hypercube : chaque sommet porte une étiquette de longueur n sur un alphabet A = {0,1}, 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 1 consécutif. Ainsi, ci-dessous, on voit que les cubes de Fibonacci FC₁,FC₂,FC₃,FC₄ peuvent se retrouver comme sous-graphes des hypercubes Q₁,Q₂,Q₃,Q₄ en éliminant les étiquettes contenant deux 1 consécutifs.

La construction par récurrence ^{[D 19]} peut-être définie par une grammaire formelle en énonçant les étiquettes valides pour les sommets, puis en considérant le graphe FC_n comme le sous-graphe de l'hypercube Q_n induit par les sommets valides V(FC_n) :

$\begin{cases} V_0 = \epsilon \\ V_1 = \{0,1\} \\ V_i = \{0 \alpha | \alpha \in V_{i-1}\} \cup \{10 \alpha | \alpha \in V_{i-2}\}, \forall i > 2 \end{cases}$

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	n	$\frac{n}{2}$	0
Twisted cube (1987)	$\frac{n+1}{2}$	$\approx \frac{3n}{8}$	(n − 1)2n − 4
Twisted hypercube (1991)	n − 1	$\approx \frac{n}{2} - \frac{1}{8}$	2n − 1
Twisted N-cube (1991)	n − 1	$\approx \frac{n}{2}$	2
Generalized twisted cube (1993)	$\frac{2n}{3}$	$\approx \frac{11n}{24}$	$n2^{\lfloor n/3 \rfloor}$
0-Möbius Cube (1995)	$\frac{n+2}{2}$	$\approx \frac{n}{3}$	(n − 2)2n − 1

Graphe libre d'échelle par contraction

L'hypercube Q₂ a été contracté dans Q₄ 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 A à un sommet B en utilisant leurs coordonnés et en remplaçant les jokers « _ » par les coordonnées de B.

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 s résultant de la contraction d'un hypercube Q_p dans Q_n, 1 < p < n est :

$d_{q_p}(s) = 2^{p}(n-p)$

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

Tracé alternatif pour Q4

Tracé alternatif pour Q4

Q3 avec étiquetage

Q4 avec étiquetage

Références

A - Ouvrages généraux et actes de conférence ↑ a  et b  (fr) 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. ↑ a  et b  (en)Wilfriend Imrich et Sandi Klavzar - Product Graphs: Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization, 2000, (ISBN 0471370398). ↑ (en) Neil J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, A087101 on-line ↑ (en) Cai Heng Li - Cayley graph in Encyclopaedia of Mathematics, Springer, (ISBN 1402006098). on-line ↑ (en)Dragos M. Cvetkovic et Michael Doob et Horst Sachs - Spectra of Graphs, Heidelberg, Leipzig, 1994, (ISBN 3335004078). ↑ (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 ↑ (fr) 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. ↑ (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 ↑ a  et b  (en) Miltos D. Grammatikakis, D. Frank Hsu et Miro Kraetzl - Parallel system interconnections and communications, CRC Press, chapitre 4 : « Hypercube Networks », 2001, (ISBN 0849331536). ↑ (en) Behrooz Parhami - Introduction to Parallel Processing: Algorithms and Architectures, Springer, chapitre 13 : « Hypercube and their algorithms », 1999, (ISBN 0306459701). ↑ (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 ↑ a  et b  (en) Paul Cull et Shawn M. Larson - Smaller diameters in hypercube-variant networks, Telecommunication Systems, volume 10, pages 175-184, 1998. ↑ a , b , c  et d  (en) Frank Harary, John P. Hayes et Horng-Jyh Wu - A survey on the theory of hypercube graphs, Comput. Math. Applic., volume 15, numéro. 4, pages 277-289, 1988. ↑ (en)Tomas Feder et Carlos Subia - Nearly tight bounds on the number of Hamiltonian circuits of the hypercubenext term and generalizations, Information Processing Letters, volume 109, numéro 5, pages 267-272, 2009. ↑ (en) F. Harary - The Automorphism Group of a Hypercube, Journal of Universal Computer Science, volume 6, pages 136-138, 2000. ↑ (en) Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41-63 ↑ (en) Michael Cook et William Wolfe - The Hypercube Graph and the Inhibitory Hypercube Network, 2006. ↑ a  et b  (en) Sandi Klavžar - Counting hypercubes in hypercubes, Discrete Mathematics, volume 306, numéro 22, pages 2964-2967, 2006. ↑ (en) Nana Arizumi, Peter Hamburger et Alexandr Kostochka - On k-detour subgraphs of hypercubes, Journal of Graph Theory, volume 57, numéro 1, pages 55-64, 2008. ↑ (en) Satoshi Fujita, Stéphane Perennes et Joseph G. Peters - Neighbourhood Gossiping in Hypercubes, Parallel Processing Letters, volume 8, numéro 2, pages 189-195, 1998. ↑ a  et b  (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. ↑ (en) Charles L. Seitz - The cosmic cube, Communications of the ACM, volume 28, numéro 1, numéro spécial sur l'architecture des ordinateurs, pages 22-33, 1985. ↑ (en) L. W. Tucker et G. G. Robertson - Architecture and applications of the connection machine, IEEE Comput., volume 21, pages 26-38, 1988. ↑ a  et b  (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. ↑ (en) Trevor N. Mudge et Tarek Saad Abdel-Rahman - Vision Algorithms for Hypercube Machines, Journal of parallel and distributed computing, volume 4, pages 79-94, 1987. ↑ (en) Vincenzo Auletta, Alberto Negro et Vittorio Scarano - Fast execution of irregularly structured programs with low communication frequency on the hypercube, LNCS, volume 980, pages 59-73, 1995. ↑ (en) Pierre Fraigniaud, Jean-Claude König et Emmanuel Lazard - Oriented hypercubes, Networks, volume 39, numéro 2, pages 98-106, 2002. ↑ (en) Kanad Ghose et Kiran R. Desai - Hierarchical cubic networks, IEEE Transactions on Parallel and Distributed Systems, volume 6, numéro 4, pages 427-435, 1995. ↑ (en) W.-J. Hsu, C. V. Page et J.-S. Liu - Fibonacci cubes: a class of self-similar graphs, Fibonacci Quarterly, volume 31, numéro 1, pages 65-72, 1993. ↑ (en) Rostislav Caha et Petr Gregor - Embedding Fibonacci Cubes into Hypercubes with Ω(2cn) Faulty Nodes, LNCS, volume 1893, pages 253-263, 2000

Bibliographie

• (en) Frank Harary, John P. Hayes et Horng-Jyh Wu - A survey on the theory of hypercube graphs, Comput. Math. Applic., volume 15, numéro. 4, pages 277-289, 1988.

La version du 26 août 2009 de cet article a été reconnue comme « bon article » (comparer avec la version actuelle). Pour toute information complémentaire, consulter sa page de discussion et le vote l’ayant promu. La version du 26 août 2009 de cet article a été reconnue comme « bon article », c'est-à-dire qu'elle répond à des critères de qualité concernant le style, la clarté, la pertinence, la citation des sources et l'illustration.

Ce document provient de « Hypercube (graphe) ».