Tech Report CS-90-21

Algorithms for Parallel Memory I: Two-Level Memories

Jeffrey Scott Vitter and Elizabeth A. M. Shriver

September 1990


We provide the first optimal algorithms in terms of the number of input/outputs (I/Os) required between internal memory and multiple disk drives 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 {\em parallel block transfer,} in which during a single I/O each of P disks can simultaneously transfer a contiguous block of B records. It pertains to a large-scale uniprocessor systems with P disks, as well as to a parallel computer of P processors with one disk attached to each processor. The difficulty in developing optimal algorithms is to cope with the partitioning of memory into P separate physical devices. Our optimal sorting algorithm is randomized, but practical: the probability of using more than an optimal number of I/Os falls off exponentially.

(complete text in pdf)