DocumentCode
851897
Title
Incomplete hypercubes
Author
Katseff, Howard P.
Author_Institution
AT&T Bell Labs., Holmdel, NJ, USA
Volume
37
Issue
5
fYear
1988
fDate
5/1/1988 12:00:00 AM
Firstpage
604
Lastpage
608
Abstract
Since a k -dimensional hypercube has 2k vertices, these systems are restricted to having exactly 2k computing nodes. Because system sizes must be a power of two, there are large gaps in the sizes of systems that can be built with hypercubes. Routing and broadcast algorithms are presented for hypercubes that are missing certain of their nodes, called incomplete hypercubes. Unlike hypercubes, incomplete hypercubes can be used to interconnect systems with any number of processors. The routing and broadcast algorithms for incomplete hypercubes are shown also to be simple and deadlock-free
Keywords
multiprocessor interconnection networks; broadcast algorithms; deadlock-free; incomplete hypercubes; interconnection topology; k-dimensional hypercube; routing; Broadcasting; Hypercubes; Joining processes; Multiprocessing systems; Power system interconnection; Routing; System recovery; Topology;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.4611
Filename
4611
Link To Document