Omega network

From Wikipedia, the free encyclopedia

This article is orphaned as few or no other articles link to it. Please help introduce links in articles on related topics. (November 2006)

An Omega network is a network configuration often used in parallel computing architectures. It is an indirect topology that relies on the perfect Shuffle interconnection algorithm.

[edit] Properties of Omega Networks

1. For N=2^K inputs, there are K stages, with N/2 exchange elements at each stage.
2. In an Omega Network, the outputs from one stage are connected to the inputs of the next stage using a Perfect Shuffle connection system. This is true for all stages except the last one where direct connections to exist. What this means is that the connections at each stage represent the movement of a deck of cards divided into 2 and then shuffles with each card from one deck alternating with the corresponding card from the other deck.
3. An Omega Network is a blocking network in the sense that because input(and output) lines are multiplexed, there may be blocking under certain conditions.

[edit] Explanation

The diagram shows an Omega Network connecting 8 CPUs with 8 Memory modules. The 8 boxes on the left are the 8 CPUs whereas the 8 boxes on the right are Memory modules. The exchangers in the middle are named A, B and C respectively, according to which level they belong to.

Exchanger A switches based on the MSB of the request(requested memory module). Exchanger B switches based on the middle bit of the request and exchanger C switches based on the LSB of the request. For each exchanger(or switch), the top path is taken if the bit under question is reset(0) and the bottom path is taken if the bit under question is set(1).

For example, if CPU 6(110) makes a request for memory module 2(010), the path followed will be: A3, B1, C2.

In general, the number of destinations(in this case memory modules) dictates how many exchangers and stages there are to be. For example, if we were to change the number of CPUs to either 4 or 16, the number of exchangers and their positions would remain the same.