Pyramid Computer Parallel Algorithms for Image Processing: a survey

Pyramid Algorithms Optimal for the Worst Case

Abstract: This survey paper gives several image-related algorithms for the pyramid computer which are proven to be optimal for the worst case. The times of these algorithms vary widely, showing the sensitivity of the pyramid to the amount of communication which is required. Lower bound arguments are used to show the time required to perform various information movement operations on the pyramid computer, and the worst case communication requirements of a variety of image-related problems are studied. Using these analyses, optimal algorithms are developed which achieve these lower bounds. Modifications of the pyramid are considered which are somewhat less sensitive to the information flow, and these have better worst case performance for many image-related problems without paying the cost penalty inherent in trying to achieve rapid performance on general problems such as sorting.

Keywords: parallel computer, parallel algorithm, mesh local, perimeter bound, strongly global, image processing, communication lower bounds, component labeling, data squares, data movement operations, data square pyramid computer, parallel computing, computational geometry, computer science

This paper appears in Parallel Computer Vision, L. Uhr, ed., Academic Press, 1987, pp. 147-168.

My related work in parallel computing

My papers in parallel computing and an overview of my research.
An explanation of parallel computing, a tutorial, Parallel Computing 101, and a list of parallel computing resources.
Our book, R Miller and QF Stout, Parallel Algorithms for Regular Architectures: Meshes and Pyramids, MIT Press, 1996, contains many algorithms for pyramid computers.