INCOMPLETE HYPERCUBES - ALGORITHMS AND EMBEDDINGS

The hypercube, though a popular and versatile architecture, has a majo r drawback in that its size must be a power of two. In order to allevi ate this drawback, Katseff [1988] defined the incomplete hypercube, wh ich allows a hypercube-like architecture to be defined for any number of nodes. In this paper we generalize this definition and introduce th e name composite hypercube. The main result of our work shows that the se incomplete architectures can be used effectively and without the si ze penalty. In particular, we show how to efficiently implement Fully Normal Algorithms on composite hypercubes. Development of these types of algorithms on composite hypercubes allows us to efficiently execute several algorithms concurrently on a complete hypercube. We also show that many host architectures, such as binary trees, arrays and butter flies, can be optimally embedded into composite hypercubes. These resu lts imply that algorithms originally designed for any such host can be optimally mapped to composite hypercubes. Finally, we show that compo site hypercubes exhibit many graph theoretic properties that are commo n with complete hypercubes. We also present results on efficient repre sentations of composite hypercubes within a complete hypercube. These results are crucial in task allocation and job scheduling problems.