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).