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 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, graph embedding, parallel algorithm, stepwise simulation, embeddings, image processing, hyper-pyramid
Complete paper. It 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
|
Copyright © 2005-2009 Quentin F. Stout |