An Omega network is a network configuration

Computer network

A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....

 often used in parallel computing

Parallel computing

Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...

 architectures

Computer architecture

In computer science and engineering, computer architecture is the practical art of selecting and interconnecting hardware components to create computers that meet functional, performance and cost goals and the formal modelling of those systems....

. It is an indirect topology that relies on the perfect shuffle interconnection algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

.

Connection Architecture

An 8x8 Omega network is a multistage interconnection network, meaning that processing elements (PEs) are connected using multiple stages of switches. Inputs and outputs are given addresses as shown in the figure. The outputs from each stage are connected to the inputs of the next stage using a perfect shuffle

Faro shuffle

The faro shuffle is a method of shuffling playing cards.In a perfect shuffle or perfect faro shuffle, the deck is split into equal halves of 26 cards which are then pushed together in a certain way so as to make them perfectly interweave....

 connection system. This means that the connections at each stage represent the movement of a deck of cards divided into 2 equal decks and then shuffled together, with each card from one deck alternating with the corresponding card from the other deck. In terms of binary representation of the PEs, each stage of the perfect shuffle can be thought of as a cyclic logical left shift

Logical shift

In computer science, a logical shift is a bitwise operation that shifts all the bits of its operand. Unlike an arithmetic shift, a logical shift does not preserve a number's sign bit or distinguish a number's exponent from its mantissa; every bit in the operand is simply moved a given number of bit...

; each bit in the address is shifted once to the left, with the most significant bit moving to the least significant bit.

At each stage, adjacent pairs of inputs are connected to a simple exchange element, which can be set either straight (pass inputs directly through to outputs) or crossed (send top input to bottom output, and vice versa). For N processing element, an Omega network contains N/2 switches at each stage, and log₂N stages. The manner in which these switches are set determines the connection paths available in the network at any given time. Two such methods are destination-tag routing and XOR-tag routing, discussed in detail below.

The Omega network is highly blocking, though one path can always be made from any input to any output in a free network.

Destination-tag routing

In destination-tag routing, switch settings are determined solely by the message destination. The most significant bit of the destination address is used to select the output of the switch in the first stage; if the most significant bit is 0, the upper output is selected, and if it is 1, the lower output is selected. The next-most significant bit of the destination address is used to select the output of the switch in the next stage, and so on until the final output has been selected.

For example, if a message's destination is PE 001, the switch settings are: upper, upper, lower. If a message's destination is PE 101, the switch settings are: lower, upper, lower. These switch settings hold regardless of the PE sending the message.

XOR-tag routing

In XOR-tag routing, switch settings are based on (source PE) XOR (destination PE). This XOR-tag contains 1s in the bit positions that must be swapped and 0s in the bit positions that both source and destination have in common. The most significant bit of the XOR-tag is used to select the setting of the switch in the first stage; if the most significant bit is 0, the switch is set to pass-through, and if it is 1, the switch is crossed. The next-most significant bit of the tag is used to set the switch in the next stage, and so on until the final output has been selected.

For example, if PE 001 wishes to send a message to PE 010, the XOR-tag will be 011 and the appropriate switch settings are: A2 straight, B3 crossed, C2 crossed.

Applications

In Multiprocessing, Omega networks may be used as connectors between the CPU's and their Shared Memory, in order to decrease the probabilty that the CPU-to-memory connection becomes a bottleneck.

See also

• Clos network
  Clos network
  In the field of telecommunications, a Clos network is a kind of multistage circuit switching network, first formalized by Charles Clos in 1953, which represents a theoretical idealization of practical multi-stage telephone switching systems. Clos networks are required when the physical circuit...
  
  
• Cube-connected cycles
  Cube-connected cycles
  In graph theory, the cube-connected cycles is an undirected cubic graph, formed by replacing each vertex of a hypercube graph by a cycle. It was introduced by for use as a network topology in parallel computing.- Definition :...
  
  
• Nonblocking minimal spanning switch
  Nonblocking minimal spanning switch
  A nonblocking minimal spanning switch is a device that can connect N inputs to N outputs in any combination. The most familiar use of switches of this type is in a telephone exchange. The term "non-blocking" means that if it is not defective, it can always make the connection...
  
  
• Banyan switch
  Banyan switch
  In electronics, a banyan switch is a complex crossover switch used in electrical or optical switches.It is named for its resemblance to the roots of the banyan tree which cross over in complex patterns. Logical banyan switches are used in logic or signal pathways to crossover switching of signals...
  
  
• Fat tree
  Fat tree
  The fat tree network, invented by Charles E. Leiserson of MIT, is a universal network for provably efficient communication. Unlike an ordinary computer scientist's notion of a tree, which has "skinny" links all over, the links in a fat-tree become "fatter" as one moves up the tree towards the root...
  
  
• Crossbar switch
  Crossbar switch
  In electronics, a crossbar switch is a switch connecting multiple inputs to multiple outputs in a matrix manner....
  
  
• Network coding
  Network coding
  Network coding is a technique where, instead of simply relaying the packets of information they receive, the nodes of a network will take several packets and combine them together for transmission. This can be used to attain the maximum possible information flow in a network...