In Proc. 2nd Symp. Frontiers of Massively Parallel Computation
(1988), pp. 195-198.
Portable Parallel Algorithms for Geometric Problems
Because the interconnection scheme among processors (or between processors
and memory) significantly affects the running time, efficient parallel
algorithms must take the interconnection scheme into account.
This in turn entails tradeoffs between efficiency and portability among
Our goal is to develop algorithms that are portable among
massively parallel fine grain
architectures such as hypercubes, meshes, and pyramids, while yielding
a fairly efficient implementation on each.
Our approach is to utilize standardized operations such as prefix, broadcast,
sort, compression, and crossproduct calculations.
This paper describes an approach for designing efficient, portable
algorithms and gives sample algorithms to solve some
fundamental geometric problems.
The difficulties of portability and efficiency for these geometric problems
have been redirected into similar difficulties for the standardized operations.
However, the cost of developing efficient implementations of them on the
various target architectures can be amortized over numerous algorithms.
Dept. of Computer Science, State University of New York at Buffalo
Quentin F. Stout
EECS Department, University of Michigan
Keywords: portable parallel algorithms, computational geometry,
data movement operations, distributed memory parallel computers, message
passing, supercomputing, computer science
Full paper (Postscript)
Full paper (PDF)
Other papers in parallel computing
Overview of work on parallel computing
Copyright © 2005-2016 Quentin F. Stout