|
Title:
|
Performance analysis of parallel I/O models for external mergesort |
|
Author:
|
Pai, Vinay Sadananda |
|
Advisor:
|
Varman, Peter J. |
|
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. "Performance analysis of parallel I/O models for external mergesort." Masters Thesis, Rice University, ETD http://hdl.handle.net/1911/13563. |
|
Citable link to this page:
|
http://hdl.handle.net/1911/13563 |
|
Date:
|
1991 |
