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 2n² 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 (4n²-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

• A paper on general graph embeddings in hypercubes.
• My work in parallel computing: papers, and an overview of research
• General parallel computing: an explanation of parallel computing, a tutorial, Parallel Computing 101, and a list of parallel computing resources

Copyright © 2005-2020 Quentin F. Stout