Fault-tolerant routing algorithm for BPC permutations on multistage interconnection networks

A control scheme is presented for routing the bit-permute-complement (BPC) class of permutations on multistage interconnection networks. A general class of networks is considered which includes the Benes permutation network, a network with 2 log N-1 stages of shuffle exchange, etc. The scheme uses log N bits to control each stage of N/2 switching elements, rather than N/2 control bits as used by previous methods. The author give an efficient algorithm for computing the control bits in O(log N) time. The control scheme offers several advantages over previously known methods. First, it leads to some degree of fault-tolerance. Second, it results in a more efficient routing algorithm for parallel computers with bit-serial communication links. In particular, the resulting algorithm for a bit-serial perfect-shuffle-computer is faster than the best previously known results by a factor of log N.