A class of fault-tolerant multiprocessor networks

A class of efficient interconnection networks for large multiprocessor systems is introduced. The important characteristics of these networks are their capability of maximal fault-tolerance, higher density, admitting simple distributed-routing algorithms both for the faulty and fault-free network, and ease of self diagnosis. The fault-tolerant routing is fully distributed and does not require any topological table. The self-diagnostic algorithm is semidistributed, and is based on a combinatorial structure known as the Hadamard matrix. The diagnostic scheme has high degree of fault-tolerance, which asymptotically approaches to a level of 100%. The scheme can be made more secure and fault-tolerant by using various froms of Hadamard matrix.>