Mapping Vision Algorithms to Parallel Architectures

Mapping Vision Algorithms to Parallel Architectures

Quentin F. Stout
EECS Department, University of Michigan

Abstract: Because parallel architectures can vary widely, the problem of mapping a given parallel algorithm onto a given parallel machine is generally much harder than the problem of mapping a serial algorithm onto a serial machine. This paper examines some of the problems encountered, emphasizing mappings of vision algorithms onto mesh, hypercube, mesh-of-trees, pyramid, and parallel random access machines (PRAMs) having many simple processors, each with a small amount of memory, i.e., fine-grained SIMD machines.

Approaches that have been suggested include simulating one architecture by another, designing ideal algorithms for ideal architectures and simulating the ideal architecture, and using general data movement operations. Each of these is shown to occasionally produce unacceptably inefficient implementations. It appears that as long as PRAMs (also known as shared memory machines) cannot achieve the desired cost and performance goals, programmers must contend with carefully designed algorithms for specific architectures.

Keywords: parallel computing, simulation, optimal parallel algorithms, mesh, pyramid, hypercube, mesh-of-trees, PRAM, shared memory, lower bounds, data movement operations, computational geometry, image processing, graph algorithms, parallel computing, computer science

Complete paper. It appears in Proc. of the IEEE 76 (1988), pp. 982-995. IEEE digitized the paper.

Other papers in parallel computing
Overview of work on parallel computing