Hypercube (graphe) - Définition

Introduction

Hypercube
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
modifier

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 de n graphes complets K₂, soit :

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 {Z₂}ⁿ, 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 G = (V,E) :

Le graphe hypercube Q₃ est le graphe hexaédrique et Q₄ est le graphe tesseract.

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.

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 ». 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 de Caltech (64 processeurs Intel 8086/86 embarquant chacun 128Kb de mémoire) en 1983. De nombreuses autres machines sont alors produites, comme les Ametek série 2010, les Connection Machine CM-1/CM-2, les nCUBE et les iPSC d'Intel. De nombreuses études sur les performances des machines parallèles utilisant une architecture en hypercube sont réalisées au laboratoire national d'Oak Ridge sous le contrat DE-AC05-84OR21400. En effet, ce laboratoire créé à l'origine pour le Projet 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.

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 (« Ordinateurs concurrents en hypercube et applications »). Utiliser une machine parallèle n'augmente pas automatiquement la performance d'un algorithme : non seulement les algorithmes doivent être conçus de façon à tirer profit de l'architecture, mais les données ne peuvent pas toujours être partitionnées pour être traitées par différents processeurs, et ces processeurs ont également besoin de communiquer. Dans l'exemple de l'addition, le coût de communication était considéré comme négligeable, et ceci est l'hypothèse que nous conserverons par la suite : en effet, les propriétés de la machine (temps de communication, lecture/écriture, ...) sont généralement ignorés dans l'analyse des algorithmes, et on se concentre sur les dépendances entre les données et les façons de rendre le calcul parallèle sur un hypercube.

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

Réutilisation d'algorithmes par plongements

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

• Congestion. 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 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.