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)