ATTENTION: The software behind KU ScholarWorks is being upgraded to a new version. Starting July 15th, users will not be able to log in to the system, add items, nor make any changes until the new version is in place at the end of July. Searching for articles and opening files will continue to work while the system is being updated.
If you have any questions, please contact Marianne Reed at mreed@ku.edu .
Competitive Parallel Disk Prefetching and Buffer Management
dc.contributor.author | Barve, Rakesh | |
dc.contributor.author | Kallahalla, Mahesh | |
dc.contributor.author | Varman, Peter J. | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.date.accessioned | 2011-03-21T18:26:24Z | |
dc.date.available | 2011-03-21T18:26:24Z | |
dc.date.issued | 2000 | |
dc.identifier.citation | R. D. Barve, M. Kallahalla, P. Varman, and J. S. Vitter. “Competitive Analysis of Buffer Management Algorithms for Parallel I/O Systems,” Journal of Algorithms, 36(2), August 2000, 152–181. An extended abstract appears in Proceedings of the ACM-IEEE Workshop on I/O in Parallel And Distributed Systems (IOPADS ’97), San Jose, CA, November 1997, 47–56. http://dx.doi.org/10.1006/jagm.2000.1089 | |
dc.identifier.uri | http://hdl.handle.net/1808/7208 | |
dc.description.abstract | We provide a competitive analysis framework for online prefetching and buffer management algorithms in parallel I/O systems, using a read-once model of block references. This has widespread applicability to key I/O-bound applications such as external merging and concurrent playback of multiple video streams. Two realistic lookahead models, global lookahead and local lookahead, are defined. Algorithms NOM and GREED based on these two forms of lookahead are analyzed for shared buffer and distributed buffer configurations, both of which occur frequently in existing systems. An important aspect of our work is that we show how to implement both the models of lookahead in practice using the simple techniques of forecasting and flushing. Given a -disk parallel I/O system and a globally shared I/O buffer that can hold upto disk blocks, we derive a lower bound of on the competitive ratio of any deterministic online prefetching algorithm with lookahead. NOM is shown to match the lower bound using global -block lookahead. In contrast, using only local lookahead results in an competitive ratio. When the buffer is distributed into portions of blocks each, the algorithm GREED based on local lookahead is shown to be optimal, and NOM is within a constant factor of optimal. Thus we provide a theoretical basis for the intuition that global lookahead is more valuable for prefetching in the case of a shared buffer configuration whereas it is enough to provide local lookahead in case of the distributed configuration. Finally, we analyze the performance of these algorithms for reference strings generated by a uniformly-random stochastic process and we show that they achieve the minimal expected number of I/Os. These results also give bounds on the worst-case expected performance of algorithms which employ randomization in the data layout. | |
dc.language.iso | en_US | |
dc.publisher | Elsevier | |
dc.title | Competitive Parallel Disk Prefetching and Buffer Management | |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffery Scott | |
kusw.oastatus | fullparticipation | |
dc.identifier.doi | 10.1006/jagm.2000.1089 | |
kusw.oaversion | Scholarly/refereed, author accepted manuscript | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess |