Performance analysis of parallel I/O models for external mergesort
Pai, Vinay Sadananda
Varman, Peter J.
Master of Science thesis
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.
Engineering, Electronics and Electrical; Computer Science; Mathematics