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.
|Number of pages||5|
|Journal||IEEE Transactions on Parallel and Distributed Systems|
|State||Published - Nov 1994|
- dynamic full access
- fault tolerance
- Multiprocessor system
- multistage interconnection networks