Hispanopedia WikiUna red Omega es una configuración de red que se usa frecuentemente en arquitecturas de computación paralela . Es una topología indirecta que se basa en el algoritmo de interconexión de mezcla perfecta .
Arquitectura de conexión
Una red Omega 8x8 es una red de interconexión multietapa, 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 de barajado perfecto . Esto significa que las conexiones en cada etapa representan el movimiento de una baraja de cartas dividida en dos barajas iguales y luego barajadas juntas, alternando cada carta de una baraja con la carta correspondiente de la otra. En términos de representación binaria de los PE, cada etapa del barajado perfecto puede considerarse como un desplazamiento lógico cíclico a la izquierda ; cada bit en la dirección se desplaza una vez a la izquierda, con el bit más significativo moviéndose al bit menos significativo.
En cada etapa, pares adyacentes de entradas se conectan a un elemento de intercambio simple, que puede configurarse en modo directo (transfiere las entradas directamente a las salidas) o cruzado (envía la entrada superior a la salida inferior, y viceversa). Para N elementos de procesamiento, una red Omega contiene N/2 conmutadores en cada etapa y log₂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 por etiqueta de destino y el enrutamiento por etiqueta XOR, que se describen en detalle más adelante.
La red Omega es altamente bloqueante, aunque en una red libre siempre se puede crear una ruta desde cualquier entrada a cualquier salida.
Enrutamiento de etiquetas de destino
En el enrutamiento por etiqueta de destino, la configuración del conmutador se determina únicamente por el destino del mensaje. El bit más significativo de la dirección de destino se utiliza para seleccionar la salida del conmutador 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 conmutador 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, la configuración del conmutador es: superior, superior, inferior. Si el destino es PE 101, la configuración del conmutador es: inferior, superior, inferior. Esta configuración se mantiene independientemente del PE que envíe el mensaje.
Enrutamiento de etiquetas XOR
En el enrutamiento con etiquetas XOR, la configuración de los conmutadores se basa en la operación XOR entre el PE de origen y el PE de destino. Esta etiqueta XOR contiene unos en las posiciones de bits que deben intercambiarse y ceros en las posiciones de bits que el origen y el destino tienen en común. El bit más significativo de la etiqueta XOR se utiliza para seleccionar la configuración del conmutador en la primera etapa; si el bit más significativo es cero, el conmutador se configura para paso directo, y si es uno, se conecta. El siguiente bit más significativo de la etiqueta se utiliza para configurar el conmutador 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 la configuración de interruptores apropiada es: A2 directa, B3 cruzada, C2 cruzada.
Aplicaciones
En el procesamiento paralelo , las redes omega pueden utilizarse como conectores entre las CPU y su memoria compartida , con el fin de disminuir la probabilidad de que la conexión entre la CPU y la memoria se convierta en un cuello de botella.
Este tipo de redes se ha incorporado al multiprocesador Illinois Cedar, al IBM RP3 y al ultraordenador de la Universidad de Nueva York (NYU Ultracomputer) .
Ejemplos
- Simulación de red Omega en c
Véase también
Referencias
- Lawrie, Duncan H. (diciembre de 1975). "Acceso y alineación de datos en un procesador de matriz". IEEE Transactions on Computers . C-24 (12): 1145– 55. doi : 10.1109/TC.1975.224157 .
- Arquitectura de red