INCOMPLETE HYPERCUBES

被引：164

作者：

KATSEFF, HP

机构：

[1] AT&T Bell Lab, Holmdel, NJ, USA, AT&T Bell Lab, Holmdel, NJ, USA

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1988年 / 37卷 / 05期

关键词：

COMPUTER PROGRAMMING - Algorithms - COMPUTERS - Data Communication Systems - MATHEMATICAL TECHNIQUES - Topology;

D O I：

10.1109/12.4611

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Since a k-dimensional hypercube has 2**k vertices, these systems are restricted to having exactly 2**k 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.

引用

页码：604 / 608

页数：5