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.