Una red Omega es una configuración de red que se utiliza a menudo en arquitecturas de computación en paralelo . Es una topología indirecta que se basa en el perfecto algoritmo de interconexión aleatoria .
Arquitectura de conexión
Una red Omega 8x8 es una red de interconexión de múltiples etapas, lo que significa que los elementos de procesamiento (PE) se conectan mediante múltiples etapas de conmutadores. Las entradas y salidas reciben direcciones como se muestra en la figura. Las salidas de cada etapa se conectan a las entradas de la siguiente etapa mediante un sistema de conexión aleatoria perfecto . Esto significa que las conexiones en cada etapa representan el movimiento de una baraja de cartas dividida en 2 barajas iguales y luego barajadas juntas, con cada carta de una baraja alternando con la carta correspondiente de la otra baraja. En términos de representación binaria de los PE, cada etapa de la mezcla perfecta puede considerarse como un desplazamiento lógico cíclico a la izquierda ; cada bit de la dirección se desplaza una vez hacia la izquierda, con el bit más significativo moviéndose al bit menos significativo.
En cada etapa, los pares de entradas adyacentes se conectan a un elemento de intercambio simple, que puede configurarse recto (pasar las entradas directamente a las salidas) o cruzado (enviar la entrada superior a la salida inferior y viceversa). Para el elemento de procesamiento N, una red Omega contiene N / 2 conmutadores en cada etapa y log 2 N etapas. La forma en que se configuran estos conmutadores determina las rutas de conexión disponibles en la red en un momento dado. Dos de estos métodos son el enrutamiento de etiquetas de destino y el enrutamiento de etiquetas XOR, que se describen en detalle a continuación.
La red Omega es altamente bloqueante, aunque siempre se puede hacer una ruta desde cualquier entrada a cualquier salida en una red libre.
Enrutamiento de etiquetas de destino
En el enrutamiento de etiquetas de destino, la configuración del conmutador está determinada únicamente por el destino del mensaje. El bit más significativo de la dirección de destino se usa para seleccionar la salida del interruptor en la primera etapa; si el bit más significativo es 0, se selecciona la salida superior, y si es 1, se selecciona la salida inferior. El siguiente bit más significativo de la dirección de destino se utiliza para seleccionar la salida del interruptor en la siguiente etapa, y así sucesivamente hasta que se haya seleccionado la salida final.
Por ejemplo, si el destino de un mensaje es PE 001, las configuraciones del interruptor son: superior, superior, inferior. Si el destino de un mensaje es PE 101, las configuraciones del interruptor son: inferior, superior, inferior. Estos ajustes de conmutador se mantienen independientemente del PE que envía el mensaje.
Enrutamiento de etiquetas XOR
En el enrutamiento de etiquetas XOR, la configuración del conmutador se basa en (PE de origen) XOR (PE de destino). Esta etiqueta XOR contiene unos en las posiciones de los bits que deben intercambiarse y ceros en las posiciones de los bits que tienen en común el origen y el destino. El bit más significativo de la etiqueta XOR se usa para seleccionar la configuración del interruptor en la primera etapa; si el bit más significativo es 0, el conmutador se establece en transferencia, y si es 1, el conmutador está cruzado. El siguiente bit más significativo de la etiqueta se usa para configurar el interruptor en la siguiente etapa, y así sucesivamente hasta que se haya seleccionado la salida final.
Por ejemplo, si PE 001 desea enviar un mensaje a PE 010, la etiqueta XOR será 011 y los ajustes apropiados del interruptor son: A2 recto, B3 cruzado, C2 cruzado.
Aplicaciones
En el multiprocesamiento , las redes omega se pueden utilizar como conectores entre las CPU y su memoria compartida , con el fin de disminuir la probabilidad de que la conexión de la CPU a la memoria se convierta en un cuello de botella.
Esta clase de redes se ha integrado en el multiprocesador Illinois Cedar, en el IBM RP3 y en la Ultracomputadora NYU [ cita requerida ] .
Ejemplos de
Ver también
Referencias
- Lawrie, Duncan H. (diciembre de 1975). "Acceso y alineación de datos en un procesador de matriz". Transacciones IEEE en computadoras . C-24 (12): 1145–55. doi : 10.1109 / TC.1975.224157 .