Competitive prefetching and buffer management for parallel I/O systems

In this thesis we study prefetching and buffer management algorithms for parallel I/O systems. Two models of lookahead, global and local, which give limited information regarding future accesses are introduced. Two configurations of the I/O buffer, shared and distributed, are considered, based upon the accessibility of the I/O buffer. The performance of prefetching algorithms using the two forms of lookahead is analyzed in the framework of competitive analysis, for read-once access patterns. Two algorithms, PHASE and GREED, which match the lower bounds are presented. A randomized version of GREED that performs the minimal expected number of I/Os is designed and applied to the problems of external sorting and video retrieval. Finally the problem of designing prefetching and buffer management algorithms for read-many reference strings is examined. An algorithm which uses randomized write-back to attain good expected I/O performance is presented.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Engineering

Grantor

Rice University

Year dc:date.issued

1997

Author dc:creator

• Kallahalla, Mahesh

Advisor dc:contributor.advisor

• Varman, Peter J.

• Electronics
• Electrical engineering
• Computer science

Statement dc:rights

• Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder.

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1911/17099

OAI identifier oai:identifier

oai:repository.rice.edu:1911/17099