Identification of Operational Subcubes in Unreliable Hypercubes

Document Type

Article

Publication Date

3-1992

Publication Title

IEE Proceedings-E Computers and Digital Techniques

Volume

139

First page number:

117

Last page number:

122

Abstract

Hypercube multiprocessors can efficiently execute a wide class of parallel algorithms. To obtain a reliable result, the correct operation of all processors in the network must be ensured. However, the number of processors in a hypercube network grows exponentially with the network dimension, making the network susceptible to node failures. Fortunately, most of the basic algorithms developed for networks such as the hypercube can be formulated with the dimension of the network as a parameter of the algorithm. Therefore it is essential to investigate methods to identify the operational subcubes (OPSCs) contained in a hypercube with some faulty node processors. The paper proposes centralised and distributed algorithms to identify OPSCs in an n-cube when the faulty processors are abundant. By utilising the properties of an unreliable environment, the proposed algorithms can identify all the largest OPSCs efficiently. Such algorithms are highly desirable since, in general, the problem of finding an OPSC in a damaged cube has an exponential time complexity.Methods are given to update the status of OPSCs dynamically once a working node fails or a faulty node is repaired.

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