Testing the Dynamic Full Access Property of a Class of Multistage Interconnection Networks

Tsern-Huei Lee, Jin Jye Chou

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

A banvan network and its topologically equivalent ones have recently been adopted as the interconnection networks in a multiprocessor system. Often a multiprocessor system is reconfigured when the banyan network becomes faulty. It is possible to avoid a complicated reconfiguration process as long as the faulty banyan network still possesses the dynamic full access (DFA) property. In this short note, we determine a necessary and sufficient condition for a faulty banyan network to possess the DFA property and design a testing procedure based on the condition. The testing procedure can be used to decompose a faulty banyan network into subsystems possessing the DFA property. We also evaluate the probability that a banyan network loses the DFA property, given the number of faulty switching elements. It is found that as long as faults do not occur in switching elements located in the first and the last stages, this probability is very small, even when there are quite a few faulty switching elements.

Original languageEnglish
Article number329668
Pages (from-to)1206-1210
Number of pages5
JournalIEEE Transactions on Parallel and Distributed Systems
Volume5
Issue number11
DOIs
StatePublished - Nov 1994

Keywords

  • dynamic full access
  • fault tolerance
  • Multiprocessor system
  • multistage interconnection networks

Fingerprint Dive into the research topics of 'Testing the Dynamic Full Access Property of a Class of Multistage Interconnection Networks'. Together they form a unique fingerprint.

Cite this