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

Research output: Contribution to journalConference articlepeer-review

12 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)278-287
Number of pages10
JournalProceedings of the International Conference on Parallel Processing
StatePublished - 1989
Externally publishedYes
EventProceedings of the 1989 International Conference on Parallel Processing - University Park, PA, USA
Duration: Aug 8 1989Aug 12 1989

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture


Dive into the research topics of 'Fault-tolerant routing algorithm for BPC permutations on multistage interconnection networks'. Together they form a unique fingerprint.

Cite this