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

fYear

1997

fDate

10-12 Dec 1997

Firstpage

323

Lastpage

330

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ICAPP.1997.651501

Filename

651501