Abstract: Divide-and-conquer is an important algorithm strategy, but it is not widely used in image processing. For higher-level, symbolic operations it should often be the strategy of choice on parallel computers. It is natural for a distributed memory machine with a regular interconnection scheme such as a mesh, mesh with broadcasting, pyramid, mesh-of-trees, or hypercube, or for shared memory machines (such as the PRAM model). It can be used either on a fine-grain machine with a pixel per processor or on a medium-grain machine many pixels per processor. However, divide-and-conquer algorithms use parallel computers in a different manner than, say, local edge detection, so machines optimized for local neighborhood algorithms may be poor for divide-and-conquer algorithms. Some characteristics of divide-and-conquer algorithms are examined, along with some of their implications for the design of machines and languages which can support the efficient programming and execution of divide-and-conquer algorithms.

Keywords: regular parallel architectures, parallel algorithms, languages, bandwidth limitations, distributed memory, hypercube, mesh, pyramid, PRAM, shared memory, fine-grain, medium-grain, parallel programming paradigms, parallel computing

Complete paper. This paper appears in the Journal of Parallel and Distributed Computing 4 (1987), pp. 95-115.

Related work in parallel computing

• My papers in parallel computing and an overview of my research.
• An explanation of parallel computing and a tutorial, Parallel Computing 101.

Copyright © 2005-2018 Quentin F. Stout.