Simple randomized mergesort on parallel disks
Rakesh D. Barve, Edward F. Grove, Jeffrey Scott Vitter · 1996
We consider the problem of sorting a file of N records on the D-disk model of parallel I/0 [VS94] in which there are two sources of parallehsm. Records are transferred to and from disk concurrently in blocks of B con-tiguous records. In each I/O operation, up to one block can be transferred to or from each of the D disks in parallel. We propose a simple, eficient, randomized mergesort algorithm called SRM that uses a forecast-and-flush approach to overcome the inherent difficulties of simple merging on parallel disks. SRM exhibits a limited use of randomization and also has a useful deterministic version. Generalizing the forecasting technique of [Knu73], our algorithm, is able to read in, at any time, the right block from any disk, and using the technique of flushing, our algorithm evicts, without any I/0 overhead, just the right blocks from memory to make space for new ones to be read in. The disk layout of SRM is such that it enjoys perfect write parallelism, avoiding fundamental inefficiencies of previous mergesort algorithms. Our analysis technique involves a novel reduction to various maximum occupancy problems. We prove that the expected I/O performance of SRM is efficient under varying sizes of memory and that it compares favorably in practice to disk-striped mergesort (DSM). Our studies indicate that SRM outperforms DSM even when the number D of parallel disks is fairly small.