Fault-tolerant hypercube multiprocessors

Document Type



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.


Computer network resources; Fault-tolerant computing; Hypercube networks (Computer networks); Parallel algorithms; Routing (Computer network management)


Computer and Systems Architecture | Computer Engineering | Digital Circuits | Digital Communications and Networking | Electrical and Computer Engineering | Systems and Communications


Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library