-CS-TR-3548, UMIACS-TR-95-101.
-Appeared in the Journal of Experimental Algorithmics.
A fundamental challenge for parallel computing is to obtain
high-level, architecture independent, algorithms which efficiently
execute 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.
We focus in this
paper 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, this paper presents 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 paper have been coded in
Split-C and run on a variety of platforms, including the Thinking
Machines CM-5, IBM SP-1 and SP-2, Cray Research T3D, 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.
HTML
or
PostScript
or
Compressed PostScript
Version of this report.
Release 3.4 of the software
(Send e-mail request
for latest version)
For more infomation on any of the these topics, click on the hotlink.
Any queries, comments, or inquiries to:
David A. Bader (Click here for personal info!)
E-mail: dbader@umiacs.umd.edu
Office phone: (301)405-6755
FAX: (301)314-9658
Return to the Experimental Parallel Algorithmics page.