Abstract: We develop some fundamental algorithms for pyramid computers of arbitrary dimension, mesh connected computers, and x-trees. (An x-tree is a 1-dimensional pyramid computer.) We give optimal Θ(n/log n) algorithms for sorting and merging n items stored in an x-tree, and show that for higher dimensional pyramids well-known mesh algorithms, using only the base processors, are optimal. We give a selection algorithm which utilizes only the tree connections of the pyramid (of any dimension) which runs in less than n^c for any c > 0. The problem of finding an optimal selection algorithm on a computer arranged as a complete k-ary tree, k ≥ 2, is apparently still an open problem. In particular, is Θ(log n) possible?

We also give an optimal algorithm for median filtering of an image. For a D x D window on an image of arbitrary size stored one pixel per processor in a mesh-connected computer, the algorithm takes Θ(D) time. This improves upon previously published algorithms, including ones published for a pyramid computer. Note that the base of a pyramid computer is a mesh-connected computer, and an interesting aspect is that the processors above the base do not aid in median filtering, in that median filtering on a pyramid computer must take Ω(D) time.

Keywords: message passing parallel computer, pyramid computer, x-tree, tree computer, sorting, merging, selection, median filtering, image processing, parallel algorithm

Complete paper.   This paper appears in Proc. 1983 International Conference on Parallel Processing, IEEE, pp. 214-221. It's a preliminary version, but I never wrote a more polished version.

Related work:
A modest explanation of parallel computing, a tutorial, Parallel Computing 101, and a list of parallel computing resources.
An overview of our work, and relevant papers.

Copyright © 2004-2018 Quentin F. Stout.