Pyramid Algorithms Optimal for the Worst Case

Quentin F. Stout
University of Michigan


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

Quentin's Home Copyright © 2005-2016 Quentin F. Stout.