-CS-TR-3833, UMIACS-TR-97-69.

-To be presented at the 12th International Parallel Processing Symposium.

Sorting on Clusters of SMPs

Clusters of symmetric multiprocessors (SMPs) have emerged as the primary candidates for large scale multiprocessor systems. In this paper, we introduce an efficient sorting algorithm for clusters of SMPs. This algorithm relies on a novel scheme for stably sorting on a single SMP coupled with balanced regular communication on the cluster. Our SMP algorithm seems to be asymptotically faster than any of the published algorithms we are aware of. The algorithms were implemented in C using Posix Threads and the SIMPLE library of communication primitives and run on a cluster of DEC AlphaServer 2100A systems. Our experimental results verify the scalability and efficiency of our proposed solution and illustrate the importance of considering both memory hierarchy and the overhead of shifting to multiple nodes.

PostScript or Compressed PostScript Version of this report.

University of Maryland

Department of Computer Science and Department of Electrical Engineering, and

The University of Maryland Institute for Advanced Computer Studies

For more infomation on any of the these topics, click on the hotlink.
Any queries, comments, or inquiries to: 
   David R. Helman
   E-mail: helman@umiacs.umd.edu
   Office phone: (301)405-6757 
   FAX: (301)314-9658

Return to the Experimental Parallel Algorithmics page.