The ACM 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 asymptotically optimal complexity for $h>p2$. 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.

• Keywords: Parallel Algorithms, Personalized Communication, Integer Sorting, Radix Sort, Communication Primitives, Routing h-Relations, Parallel Performance.
• CR Categories:
• Sources:
  Note: The version currently on the server is the final revision provided by the authors; it is not the definitive version, which awaits editing from ACM personnel. In consequence, it will be replaced by that definitive version when the editing is complete.
  • The LaTeX version of the article; this is a Unix tar file that contains the LaTeX source, several EPS figures, and a style sheet; the LaTeX source alone is available here;
    note that you must be a subscriber (institutional or individual) to access these files.
  • The Postscript version or PDF version of the article;
    note that you must be a subscriber (institutional or individual) to access these files.
  • The HTML version of the article;
    note that you must be a subscriber (institutional or individual) to access this file.
  • The bibliography given in the article.
  • The software suite accompanying the article; this is a large (3.3Megs) Unix tar file.

Last updated and validated September 4, 1996, by editor@jea.acm.org