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.)