Reconfiguration of self routing networks for the realization of an arbitrary set of permutations a feasibility study

Abstract

This thesis deals with the Feasibility study of Reconfiguration of Self-Routing Networks for the Realization of an Arbitrary Set of Permutations. Interconnection Networks (IN) are capable of allowing simultaneous communication between the memory blocks and the processing elements and hence are considered as the heart of the parallel systems. A class of interconnection networks, called permutation networks, consists of multiple stages, each stage having N/2 (2 x 2) cross-bar switches. An in-depth study is made to have an idea on the construction and design of the Baseline network, the Omega network, the Generalized Delta network, and the BIPED networks. All these networks are called Self-routing Permutation Networks, because the routing is done by the network itself for the given permutation. A permutation P is said to be passable or realizable by a network, if there exists switch settings such that the one-to-one onto function defined by P is realized. (N x N) Baseline network is one of the self-routing permutation networks employed in many parallel computing systems. It connects equal number of inputs and outputs, and realizes as many as 2(N/2) * log2N permutations. Since, exactly one path exists between any input-output pair, for a given arbitrary permutation, conflict may arise whenever more than one input - output transfers require a common link. Later, Dr. Dharma P. Agrawal provided a methodology to reconfigure the inputs of a Baseline Network so as to realize any arbitrary permutation, keeping in mind that a typical application may most of the times use this permutation. 1 In this thesis, necessary and sufficient condition for the passability of a permutation using Baseline network is derived. A methodology is provided to reconfigure the inputs of a Baseline network so as to realize any arbitrary pair of permutations making use of this result. It is then shown that such a reconfiguration is not feasible in the Baseline network for the realization of an arbitrary triple permutations, leading to the conclusion that the reconfiguration of Baseline network is not feasible for an arbitrary set of permutations. In this thesis, from among (an x bn) Delta networks, (rn x rn) Delta networks are considered to study the permuting capabilities. The algorithm to reconfigure the inputs of the Baseline network to realize an arbitrary pair of permutations is extended and tested for the admissibility of a pair of permutations using (3n x 3n) Delta network. It is then shown that such a reconfiguration is not even feasible for the realization of a set of triple permutations. The class of BIPED networks is a subclass of Delta networks. These Biped networks have many Self-routing Permutation Networks, that are non-equivalent to Baseline network, though Baseline network itself is a special case of BIPED Network. An (N x N) Biped will be having N inputs and N outputs. The feasibility study and analysis done for Baseline network is extended to these BEPEDs also. Permuting capabilities of BIPED network is analyzed through a graphical perspective and it is then proved that it is not possible to reconfigure Biped networks for n the realization of any arbitrary set of permutations. All these above results help close one of the problems thrown open by Dr. Agrawal in 1983, that people should work towards reconfiguration of networks for the realization of an arbitrary set of permutations. The other important conclusion is that it will be of no use even if one employs permutation networks like Bipeds, which are non-equivalent to the Baseline network, as even Biped cannot be reconfigured for the realization of an arbitrary set of permutations. Hence, one shall employ only Baseline network, as its connection patterns are regular and VLSI implementation of which will also be simple, and attempts to derive non-equivalent networks shall come to an end. in