Abstract
In this paper, we present a reconfiguration approach to identify the maximal fault-free subcube-ring for tolerating faults in faulty hypercubes. The fault-free subcube-ring is connected by a ring of fault-free subcubes with dilation 3. By exploiting the size of fault-free subcubes as large as possible, the maximal fault-free subcube-ring with higher processor utilization is obtained. Using this approach, we can tolerate more than n faults in n-dimensional hypercubes. To demonstrate the fault-tolerant capability of our approach, we implement a fault-tolerant matrix-multiplication algorithms on the nCUBE/2E hypercube machine with 32 processors. The simulation results show that our reconfiguration approach has low performance slowdown and high processor utilization.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
NCUBE corporation: nCUBE/2 processor manual. NCUBE corporation. (1990).
F. T. Leighton: Introduction to parallel algorithms and architecture: array · tree · hypercube. Morgan Kaufmann Publishers. (1992).
J. Berntsen: Communication efficient matrix multiplication on hypercubes. Parallel Comput. 12 (1989) 335–342.
J. Bruck, R. Cypher, and D. Soroker: Tolerating faults in hypercubes using subcube partitioning. IEEE Trans. Comput. 41, 5 (1992) 599–605.
H. L. Chen and N. F. Tzeng: Quick determination of subcubes in a faulty hypercube. Proc. of 21th Int. Conf. Parallel Processing. 3 (1992) 338–345.
H. L. Chen and N. F. Tzeng: Distributed identification of all maximal incomplete subcubes in a faulty hypercube. Proc. of the 8th Int. Parallel Processing Symp. (1994) 723–728.
C. S. Raghavendra, P. J. Yang, and S. B. Tien: Free dimension — an effective approach to achieving fault tolerance in hypercubes. Proc. of Int. Symp. Fault-Tolerant Comput. (1992) 170–177.
J. P. Sheu: Fault-tolerant parallel k selection algorithm in n-cube networks, Information Processing Letters. 39, 2, (1992) 93–97.
J. P. Sheu, Y. S. Chen, and C. Y. Chang: Fault-tolerant sorting algorithm on hypercube multicomputers. J. Parallel and Distributed Comput. 16, 2 (1992) 185–197.
S. B. Tien, and C. S. Raghavendra: Simulation of SIMD algorithms on faulty hypercubes. Proc. of 20th Int. Conf. Parallel Processing. 1 (1991) 716–717.
Y. C. Tseng and T. H. Lai: Ring embedding in an injured hypercube. Proc. of 22th Int. Conf. Parallel Processing. 3 (1993) 149–152.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sheu, JP., Chen, YS. (1995). Tolerating faults in faulty hypercubes using maximal fault-free subcube-ring. In: Haridi, S., Ali, K., Magnusson, P. (eds) EURO-PAR '95 Parallel Processing. Euro-Par 1995. Lecture Notes in Computer Science, vol 966. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0020500
Download citation
DOI: https://doi.org/10.1007/BFb0020500
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60247-7
Online ISBN: 978-3-540-44769-6
eBook Packages: Springer Book Archive