Tech Report CS-92-04

Algorithms for Parallel Memory I: Two-Level Memories

Jeffrey Scott Vitter and Elizabeth A.M. Shriver

August 1992

Abstract:

We provide the first optimal algorithms in terms of the number of input/outputs (I/Os) required between internal memory and multiple secondary storage devices for the problems of sorting, FFT, matrix transposition, standard matrix multiplication, and related problems. Our two-level memory model is new and gives a realistic treatment of parallel block transfer, in which during a single I/O each of the P secondary storage devices can simultaneously transfer a contiguous block of B records. The model pertains to a large-scale uniprocessor system or parallel multiprocessor system with P disks. In addition, the sorting, FFT, permutation network, and standard matrix multiplication algorithms are typically optimal in terms of the amount of internal processing time. The difficulty in developing optimal algorithms is to cope with the partitioning of memory into P separate physical devices. Our algorithms' performance can be significantly better than those obtained by the well-known but nonoptimal technique of disk striping. Our optimal sorting algorithm is randomized, but practical; the probability of using more than $l$ times the optimal number of I/Os is exponentially small in $l$ $(\log l) \log (M/B)$, where $M$ is the internal memory size.

(complete text in pdf or gzipped postscript)