Title :
Embedding a complete binary tree into a faulty supercube
Author :
Keh, Haun-Chao ; Lin, Jen-Chih
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Tamkang Univ., Tamsui, Taiwan
Abstract :
The supercube is a novel interconnection network that is derived from the hypercube. Unlike the hypercube, the supercube can be constructed for any number of nodes. That is, the supercube is incrementally expandable. In addition, the supercube retains the connectivity and diameter properties of the corresponding hypercube. In this paper, we consider the problem of embedding and reconfiguring binary tree structures in a faulty supercube. Further more, for finding the replaceable node of the faulty node, we allow 2-expansion such that we can show that up to (n-2) faults can be tolerated with congestion 1 and dilation 4 that is (n-1) is the dimension of a supercube
Keywords :
fault tolerant computing; hypercube networks; reconfigurable architectures; binary tree; connectivity; diameter properties; faulty supercube; interconnection network; reconfiguring binary tree structure; supercube; Bidirectional control; Binary trees; Computer science; Costs; Fault tolerance; Hypercubes; Multiprocessing systems; Multiprocessor interconnection networks; Topology;
Conference_Titel :
Algorithms and Architectures for Parallel Processing, 1997. ICAPP 97., 1997 3rd International Conference on
Conference_Location :
Melbourne, Vic.
Print_ISBN :
0-7803-4229-1
DOI :
10.1109/ICAPP.1997.651501
