Practical Parallel Algorithms for Personalized Communication and Integer Sorting

dc.contributor.authorBader, David A.en_US
dc.contributor.authorHelman, David R.en_US
dc.contributor.authorJaJa, Josephen_US
dc.date.accessioned2004-05-31T22:35:18Z
dc.date.available2004-05-31T22:35:18Z
dc.date.created1995-11en_US
dc.date.issued1998-10-15en_US
dc.description.abstractA 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. 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. (Also cross-referenced as UMIACS-TR-95-101.)en_US
dc.format.extent1425732 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/767
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3548en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-95-101.en_US
dc.titlePractical Parallel Algorithms for Personalized Communication and Integer Sortingen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CS-TR-3548.ps
Size:
1.36 MB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
CS-TR-3548.pdf
Size:
496.52 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-3548.ps