{"id":{"repo_id":"rice","oai_identifier":"oai:repository.rice.edu:1911/17099"},"canonical_url":"https://search.dev.ndltd.org/etd/rice/oai:repository.rice.edu:1911/17099","repository":{"repo_id":"rice","name":"Rice University","base_url":"https://repository.rice.edu/server/oai/request"},"display":{"title":"Competitive prefetching and buffer management for parallel I/O systems","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Kallahalla, Mahesh"],"institution":"Rice University","degree_name":"Master of Science","degree_level":"Masters","degree_discipline":"Engineering","degree_department":null,"school":null,"contributors":[],"advisors":["Varman, Peter J."],"committee_chairs":[],"committee_members":[],"year":1997,"date_issued":"1997","date_published":"1997","updated_at":"2026-07-24T04:10:22Z","subjects":["Electronics","Electrical engineering","Computer science"],"languages":["eng"],"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."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1911/17099","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Varman, Peter J."]},{"key":"dc:creator","label":"Author","values":["Kallahalla, Mahesh"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2009-06-04T07:03:53Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2009-06-04T07:03:53Z"]},{"key":"dc:date.issued","label":"Date","values":["1997"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Rice University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electronics","Electrical engineering","Computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1911/17099"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Competitive prefetching and buffer management for parallel I/O systems"]}]}],"canonical_facts":{"dc:contributor.advisor":["Varman, Peter J."],"dc:creator":["Kallahalla, Mahesh"],"dc:date.accessioned":["2009-06-04T07:03:53Z"],"dc:date.available":["2009-06-04T07:03:53Z"],"dc:date.issued":["1997"],"dc:description.abstract":["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."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["https://hdl.handle.net/1911/17099"],"dc:language.iso":["eng"],"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."],"dc:subject":["Electronics","Electrical engineering","Computer science"],"dc:title":["Competitive prefetching and buffer management for parallel I/O systems"],"dc:type":["Thesis"],"thesis:degree_discipline":["Engineering"],"thesis:degree_level":["Masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Rice University"]},"updated_at":"2026-07-24T04:10:22Z"}