A realization of arbitrary BPC permutations in bidirectional hypercube and chordal ring networks

A multiple instruction stream-multiple data stream (MIMD) computer is a parallel computer with a large number of identical processing elements. The essential feature that distinguishes each MIMD computer family is the interconnection network. In this paper, we are concerned with two representative types of interconnection networks that are called the hypercube and the chordal ring networks. A family of regular graphs is presented as a possible candidate for the implementation of a distributed system and for fault-tolerant architecture. The symmetry of these graphs makes it possible to determine message routing by using a simple distributed algorithm. Arbitrary data permutations are generally accomplished by sorting. For certain classes of permutations, however, (for example, many frequently used permutations in parallel processing, such as bit reversal, bit shuffle, bit complement, matrix transpose, butterfly permutations in FFT algorithms, and segment shuffles), there are algorithms that are more efficient than the best sorting algorithm. One of these is the bit permute complement (BPC) class of permutations. We have developed algorithms for bidirectional networks. The developed algorithm in hypercube networks requires only 1 token memory register in each node. The algorithm takes the same number of steps as the maximum Hamming distance. Therefore, we have concluded that the presented algorithm is the optimal one. On the other hand, the developed algorithm in chordal ring networks requires 2 token storage register. The number of required routing steps in two kinds of networks is evaluated