Performance analysis of parallel I/O models for external mergesort
V S Pai · Rice Research Repository (Rice University) · 1991
Since the I/O subsystem is the bottleneck in external mergesort, I/O parallelism can result in substantial performance improvements. Concurrency can be introduced by overlapping I/O requests at different disks, and the average service time can be reduced by reading several blocks on each I/O operation. However, a RAM-based cache is required to support this prefetching. A prefetching strategy is proposed in which one block from each run is read on every I/O operation, and a Markov model is developed to analyze the dynamic behavior of the system. The steady-state probabilities and a closed-form expression for the average parallelism are derived as functions of the cache size and the number of runs. Several related prefetching strategies are also investigated for both single-disk and multiple-disk cases. For each strategy, the total execution time and the cache behavior are studied by simulating the merge and deriving analytic expressions for the average service time.