La Red de Omega es una configuración de interconexión de uso común en las arquitecturas de computación paralela con un acceso uniforme a la memoria, es decir, todos los accesos tienen un tiempo de acceso fijo. La motivación para utilizar esta topología viene de su mejor escalabilidad como cuando comparada a la topología Crossbar y por no ser tan bloqueadora como la configuración del bus.

Como se genera la red?

En primer lugar, una red Omega debe tener el mismo número N de CPUs y Memorias. Establecido este valor N, se debe poner log2N etapas de enrutamiento entre CPU y memoria. Cada etapa tendrá N / 2 switches responsables por el algoritmo de enrutamiento. Un switch tiene 2 puertos de entrada y 2 de salida. Después de haber organizado las CPUs en una columna, los switches en un cuartel N / 2xlog2N y las Memorias en otra columna, los puertos de entrada y / o de salida de las CPUs, switches y memorias se numeran secuencialmente, de abajo hacia arriba. Así, la primera CPU tendrá una salida 0, la segunda CPU tendrá salida 1, y así sucesivamente. En el caso de los switches de la primera fila, existen las siguientes entradas 0 y 1. En los switches de la segunda fila, existen las entradas 2 y 3 y así sucesivamente. Esta topología utiliza una rotación a la izquierda del número de puerto de origen para determinar el puerto de salida y de este modo conectarlo.

Por ejemplo, en una red de 8x8, un puerto 010 (2), independiente de la columna a la cual pertenece, tendrá su número rotacionado para determinar a cual puerto se conectará. En este caso, debe ser conectado al puerto 100 (4), es decir, el primer puerto de entrada del switch 3 en la etapa siguiente. Este algoritmo es el mismo para las conexiones de CPU / 1ºEstagio (de enrutamiento) y entre todas las siguientes etapas (K-1) ºEstagio -> KºEstagio, donde 2 ≤ K ≤ log2N. Sin embargo, los enlaces de la última columna de switches hacia las memorias se hace de otra manera. Las salidas N estarán vinculadas a las entradas N en las Memorias. En el mismo ejemplo de la red 8x8 anterior, la salida 001 (segunda salida del primer switch) estará conectada al mismo puerto 001 que corresponde a la entrada 2 de la memoria.

Los switches y el Algoritmo de enrutamiento.

Los switches reciben un mensaje en los puertos de entrada y las pasan para el puerto de salida correcto. Cada mensaje esta compuesto por los campos:

El algoritmo de enrutamiento es simple: yn switch de etapa K en una red de NxN, al recibir un mensaje analizará el más significativo bit K del campo Modulo. Si es 0, se trasladará a su primer puerto; si es 1, se trasladará al segundo. Por ejemplo, en una red 8x8 un switch de la segunda etapa examinará el segundo bit de la izquierda a la derecha. Si el campo Modulo muestra la siguiente secuencia 010, el bit 1 en negrita se utilizará para análisis y el mensaje será pasado al segundo puerto del switch.

Como un mensaje sabe su camino de regreso?

Cuando un mensaje lleva una operación de lectura, la memoria de destino debe responder a la solicitud enviando el mensaje de vuelta a la CPU que realizó la solicitud. Para que la memoria tenga el conocimiento de la CPU de origen los switches deben actualizar los bits en el campo Módulo del mensaje, como esta se encamina. Cada switch, después de determinar el puerto de salida del mensaje, sustituye el bit analizado por su correspondiente al puerto en el que el mensaje llegó. Por ejemplo, si el mensaje ha llegado al primer puerto, y el campo modulo contiene el mismo 010 del ejemplo anterior, el bit 1 se cambia a 0 y el nuevo módulo será 000. Si hubiese llegado al segundo puerto, el bit 1 sería sobrepuesto por otro 1. Como este bit modificado y los más significativos que él son irrelevantes para los próximos pasos de enrutamiento, no hay problemas. Cuando el mensaje llega a la memoria, el campo módulo tendrá el número de la CPU que hizo la solicitud y ese valor será utilizado por los switches en el camino de vuelta por el mismo algoritmo de enrutamiento del viaje.

Red Omega, segun Andrew S. Tanenbaum presentado en su libro Modern Operating Systems 4ta edición.