In SIAM J. on Computing 16 (1987), pp. 38-60.

Data Movement Techniques for the Pyramid Computer

Russ Miller
Dept of Comp Sci & Eng, State University of New York at Buffalo

Quentin F. Stout
EECS Department, University of Michigan

Abstract: The pyramid computer was initially proposed for performing high-speed low-level image processing. However, its regular geometry can be adapted quite naturally to many other problems, providing effective solutions to problems more complex than those previously considered. We illustrate this by presenting pyramid computer solutions to problems involving component labeling, minimal spanning forests, nearest neighbors, transitive closure, articulation points, bridge edges, etc. Central to these algorithms is our collection of data movement techniques which exploit the pyramid's mix of tree and mesh connections. Our pyramid algorithms are significantly faster than their mesh-connected computer counterparts. For example, given a black/white square picture with n pixels, the pyramid can label the connected components in Theta(n1/4) time, as compared with the Omega(n1/2) time required on the mesh.

Keywords: parallel computer, pyramid computer, graph algorithms, computational geometry, image processing, component labeling, mesh computer, data movement operations, parallel algorithms, computer science

Much of the content of this paper has been incorporated into the book Parallel Algorithms for Regular Architectures: Meshes and Pyramids, by R. Miller and Q.F. Stout. More information about the book is available.

Russ Miller (