Fault-tolerant hypercube multiprocessors

The author presents a new design, called fault-tolerant hypercube (FTH), obtained by augmenting the hypercube topology with some extra links. The FTH has a graceful degradation in performance with the existence of faults. The hardware (link redundancy) is small and negligible for hypercubes with large dimensions. A probabilistic model based on a Markov chain characterizes the FTH-subcube reliability. The mean time to failure is at least 22% better than that for the conventional hypercube. The results have been verified by Monte Carlo simulation. The FTH design is simple and easy to implement. This network can lend itself to the execution of many parallel algorithms designed to run on hypercubes. The FTH contains many more subcubes than the standard hypercube, and thus executes tasks requiring various cube sizes. Where allocation and deallocation of tasks to various subcubes is a common practice, this design achieves an excellent processor usage by efficiently and compactly assigning subcubes