Interconexión Hipercubo

La estructura de hipercubo (o multiprocesador binario de n cubos) representa un sistema débilmente acoplado formado por N = 2 n procesadores interconectados en un cubo binario de n dimensiones. Cada procesador hace un hecho del cubo. Cada procesador hace un Node del cubo. Por lo tanto, es habitual referirse a cada Node como que contiene un procesador; en efecto, no solo tiene una CPU, sino también memoria local e interfaz de E/S. Cada procesador tiene rutas de comunicación directas con otros n procesadores vecinos. Estos caminos corresponden a los bordes del cubo.

Hay 2 direcciones binarias distintas de n bits que se pueden asignar a los procesadores. Cada dirección de procesador difiere de la de cada uno de sus n vecinos exactamente en una posición de bit.

• Estructura de hipercubo para n= 1, 2 y 3.
• Una estructura de un cubo contiene n = 1 y 2n = 2.
• Tiene dos procesadores interconectados por un solo camino.
• Una estructura de dos cubos contiene n=2 y 2n=4.
• Tiene cuatro Nodes interconectados como un cubo.
• Una estructura de n cubos contiene 2n Nodes con un procesador que reside en cada Node.

A cada Node se le asigna una dirección binaria de tal manera que las direcciones de dos vecinos difieren exactamente en una posición de bit. Por ejemplo, los tres vecinos del Node con dirección 100 son 000, 110 y 101 en una estructura de tres cubos. Cada uno de estos números binarios difiere de la dirección 100 en un valor de bit.

El enrutamiento de mensajes a través de una estructura de n cubos puede tomar de uno a n enlaces desde un Node de origen a un Node de destino.

Ejemplo:
en una estructura de tres cubos, el Node 000 puede comunicarse con el 011 (del 000 al 010 al 011 o del 000 al 001 al 011). Debe cruzar al menos tres enlaces para comunicarse desde el Node 000 al Node 111. Se diseña un procedimiento de enrutamiento determinando el OR exclusivo de la dirección del Node de origen con la dirección del Node de destino. El valor binario resultante tendrá 1 bits correspondientes a los ejes en los que difieren los dos Nodes. Luego, el mensaje se transmite a lo largo de cualquiera de los ex.

Por ejemplo, un mensaje en el Node 010 que va al Node 001 produce un OR exclusivo de las dos direcciones igual a 011 en una estructura de tres cubos. El mensaje se puede transmitir a lo largo del segundo eje al Node 000 y luego a través del tercer eje al Node 001.