Name
Abstract | ||
|---|---|---|
We address the problem of I/O scheduling of read-once reference strings in a multiple-disk parallel I/O system. We present a novel online algorithm, Red-Black Prefetching (RBP), for parallel I/O scheduling. In order to perform accurate prefetching; RBP uses L-block lookahead. The performance of RBP is analyzed in the standard parallel disk model with D independent disks and a shared I/O buffer of size M. We show that the number of parallel I/Os performed by RBP is within a factot Theta(max{root MD/L, D-1/3}) of the number of I/Os done by the optimal offline algorithm. This ratio is within a canstant factor of the best possible when L is L = O(MD1/3). |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/b71635 | FSTTCS |
Keywords | Field | DocType |
disk scheduling | Approximation algorithm,Algorithm complexity,I/O scheduling,Scheduling (computing),Computer science,Parallel computing,Processor scheduling,Competitive analysis | Conference |
Volume | ISSN | ISBN |
1530 | 0302-9743 | 3-540-65384-8 |
Citations | PageRank | References |
3 | 0.41 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mahesh Kallahalla | 1 | 539 | 34.54 |
| Peter J. Varman | 2 | 700 | 83.23 |