Name
Abstract | ||
|---|---|---|
Buffer management for a D-disk parallel I/O system is considered in the context of randomized placement of data on the disks. A simple prefetching and caching algorithm PHASE-LRU using bounded lookahead is described and analyzed. It is shown that PHASE-LRU performs an expected number of I/Os that is within a factor Θ(log D /log log D) of the number performed by an optimal off-line algorithm. In contrast, any deterministic buffer management algorithm with the same amount of lookahead must do at least Ω (√D) times the number of I/Os of the optimal. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.ipl.2004.01.009 | Inf. Process. Lett. |
Keywords | Field | DocType |
d-disk parallel,competitive ratio,expected number,optimal off-line algorithm,randomization,o system,algorithm phase-lru,prefetching,deterministic buffer management algorithm,buffer management,randomized placement,analysis of algorithms,log log d,bounded lookahead,parallel i/o,caching,simple randomized buffer management | Log-log plot,Discrete mathematics,Analysis of algorithms,Algorithm,Information storage,Input/output,Expected value,Parallel I/O,Mathematics,Competitive analysis,Bounded function | Journal |
Volume | Issue | ISSN |
90 | 1 | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mahesh Kallahalla | 1 | 539 | 34.54 |
| Peter J. Varman | 2 | 700 | 83.23 |