Parallel sorting on cache-coherent DSM multiprocessors
Hongzhang Shan, Jaswinder Pal Singh · 1999
The performance of parallel sorting is not well understood on hardware cachecoherent shared address space (CC-SAS) multiprocessors, which increasingly dominate the market for tightly-coupled multiprocessing.We study two high-performance parallel sorting algorithms, radix and sample sorting, under three major programming models-a load-store CC-SAS, message passing, and the segmented SHMEM model-on a 64-processor SGI Origin2000.We observe surprisingly good speedups on this demanding application.The performance of radix sort is greatly affected by the programming model and particular implementation used.Sample sort exhibits more uniform performance across programming models on this platform, but it is usually not so good as that of the best radix sort for larger data sets if each is allowed to use the best programming model for itself.The best combination of algorithm and programming model is radix sorting under the SHMEM model for larger data sets and sample sorting under CC-SAS for smaller data sets.Recently, a new type of platform has begun to dominate tightly-coupled multiprocessing, and together with less tightly-coupled commodity clusters constitutes the stateof-the-art going forward in multiprocessing.This type of platform supports a shared address space with implicit coherent replication of data in hardware, even though memory is physically distributed.It is very different from the traditional message-passing 1