Supporting divide-and-conquer algorithms for image processing

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 for parallel computers. It is natural for a machine with a regular interconnection scheme such as a mesh, mesh with broadcasting, tree, pyramid, mesh-of-trees, PRAM, or hypercube, and can be used either on a machine with a pixel per processor or on one with 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.