Tech Report CS-92-48

Minimizing the Input/Output Bottleneck

Mark Howard Nodine

October 1992

Abstract:

In this thesis, we examine ways of ameliorating the input/output (I/O) bottleneck through developing special-purpose algorithms tailored to specific I/O environments. We give provably optimal deterministic algorithms for sorting on parallel disks and in parallel memory hierarchies. The memory hierarchies considered are the Hierarchical Memory Model (HMM), the Block Transfer model (BT), and the Uniform Memory Hierarchy (UMH). We give an algorithm for sorting that is simultaneously optimal in terms of I/Os and internal processing time in a model where we have $D$ disks and $P$ processors, as long as $P$ does not exceed $M \log \min \{M/B,\log M\}/\log M$. We give the first known algorithms for sorting efficiently in single Uniform Memory Hierarchies.

We show how to achieved optimal I/O performance of VLSI implementations of lattice computations by transferring less information, and give matching upper and lower bounds. Finally, we show how to use blocking efficiently for external graph searching.

(complete text in pdf or gzipped postscript)