A Rede Ômega é uma configuração de interconexões comumente utilizada em arquiteturas de computação paralela em que se deseja uma acesso uniforme a memoria, ou seja, todos acessos possuem um tempo de acesso fixo. A motivação de usar essa topologia vem da sua melhor escalabilidade se comparada a topologia Crossbar e não ser totalmente bloqueante como a configuração de barramento.

Como a rede é gerada?

Primeiramente, uma rede Ômega deve ter o mesmo numero N de CPUs e Memórias. Fixado esse valor N, deve-se colocar logN (base 2) estágios de roteamento entre as CPUs e a Memoria. Cada estagio terá N/2 Swithces responsáveis pelo algoritimo de roteamento. Um Switch possui 2 portas de entrada e 2 de saída. Após ter organizado as CPUs em uma coluna, os Switches em uma matriz N/2xlogN (base 2) e as Memorias em outra coluna, as portas de entrada e/ou saida das CPUs, Switches e Memorias são numeradas sequencialmente de baixo para cima. Dessa forma a primeira CPU terá uma saida 0, a segunda CPU terá a saida 1 e assim sucessivamente. No caso dos Switches da primeira linha, existirão as seguintes entradas 0 e 1. No Switches da segunda linha , tem-se as entradas 2 e 3 e assim sucessivamente. Essa topologia utiliza uma rotação a esquerda do numero da porta de origem para determinar a porta de destino e assim, conectá-las.

Por exemplo, em uma rede 8x8 uma porta 010 (2), independente de qual coluna pertencer, terá seu número rotacionado para determinar em que porta será conectada. Nesse caso, ela deverá ser ligada à porta 100 (4), ou seja, a primeira porta de entrada do Switch 3 no estágio seguinte. Esse algoritimo é o mesmo para as conexões CPU/1ºEstagio (de roteamento) e entre todos os estagios seguintes (K-1)ºEstagio -> KºEstagio, onde 2 ≤ K ≤ logN (base 2) . No entanto, as ligações da última coluna de Switches às Memorias é feito de forma diferente. As saídas N serão ligadas as entradas N nas Memorias. No mesmo exemplo da rede 8x8 anterior, a saída 001 (segunda saída do primeiro Switch) será ligada a mesma porta 001 que corresponde a entrada da Memória 2.

Os Switches e o Algoritimo de roteamento.

Os Switches recebem uma mensagem nas portas de entrada e repassam para porta de saída correta. Cada mensagem é composta pelos campos:

O algoritimo de roteamento é simples: um Switch do estágio K em uma rede NxN, ao receber uma mensagem irá analisar o bit K mais significativo do campo Modulo. Caso 0, repassará para sua primeira porta; caso 1, repassará para segunda. Por exemplo, em uma rede 8x8 um Switch do segundo estágio irá analisar o segundo bit da esquerda para a direita. Caso o campo Modulo apresente a seguinte sequencia 010, o bit 1 em negrito será utilizado para a análise e a mensagem será repassada para segunda porta do Switch.

Como uma mensagem sabe seu caminho de volta?

Quando uma mensagem carrega uma operação de leitura, a memória de destino deve responder à requisição endereçando de volta mensagem a CPU que fez o pedido. Para a memoria ter conhecimento da CPU de origem os Switches devem atualizar os bits no campo Modulo da mensagem conforme ela é roteada. Cada Switch após determinar a porta de saída da mensagem, substitui o bit analisado pelo correspondente a porta que a mensagem chegou. Por exemplo, se a mensagem chegou na primeira porta, e o campo modulo contem o mesmo 010 do exemplo anterior, o bit 1 será trocado para 0 e o novo modulo será 000. Caso, ela tivesse chegado na segunda porta, o bit 1 seria sobrescrevido por outro bit 1. Como esse bit trocado e os mais significativos que ele são irrelevantes para as próximas etapas de roteamento, não há problemas. Quando a mensagem chegar a memória, o campo modulo terá o número da CPU que fez a requisição e esse valor será utilizado pelos Switches no caminho de volta por meio do mesmo algoritimo de roteamento da ida.

Rede Ômega segundo Andrew S. Tanenbaum apresentado em seu livro Modern Operating Systems 4ª edição.