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 (miller@cse.buffalo.edu)