article · 1998

Parallel-Disk Buffer Management using Randomization

Mahesh Kallahalla, Peter J. Varman

Cited by 0Abstract and details only

Abstract

We present an on-line algorithm for prefetching and caching for a multiple-disk parallel I/O system. We introduce the notion of write-back whereby blocks are relocated between disks during the course of the computation. Write-back allows the layout to be altered dynamically to suit access patterns in different parts of the reference string. The algorithm is analyzed using the standard parallel disk model with D parallel disks and a shared I/O buffer of size M blocks. We show that any on-line algorithm with M-block lookahead using deterministic write-back and buffer management policies must have a competitive ratio of \\Omega\\Gamma D). We therefore present a randomized algorithm, RAND-WB, that uses randomized write-back and attains a competitive ratio of \\Theta( p D), the best achievable by any on-line algorithm with M-block lookahead. Simulations show that RAND-WB obtains considerable performance benefit even when the data has just a small amount of re-use.

Cite this paper

APA 7

Kallahalla, M., & Varman, P. J. (1998). Parallel-Disk Buffer Management using Randomization.

MLA 9

Kallahalla, Mahesh, and Peter J. Varman. “Parallel-Disk Buffer Management using Randomization.” 1998.

Chicago

Kallahalla, Mahesh, and Peter J. Varman. 1998. “Parallel-Disk Buffer Management using Randomization.”

Harvard

Kallahalla, M. and Varman, P.J. (1998) ‘Parallel-Disk Buffer Management using Randomization’.

BibTeX

@article{kallahalla1998parallel,
  title = {{Parallel-Disk Buffer Management using Randomization}},
  author = {Kallahalla, Mahesh and Varman, Peter J.},
  year = {1998}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.