Fault-tolerant Hypercube Multiprocessors

Document Type

Article

Publication Date

8-1990

Publication Title

IEEE Transactions on Reliability

Volume

39

First page number:

361

Last page number:

368

Abstract

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.

Keywords

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

Disciplines

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

Language

English

Permissions

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

Share

COinS