Tech Report CS-92-02

Large-Scale Sorting in Uniform Memory Hierarchies

Jeffrey Scott Vitter and Mark H. Nodine

January 1992


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)