ALGORITHMS TO REALIZE AN ARBITRARY BPC PERMUTATION IN CHORDAL RING NETWORKS AND MESH-CONNECTED NETWORKS

A multiple instruction stream-multiple data stream (MIMD) computer is a parallel computer consisting of a large number of identical processi ng elements. The essential feature that distinguishes one MIMD compute r family from another is the interconnection network. In this paper, 2 representative types of interconnection networks are dealt with the c hordal ring network and the mesh connected network. A family of regula r graphs of degree 3, called chordal rings is presented as a possible candidate for the implementation of a distributed system and for fault -tolerant architectures. The symmetry of graphs makes it possible to d etermine message routing by using a simple distributed algorithm. Anot her candidate having the same property is the mesh connected networks. Arbitrary data permutations are generally accomplished by sorting. Fo r certain classes of permutations, however, there exist algorithms tha t are more efficient than the best sorting algorithm. One such class i s the bit permute complement (BPC) class of permutations. The class of BPC permutations includes many of the frequently occurring permutatio ns such as bit reversal, bit shuffle, bit complement, matrix transpose , etc. In this paper, we evaluate the abilities of the above networks to realize BPC permutations. In this paper, we, first, develop algorit hms required 2 token storage registers in each node to realize an arbi trary BPC permutation in both chordal ring networks and mesh connected networks. We next evaluate the ability to realize BPC permutations in these networks of an arbitrary size by estimating the number of requi red routing steps.