Sorting on Clusters of SMPs
Sorting on Clusters of SMPs
Loading...
Files
Publication or External Link
Date
1998-10-15
Authors
Helman, David R.
JaJa, Joseph
Advisor
Citation
DRUM DOI
Abstract
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.
(Also cross-reference as UMIACS-TR-97-69