On gracefully degrading multiprocessors with multistage interconnection networks

The behavior of a multiprocessing system with a multistage interconnection network is studied in the presence of faulty components. Measures for the connectivity and performance of these systems are proposed, including the average number of operational paths, the average number of accessible processors and memories, the average number of fault-free processors (memories) that are connected to an accessible memory (processor), the bandwidth, and the processing power of the system. Based on these measures, a tight upper bound for the maximal fully connected system is suggested. The gracefully degrading system is then compared, through some numerical examples, to a system whose faulty components are repaired upon failure. Based on these comparisons, the anticipated reduction in system performance can be estimated and consequently, appropriate maintenance policies can be determined