Tech Report CS-92-38

Optimal Deterministic Sorting in Parallel Memory Hierarchies

Mark H. Nodine and Jeffrey Scott Vitter

August 1992


We present a general deterministic sorting strategy that is applicable to a wide variety of parallel memory hierarchies with parallel processors. The simplest incarnation of the strategy is an optimal deterministic algorithm called Balance Sort for external sorting on multiple disks with a single CPU. Balance Sort was the topic of a previous technical report. This technical report shows how to adapt Balance Sort to sort deterministically in parallel memory hierarchies. The algorithms so derived will be optimal for all parallel memory hierarchies for which an optimal algorithm is known for a single hierarchy. In the case of $D$ disks, $P$ processors, block size $B$, and internal memory size $M$, they are optimal in terms of I/Os for any $P \leq M$ and $DB < M$, and in terms of internal processing time except when $P> M \log \min\{M/B, \log M\}/\log M$ and $\log M/B = o(\log M)$.

(complete text in pdf or gzipped postscript)