Reliability Analysis of Mux - Demux Replicated Multistage Interconnection Networks

The performance of most digital systems today is limited by their communication or interconnection, not by their logic or memory. The pin density and wiring density that govern interconnections between system components are scaling at a slower rate than the components themselves. Also, the frequency of communication between components is lagging far beyond the clock rates of modern processors. These factors combine to make interconnection the key factor in the success of future digital systems. The basic function of an interconnection network is to transfer information from the input nodes of the network to the output nodes by setting up communication paths for routing through the network, in an efficient manner. Because the cost of a crossbar network is too high to be practical for building large multiprocessor systems, an alternative to the crossbar network is multistage interconnection network (MIN).1,2 Multiple buses may be a choice, although throughput is a bottleneck. The interconnection network topologies can be broadly classified as static and dynamic. In a static network, point-to-point links interconnect the network nodes in some fixed topology, like mesh or hypercube. These networks are also referred to as direct networks. Such networks have the advantage of being simple to build and expand, requiring a simple routing algorithm. But such a network fails even in the presence of a single fault, without overheads. Many static networks have been proposed; examples include the Omega Network and the Baseline Network. A dynamic network allows the interconnection pattern among the network nodes to be varied dynamically, being accomplished by some form of switching. Examples of dynamic networks include ASEN, ABN, and so forth, and many bus-based networks. The routing path is fixed in a static MIN, while in a dynamic MIN it is adaptable according to faults/traffic present. To design MINs, small crossbar switches organized in stages are used. A large number of network designs based on Clos3 and Benes4 networks have been proposed and used in the past three decades. Clos Network was first outlined by Charles Clos in 1953. The first stage of the network consists of r switches, each of size n×m; middle stage has m switches of size r×r each; and the last stage is the mirror image of the first. Thus, the network has N=rn input terminals and output terminals. Most of the MINs proposed in the literature are usually constructed using 2 × 2 crossbar switches and have n= log2N stages, every stage consisting of N/2 switching elements (SEs). Total number of switches in the network is N/2 (log2N) for N×N network, as compared to O(N2) for a crossbar network. Omega Network5 maintains a uniform connection pattern between stages. Every input terminal has a unique path to every output terminal and exhibits the property of self-routing, that is, routing is performed in a distributed manner using destination address as the “routing tag.” If the stages of Omega Network are traversed backward, inverse path from destination to source is accomplished between stages, to get the inverse Omega Network, which is also a useful MIN in parallel processing environment as it sufficiently supports the communication patterns in several parallel algorithms such as Fast Fourier Transforms and matrix operations. A wide range of proposed topologies may have a uniform or nonuniform connection pattern between stages. If the number of SEs is the same in each stage, then the MIN is specified as regular, otherwise it is irregular. Applications of regular topologies include such usage where latency provided by all paths is the same. Cube Network is an example of a regular MIN wherein which the SEs are interconnected as the corners of an m-dimensional cube.6 Irregular topologies provide paths of varying lengths, thus reducing the average latency considerably. The irregular Double Tree Network, originally proposed by Levitt et al.,7 has found application in the design of MIT data flow processor.8 Many paths of diverse length are available between any input and output. Other examples of static MINs include the Shuffle-Exchange Network (SEN),9 the Delta Network,10 Generalized Shuffle-Exchange Network (GSN),11 Data Manipulator Network,1 and Indirect Binary n-cube Network.12 Topological equivalence of several of these networks has been established.13 These networks can also be constructed by using larger sized SEs with corresponding reduction in the number of stages and hence in the latency offered by the network. Unique-path M×N SEN,9 where M=m1m2…mm inputs and N=n1n2…nn. outputs, is composed of r identical stages of SEs sized mi×ni, the ith stage (1 < i < r) incorporating M (n1n2…Nn−1)/(m1m2…mi) crossbar switches. Delta Networks introduced by Patel10 have the property of digit-controlled routing, which means that a path can be set up through the network in a distributed manner by using individual bits of the destination address. The radix may be 2 or higher. This network has m stages of switches sized a×b, having am input terminals and bm output terminals. A further generalization of Delta Networks called Generalized Shuffle-Exchange Network was introduced by Bhuyan and Agrawal.11 A GSN with N inputs, M outputs, and r switching stages can be constructed if both N and M are expressible as products of r integers. The integer in such a factorization determines the size of SEs in the r stages. A generalization of the perfect shuffle is used as the interconnection pattern between stages. Thus, these networks belong to the class of irregular banyan networks with r levels