CATS Invited Talk: Practical Parallel Algorithms for Personalized Communication and Integer Sorting

Abstract

A fundamental challenge for parallel computing is to obtain high-level, architecture independent, algorithms which execute efficiently on general-purpose parallel machines. With the emergence of message passing standards such as MPI, it has become easier to design efficient and portable parallel algorithms by making use of these communication primitives. While existing primitives allow an assortment of collective communication routines, they do not handle an important communication event when most or all processors have non-uniformly sized personalized messages to exchange with each other. In this talk, we will focus on the h-relation personalized communication whose efficient implementation will allow high performance implementations of a large class of algorithms. While most previous h-relation algorithms use randomization, we present a new deterministic approach for h-relation personalized communication with asymptoticaly optimal complexity for h >= p^2. As an application, we present an efficient algorithm for stable integer sorting. The algorithms presented in this talk have been coded in Split-C and run on a variety of platforms, including the IBM SP-1 and SP-2, Cray Research T3D, Thinking Machines CM-5, Meiko Scientific CS-2, and the Intel Paragon. Our experimental results are consistent with the theoretical analysis and illustrate the scalability and efficiency of our algorithms across different platforms. In fact, they seem to outperform all similar algorithms known to the authors on these platforms. (Joint work with Dr. Joseph Ja’Ja’ and David R. Helman.)

The Capital Area Theory Symposia is an NSF sponsored series of symposia in theoretical computer science bringing computer scientists from around the world to the Capital area. The Symposia are given at the University of Maryland in cooperation with the Computer Science Department and UMIACS. NSF support under grant CCR-9401842 is gratefully acknowledged.

http://www.cs.umd.edu/users/samir/catss96.html

David A. Bader

Distinguished Professor and Director of the Institute for Data Science

David A. Bader is a Distinguished Professor in the Department of Computer Science at New Jersey Institute of Technology.