Performance analysis of parallel I/O models for external mergesort

Files in this item

Files Size Format View
1345353.PDF 3.714Mb application/pdf Thumbnail

Show full item record

Item Metadata

Title: Performance analysis of parallel I/O models for external mergesort
Author: Pai, Vinay Sadananda
Advisor: Varman, Peter J.
Degree: Master of Science thesis
Abstract: 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.
Citation: Pai, Vinay Sadananda. (1991) "Performance analysis of parallel I/O models for external mergesort." Masters Thesis, Rice University.
Date: 1991

This item appears in the following Collection(s)