Abstract: The single-disk, D-head model of parallel I/O was introduced by Agarwal and Vitter to analyze algorithms for problem instances that are too large to fit in primary memory. Subsequently Vitter and Shriver proposed a more realistic model in which the disk space is partitioned into D disks, with a single head per disk. To date, each problem for which there is a known optimal algorithm for both models has the same asymptotic bounds on both models. Therefore, it has been unknown whether the models are equivalent or whether the single-disk model is strictly more powerful.In this paper we provide evidence that the single-disk model is strictly more powerful. We prove a lower bound on any general simulation of the single-disk model on the multi-disk model and establish randomized and deterministic upper bounds. Let N be the problem size and let T be the number of parallel I/Os required by a program on the single-disk model. Then any simulation of this program on the multi-disk model will require Omega(T log(N/D)/log log(N/D) parallel I/Os. This lower bound holds even if replication is allowed in the multi-disk model. We also show an O(log D/log log D) randomized upper bound and an O(log D (log log D)^2) deterministic upper bound. These results exploit an interesting analogy between the disk models and the PRAM and DCM models of parallel computation.
David Kotz -- Last modified: Tue Jul 9 11:32:20 1996