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)