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

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

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
Volume1
StatePublished - Dec 1 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint 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