Portable Parallel Algorithms

In Proc. 2nd Symp. Frontiers of Massively Parallel Computation (1988), pp. 195-198.

Portable Parallel Algorithms for Geometric Problems
Preliminary version

Russ Miller
Dept. of Computer Science, State University of New York at Buffalo

Quentin F. Stout
EECS Department, University of Michigan

Abstract: 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 different architectures. 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.

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