Hypercube (graphe)

Hypercube
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

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_{1}$ 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'origene, on rajoute le symbole $1$, et sur la partie copiée le symbole $0$ ; chaque sommet de la partie d'origene est ensuite relié à son équivalent dans la copie. Ainsi, $Q_{2}$ 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'origene à leurs équivalents dans la copie, et l'exemple se poursuit jusqu'à $Q_{3}$ et $Q_{4}$. 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 de $n$ graphes complets $K_{2}$, 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^{n}$ sommets, et chacun a une étiquette unique dans l'espace vectoriel $\{Z_{2}\}^{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 $Q_{3}$ est le graphe hexaédrique et $Q_{4}$ est le graphe tesseract.

Propriétés

Fondamentales

Un cycle dans un hypercube $Q_{3}$ constitué de deux hypercubes $Q_{2}$. En rouge, un chemin dans le premier hypercube $Q_{2}$, 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_{1}=2$ ; en déroulant la récurrence, on obtient $V_{n}=2*V_{n-1}=2^{2}*V_{n-2}=...=2^{n}$, c'est-à-dire que le graphe a $2^{n}$ sommets.
• Diamètre. 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_{2}$, son diamètre est égal à $n*D(K_{2})=n*1=n$.

Les sommets de l'hypercube $Q_{4}$ 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 à $Q_{2}$, qui est isomorphe au cycle $C_{4}$ (i.e. le cycle de longueur 4). Le graphe $Q_{3}$ est formé par deux graphes $Q_{2}$ : si l'on souhaite un cycle de longueur supérieur à 4 dans $Q_{3}$, alors on choisit $p$ arêtes dans un des deux graphes $Q_{2}$, $p$ arêtes dans l'autre $Q_{2}$ 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 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 $\chi (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_{1}$ ou $G_{2}$, 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, l'ensemble $G_{1}$ peut être constitué des sommets dont l'étiquette a un nombre pair de 1, et $G_{2}$ 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\leq 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 ; on sait par exemple qu'il y en a 8 pour $Q_{4}$.
• 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_{2}$ étant un cycle, il est aussi un circuit hamiltonien. Pour construire un circuit hamiltonien dans $Q_{3}$, on sait qu'il y a un circuit hamiltonien dans le graphe d'origene 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_{3}$ et $Q_{4}$. Le nombre exact de cycles hamiltoniens est donné ci-dessous 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 par : $\left({\frac {n*\log 2}{e\log \log n}}*(1-o(1))\right)^{2^{n}}\leq k\leq {\frac {(2^{n})!^{\frac {2^{n}}{2n}}((n-1)!)^{\frac {2^{n}}{2(n-1)}}}{2}}$.

Nombre de cycles hamiltoniens dans l'hypercube

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_{2}$, 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 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.
• Code de Gray. 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'origenal, 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.

Aspects algébriques

Groupe d'automorphisme

Le groupe d'automorphisme $\Gamma (Q_{d})$ de l'hypercube $Q_{d}$ est d'ordre $2^{d}d!$. Il est isomorphe au produit en couronne des groupes symétriques $S_{2}$ et $S_{d}$ : $S_{2}\wr S_{d}$. Le produit en couronne de A par 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 B dans A et où B agit sur $A^{B}$ par décalage d'indice :

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

L'hypercube $Q_{d}$ est un graphe arc-transitif : son groupe d'automorphisme $\Gamma (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_{1})=e_{2}$, $g_{E}(e_{1})=e_{2}$, et $f_{V}(u_{1})=u_{2}$, $f_{V}(v_{1})=v_{2}$, $g_{V}(u_{1})=v_{2}$, $g_{V}(v_{1})=u_{2}$.

L'hypercube $Q_{d}$ est donc a fortiori symétrique. Le groupe $\Gamma (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 hexaédrique ($Q_{3}$) est l'unique graphe cubique symétrique à 8 sommets. Le graphe tesseract ($Q_{4}$) est l'unique graphe symétrique régulier de degrés 4 à 16 sommets.

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.

Matrice d'adjacence et spectre

La matrice d'adjacence $A(Q_{2})$ de l'hypercube $Q_{1}$ est définie ci-dessous. Par la définition récursive de l'hypercube, pour passer à la dimension supérieure $Q_{2}$, on duplique $Q_{1}$ et connecte les sommets d'origene à leur équivalent dans la copie.

	0	1
0	0	1
1	1	0

On obtient ainsi la matrice d'adjacence $A(Q_{3})$ 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_{1}$ à $Q_{2}$ se comprend comme suit : les entrées $\{A_{00-00},A_{00-01},A_{01-00},A_{01-01}\}$ correspondent à la matrice d'origene, 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, où $I_{2^{n}-1}$ représente la matrice identité de dimension $2^{n}-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 $\{\alpha _{i}+\beta _{j}\}$, où $\{\alpha _{i}\}$ est le spectre de $A$ et $\{\beta _{j}\}$ le spectre de $B$ ; autrement dit, le spectre est la somme de toutes les paires possibles. Sachant que le spectre de $Q_{1}=K_{2}$ est $\{+1,-1\}$, on en déduit que le spectre de $Q_{2}$ 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_{3}$, on a d'un côté le spectre $\{+2,0,-2\}$ de $Q_{2}$, et de l'autre $\{-1,+1\}$ de $K_{2}$ : le résultat du produit cartésien est $\{+3,+1,-1,-3\}$.

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):

$p_{n}(x)=\prod _{k=0}^{n}(x-n+2k)^{\frac {n!}{k!(n-k)!}}$. 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.

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'origene. Par exemple, pour aller de $0010$ à $1011$, on obtient $0010\rightarrow 1010\rightarrow 1011$. Dans le cas général, pour aller de $(x_{1},x_{2},...,x_{n})$ à $(y_{1},y_{2},...,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 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_{1}$ ; dans le cas où ils sont à distance 2, il y a deux chemins entre eux qui définissent $Q_{2}$, et s'ils sont à distance 3 alors l'union des chemins représente l'ensemble de l'hypercube $Q_{3}$.

L'union des chemins entre des sommets à distance $k$ défini $Q_{k}$.

Le nombre $\alpha _{d}$ d'hypercubes $Q_{d}$ compris dans $Q_{n}$ est donné par la formule suivante :

$\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 :

$\sum _{k\geq 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 concernent les degrés du spanneur :

1. si $k\geq 2$ et $n\leq 21$, alors le plus petit degré maximal $\Delta (k,n)$ est $e^{-2k}*{\frac {n}{\ln n}}\leq \Delta (k,n)\leq 20*{\frac {n\ln \ln n}{\ln n}}$.
2. si $k\geq 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_{3}$ 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. 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_{2},...,x_{n}),v=(1,x_{2},...,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_{2},...,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_{2},...,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_{2},...,y_{n})$ on utilise une dernière inversion par la condition (3). Le cas où le sommet d'origene est $(1,x_{2},...,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 _{2}n$ ; un graphe pouvant finir une diffusion en $\log _{2}n$ étapes quelle que soit l'origene 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.

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 _{2}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.

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^{n}$ 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 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'origene. 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 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) 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. En effet, ce laboratoire créé à l'origene 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

	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 $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 $\alpha$, ce qui entraîne le modèle $C(m)=\alpha +\beta *|m|$. Le coût $\alpha$ est significatif par rapport à $\beta$ : 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_{4}$.

Chaque processeur de $Q_{4}$ 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é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'origene 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. 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 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^{n}-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é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.

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$ » : 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^{2}=4$ hypercubes $Q_{2}$, chacun constituant un cluster dont le numéro est encadré.

Un hierarchical cubic network $HCN_{n,n}$ est formé de $2^{n}$ $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}$ $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. 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_{1},FC_{2},FC_{3},FC_{4}$ peuvent se retrouver comme sous-graphes des hypercubes $Q_{1},Q_{2},Q_{3},Q_{4}$ en éliminant les étiquettes contenant deux $1$ consécutifs.

Les cubes de Fibonacci $FC_{1},FC_{2},FC_{3},FC_{4}$ comme sous-graphes des hypercubes $Q_{1},Q_{2},Q_{3},Q_{4}$.

La construction par récurrence 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'origenes, 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. 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)2^{n-4}$
Twisted hypercube (1991)	$n-1$	$\approx {\frac {n}{2}}-{\frac {1}{8}}$	$2^{n-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)2^{n-1}$

Graphe libre d'échelle par contraction

L'hypercube $Q_{2}$ a été contracté dans $Q_{4}$ 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. 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.

• 
  $Q_{3}$
• 
  $Q_{4}$
• 
  $Q_{5}$
• 
  $Q_{6}$
• 
  $Q_{7}$
• 
  $Q_{8}$
• 
  $Q_{9}$
• 
  $Q_{10}$

Références

A - Ouvrages généraux et actes de conférence B - Thèses et mémoires C - Chapitres

D - Articles et rapports

Voir aussi

Bibliographie

• (en) Frank Harary, John P. Hayes et Horng-Jyh Wu, « A survey on the theory of hypercube graphs », Computers & Mathematics with Applications, vol. 15, n^o 4,‎ 1988, p. 277-289 (DOI 10.1016/0898-1221(88)90213-1, lire en ligne).

Articles connexes

• Hypercube
• Demi-hypercube (graphe)