Simulating Essential Pyramids

Russ Miller
Dept. of Computer Science, State University of New York at Buffalo

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

 

Abstract: Pyramid parallel computers, and pyramid algorithms, have long been proposed for image processing. They have the advantages of a regular structure with a square base naturally indentified with an image, and a logarithmic communication diameter to speed processing. Unfortunately, when the image contains multiple objectss of interest it is often difficult to use the pyramid efficiently since the most straightforward algorithms try to use the apex simultaneously for each object, creating a serial bottleneck. Further, algorithms which take this into account and optimize the total time are often rather complicated, limiting the appeal of the pyramid architecture.

This papers shows that one can simulate the effect of having a separate ``essential'' pyramid over each object, simplifying algorithm development since the algorithm can be designed as if there is only a single object in the image. This approach can yield optimal or near-optimal algorithms for the pyramid, and can be used on architectures such as the hypercube, mesh-of-trees, mesh, reconfigurable mesh, and PRAM. For several of these architectures, the simulated essential pyramids can all complete their algorithm nearly as fast as a pyramid computer with a single object.

Keywords: parallel computer, image processing, simulation, vision architectures, pyramid computer

Complete paper. This appeared in IEEE Transactions on Computers 37 (1988) pp. 1642-1648. It was digitized by IEEE.

 

Related Work in Parallel Computing


Quentin F. Stout Home Copyright © 2004-2017 Quentin F. Stout