Tech Report CS-92-02
Large-Scale Sorting in Uniform Memory Hierarchies
Jeffrey Scott Vitter and Mark H. Nodine
January 1992
Abstract:
We present several efficient algorithms for sorting on the uniform memory hierarchy (UMH), introduced by Alpern, Carter, and Fei, and its parallelization P-UMH. We give optimal and nearly-optimal algorithms for a wide range of bandwidth degradations, including a parsimonious algorithm for constant bandwidth. We also develop optimal sorting algorithms for all bandwidths for other versions of UMH and P-UMH, including natural restrictions we introduce called RUMH and P-RUMH, which more closely correspond to current programming languages.
(complete text in pdf or gzipped postscript)