Name
Abstract | ||
|---|---|---|
An optimal prefetching and I/O scheduling algorithm L-OPT, for parallel I/O systems, using a read-once model of block references is presented. The algorithm uses knowledge of the next $L$ references, $L$-block lookahead, to create a minimal-length I/O schedule. For a system with $D$ disks and a buffer of capacity $m$ blocks, we show that the competitive ratio of L-OPT is $\Theta(\sqrt{mD/L})$ when $L \geq m$, which matches the lower bound of any prefetching algorithm with $L$-block lookahead. Tight bounds for the remaining ranges of lookahead are also presented. In addition we show that L-OPT is the optimal offline algorithm: when the lookahead consists of the entire reference string, it performs the absolute minimum possible number of I/Os. Finally, we show that L-OPT is comparable with the best online algorithm with the same amount of lookahead; the ratio of the length of its schedule to the length of the optimal schedule is always within a constant factor. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/s00453-004-1129-7 | Algorithmica |
Keywords | Field | DocType |
optimal read-once parallel disk,o schedule,scheduling.,o scheduling algorithm,optimal prefetching,o system,prefetching algorithm,online algorithm,optimal schedule,prefetching,external memory algorithms,block lookahead,parallel i/o,block reference,caching,optimal offline algorithm,lower bound,scheduling algorithm,disk scheduling,competitive ratio | Online algorithm,I/O scheduling,Fair-share scheduling,Scheduling (computing),Computer science,Upper and lower bounds,Parallel computing,Real-time computing,Out-of-core algorithm,Parallel I/O,Competitive analysis,Distributed computing | Journal |
Volume | Issue | ISSN |
43 | 4 | 1432-0541 |
Citations | PageRank | References |
21 | 1.04 | 28 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mahesh Kallahalla | 1 | 539 | 34.54 |
| Peter J. Varman | 2 | 700 | 83.23 |