Fault tolerant broadcasting algorithms in SIMD hypercubes /
Abstract: "We study the problem of broadcasting in faulty SIMD hypercube multiprocessors subject to node failures. In a faulty SIMD hypercube of dimension n containing n - 1 or fewer faulty nodes, the best known broadcasting algorithm takes n + 12 steps to forward the message from a source no...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Book |
| Language: | English |
| Published: |
College Station, Tex. :
Texas A & M University, Computer Science Dept.,
[1993]
|
| Series: | Technical report (Texas A & M University. Computer Science Department) ;
93-044. |
| Subjects: |
| Summary: | Abstract: "We study the problem of broadcasting in faulty SIMD hypercube multiprocessors subject to node failures. In a faulty SIMD hypercube of dimension n containing n - 1 or fewer faulty nodes, the best known broadcasting algorithm takes n + 12 steps to forward the message from a source node to all other fault-free nodes. In this paper, we propose an optimal broadcasting algorithm which requires only n + 1 steps. The basic idea of the proposed algorithm is to find a specific dimension sequence as follows. We first find a fault-free subcube (C[subscript S]) which contains the source node (S) such that each neighboring subcube of the subcube C[subscript S] contains at least one fault. Next, the message is broadcast along the internal dimensions followed by external dimensions of the subcube C[subscript S]. This process requires n steps. Since this process does not guarantee that all the fault-free nodes receive the message, an extra step may be needed. We prove that there exists an internal dimension of the subcube C[subscript S] such that all the nodes which did not receive the message in n steps will receive the message by broadcasting the message along that dimension. An efficient algorithm is presented to find the dimension sequence for broadcasting. In order to tolerate more than n - 1 faulty nodes, we develop a divide-and-conquer scheme which takes at most n + 7 and n + 22 steps for broadcasting in an n-cube containing 2n - 3 and 4n - 9 faults, respectively. A generalized broadcasting algorithm is also developed to tolerate any number of faults with a very high probability. The effectiveness of this algorithm is demonstrated by simulation results." |
|---|---|
| Physical Description: | 20 leaves : illustrations ; 28 cm. |
| Bibliography: | Includes bibliographical references. |