Quentin F. Stout
Computer Science and Engineering, 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. The paper appears in Proceedings of the IEEE 76 (1988), pp. 982-995. It was digitized by IEEE.
Related Work:
|
Copyright © 2005-2017 Quentin F. Stout. |