The Omega Network is an interconnect configuration commonly used in parallel computing architectures when a uniform access to memory is needed, in other words, all accesses have a fixed access time. The motivation to use this topology comes from its better scalability compared the crossbar topology and from not be totally blocking as the bus configuration.

How is the network is generated?

First, a Omega network must have the same number N of CPUs and Memories. After being set this value N, log2N routing stages should be placed between the CPUs and Memories. Each stage will have N / 2 swithces responsible for the routing algorithm. A Switch has 2 input and 2 output ports. After having organized the CPUs in a column, the switches in a N / 2xlog2N matrix and the Memories in another column, the inbound and/or output ports of the CPUs, Switches and Memories are numbered sequentially from the top down. Thus the first CPU will have an output 0, the second CPU will be output 1 and so forth. The first row of Switches, will have the 0 and 1 output ports. The second row will have 2 and 3 and so on. This topology uses a rotation to the left of the source port number to determine the destination port and thus connect them.

For example, in a network 8x8 a output port 010 (2), regardless of which column it belongs, will have its number left rotationed to determine which input port it will be connected. In this case, it must be attached to port 100 (4): the first input port from Switch 3 in the next routing stage. This algorithm is the same for the connections CPU / 1stStage(routing) and between all of the connections (K-1) thStage-> KthStage, where 2 ≤ K ≤ log2N. However, the links from the last switches column and the memories is done differently. The output N in the Switches will be linked to the input N in the Memories. In the same example of the previous 8x8 grid, the output 001 (second output of the first Switch) is connected to the same port 001 which corresponds to the input of Memory 2.

The Switches and the routing Algorithm.

The switches receive a message on the input port and pass it to the correct output port. Each messageis made up by the following fields:

• Module - Has the target module (CPU or Memory).

• Address - the to be accessed memory address.

• Opcode - Indicates what type of messagem (eg writing or reading)

• Value - has the value to be written or read from the Memory.

The routing algorithm is simple: a Switch on stage K in a NxN network, upon receiving a message will analyze the most significant K bit on the Module field. If it’s 0, the message will exit form the first output port. If it’s 1, the message will through the second. For example, in a 8x8 grid a second stage switch will examine the second bit from left to right. If the Module field carries the following sequence 010, bit 1 in bold will be used for analysis and the message will be passed through the second output port.

How does a message knows its way back?

When a message carries a read operation, the destination memory must respond to the CPU that made the request. To the memory be able of knowing the origin CPU, the Switches must update the bits in the Module field of the message as it is routed. Each Switch, after determining through which outport the message should pass, replaces the corresponding analyzed bit by the port that the message arrived. For example, if the message has reached the switch through the first input port and the Module field contains the same 010 as the earlier example, the bit 1 will be changed to 0 and the new module will be 000. If it had arrived on the second input port, the bit 1 would be overwritten by another bit 1. Since this bit modification is irrelevant to the next routing steps, there will be no problems. When the message arrives at the Memory, the Module field will contain the origin CPU number. This value will be used by switches on the way back using the same routing algorithm.

Omega Network according Andrew S. Tanenbaum as shown in his book Modern Operating Systems 4th edition.