# Implementations of Parallel Algorithms

Here I'm interested in getting demonstrably good performance from highly
parallel computers on key problems. Most of this work was carried out on
MasPar MP-1 and MP-2 computers, but the techniques apply to other
architectures as well. Here are some references, and, in some cases,
access to publications in postscript form and program sources.

## Sorting

- W. Hightower, J. Prins, J. Reif, "Implementations of Randomized Sorting
on Large Parallel Machines",
* Proc. 3rd Symposium on Parallel
Architectures and Algorithms*, ACM, 1992.
Postscript (258K).
- J. Prins, "B-Flashsort: A High-performance parallel sort for the MasPar
MP-1 and MP-2", UNC Dept. of Computer Science TR92-091, 1992.
PostScript (113K) and
distribution (44K) (shar file).
- J. Prins "Efficient Bitonic Sorting of Large Arrays on the MasPar MP-1",
UNC Dept. of Computer Science TR91-041, 1991.
PostScript (119K) and
distribution (17K) (shar file).
- J. Prins, J. Smith, "Parallel Sorting of Large Arrays on the MasPar MP-1",
* Proc. of the 3rd Symposium on the Frontiers of Massively Parallel
Processing*, IEEE, 1990.

## Connected Components

- S. Goddard, S. Kumar, J. Prins, "Connected Components Algorithms for
Mesh-Connected Parallel Computers", DIMACS implementation challenge workshop,
Fall 1994.

## Rendering

- A. Varshney, J. Prins, "An Environment-Projection Approach to Radiosity
for Mesh-Connected Computers", in
* Third Eurographics Workshop on
Rendering*, A. Chalmers, D. Paddon, F. Sillion (eds),
Alpha Press (U.K.), 1992.

## Interactive Simulations

- M. Parris, C. Mueller, J. Prins, A. Duggan, Q. Zhou, E. Erikson,
"A Distributed Implementation of an N-body Virtual World Simulation",
* Proc. IEEE Workshop on Parallel and Distributed Real-Time Systems*,
IEEE, 1993.

## Load Balancing

- E. Biagioni, J. Prins, "Scan-Directed Load Balancing for
Mesh-Connected Highly-Parallel Computers", in
* Unstructured Scientific Computation on Scalable Multiprocessors*,
P. Mehrotra, J. Saltz, R. Voigt (eds.), MIT Press, 1992.
- J. Prins, "Work-efficient Techniques for the Parallel Execution of
Sparse Grid-based Computations", UNC TR92-042.

## Lattice Gas and Lattice Boltzmann Automata

- J. Butterworth, J. Prins, "A Comparison of Lattice-Gas Automata
Implementations on the MasPar MP-1", in
*Parallel Computational Fluid
Dynamics*, J. Hauser, ed., Elsevier Scientific, 1993.

## Fast Multipole N-body simulations

- L. Nyland, J. Prins, J. Reif, "A Data-Parallel Implementation of the Adaptive Fast Multipole Algorithm", 1993 DAGS/PC Workshop on Practical Parallel Algorithms, Dartmouth University, 1993.

prins@cs.unc.edu