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 with an n x n base into a hypercube 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. 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 the idea of mixing pyramidal and hypercubic
interconnections, making a hyper-pyramid suitable for cost-effective
image processing.
Keywords:
parallel computer,
hypercube computer, pyramid, parallel algorithm, stepwise simulation,
embeddings, image processing, hyper-pyramid, supercomputer, computer science
