Hypercubes and Pyramids

Quentin F. Stout
Computer Science and Engineering, University of Michigan

 

Abstract: This paper compares hypercube and pyramid parallel computers, and shows that the hypercube has significantly more flexibility. It is well-known that meshes can be efficiently embedded into hypercubes, and here it is shown that pyramids can also be efficiently embedded. An explicit 1-1 embedding of a pyramid graph with an n x n base into a hypercube graph of 2n2 processors is given, where neighbors in the pyramid are at most distance 2 apart in the hypercube (n is a power of 2). This is the smallest possible dilation, and the target hypercube is the smallest one with as many processors as the pyramid (a pyramid with an nxn base has exactly (4n2-1)/3 processors). This embedding permits constant-time stepwise simulation of the pyramid by the hypercube. For hypercubes smaller than this, many-to-one embeddings are given which are optimized for simulating typical pyramidal algorithms.

Brief mention is also made of mixing pyramidal and hypercubic interconnections, making a hyper-pyramid suitable for cost-effective image processing.

Keywords: parallel computer, hypercube computer, pyramid, graph embedding, parallel algorithm, stepwise simulation, image processing, hyper-pyramid

Complete paper. This appears in Pyramidal Systems for Computer Vision, V. Cantoni and S. Levialdi, eds., NATO ASI Series ARW Vol. F 25, Springer-Verlag, 1986, pp. 75-89

 


Related work


Quentin Copyright © 2005-2020 Quentin F. Stout