10-08-2012, 01:12 PM
Multi-Stage Interconnection Networks
Multi-Stage Interconnection.pdf (Size: 163.3 KB / Downloads: 110)
An Introduction to Interconnection Networks
A number of useful general surveys of interconnection networks have been published,
notably [99, 47, 95] with [132, 143] also being of some relevance. Much of the early
work on interconnection networks was motivated by the needs of the communica-
tions industry, particularly in the context of telephone switching. With the growth of
the computer industry, applications for interconnection networks within computing
machines began to become apparent. Amongst the rst of these was the sorting of
sequences of numbers, but as interest in parallel processing grew, a large number of
networks were proposed for processor to memory and processor to processor intercon-
nection [131]. With the advent of the fast packet switch, interest in interconnection
networks has turned full circle in that many of the networks originally proposed for
parallel processing are now being considered for use in fast packet switch designs.
A simple classication of interconnection networks according to topology will rst
be oered followed by some comments on the control mechanisms employed with the
various classes of multi-stage network. A discussion of the blocking characteristics of
the various networks will then lead into a detailed discussion of some of the multi-stage
interconnection networks useful in communications applications.
Topology
A simple, general classication of interconnection networks is presented in g. 4.1.
Regular, static networks, also called dedicated networks, are mostly used to inter-
connect loosely coupled processors to form parallel processing machines while any
general packet switching network may be classed as an irregular static network. Two
simple examples of dedicated path static networks are given in g. 4.2 in which pro-
cessing elements are connected by point-to-point links. Shared path static networks
are formed by interconnecting processing elements with buses. In general the use
of regular static networks has been restricted to the packet switched interconnection
of loosely coupled processors as the delay across the network is dependent upon the
distance between the communicating nodes. Also the processing delay required by
the routing algorithm may render the use of short packets inecient.
Control Mechanism
Interconnection networks may also be classied according to the control mechanism
employed to eect connections between input ports and output ports. If the al-
gorithm is centralised and implemented in a central processor then the state of all
existing connections and all connection requests may be consulted in order to make
the necessary routing decisions. The use of a centralised control mechanism implies
circuit switching where the holding time of a connection is much greater than the
time required to establish connection. The vast majority of modern telephone switch
designs use centralised control.
In fast packet switching applications the control mechanism must be distributed
across the switch fabric and must be capable of operating without access to infor-
mation regarding the entire state of the switch. Three classes of distributed routing
algorithm are relevant to a regular network: source routing, self-routing and regular
routing. Source routing requires a tag to be prexed to the packet which species
all of the routing decisions to be taken within the network, one eld of the tag for
each switch in the path. It thus removes the burden of route computation from
within the switch fabric to the periphery. The self-routing and regular routing con-
trol mechanisms are sometimes confused as both require a tag to be prexed to the
packet specifying the required destination output port number and both rely upon
the regularity of the interconnection network. Self-routing applies to dynamic, multi-
stage interconnection networks. It may be implemented such that each switching
element within the path makes a simple routing decision based only upon the tag of
the incoming packet independently of the position of the switching element within
the interconnection network. The regular routing mechanism applies to regular static
networks in which each network node makes a routing decision based upon the packet
tag and the position of the node within the network. This decision requires a certain
amount of computation and thus involves some delay. The regular routing algorithm
is thus best suited to conventional packet switching applications. The routing deci-
sion in a self-routing algorithm, however, requires no computation, does not involve
the maintenance of routing tables within the switch fabric, and may be executed by
very simple hardware within a single bit time. It is therefore of considerable interest
in fast packet switching applications.
The Crossbar Network
The crossbar network, or more often crossbar switch, is a non-blocking interconnection
network that derives its name from a particular switch implementation developed for
analogue telephone switching applications. The name is often taken to refer to non-
blocking networks in general.