Paper Info
Title
Improving parallel-disk buffer management using randomized writeback
Abstract
We address the problems of I/O scheduling and buffer management for general reference strings in a parallel I/O system. Using the standard parallel disk model with D disks and a shared I/O buffer of size M, we study the performance of online algorithms that use bounded global M-block lookahead. We introduce the concept of write-back whereby blocks are dynamically relocated between disks during the course of the computation. Write-back allows the layout to be altered to suit different access patterns in different parts of the reference string. We show that any bounded-lookahead online algorithm that uses purely deterministic policies must have a competitive ratio of Ω (D). We show how to improve the performance by using randomization, and present a novel algorithm, RAND-WB, using a randomized write-back scheme. RAND-WB has a competitive ratio of θ(√D), which is the best achievable by any online algorithm with only global M-block lookahead. If the initial layout of data on the disks is uniformly random, RAND-WB has a competitive ratio of θ(log D)
Year
DOI
Venue
1998
10.1109/ICPP.1998.708495
Minneapolis, MN
Keywords
Field
DocType
buffer storage,magnetic disc storage,parallel algorithms,processor scheduling,random processes,storage management,D disks,I/O scheduling,RAND-WB,access patterns,bounded global M-block lookahead,bounded-lookahead online algorithm,buffer management,competitive ratio,general reference strings,global M-block lookahead,initial layout,online algorithm,online algorithms,parallel I/O system,parallel disk buffer management,purely deterministic policies,randomization,randomized write-back scheme,randomized writeback,reference string,shared I/O buffer,standard parallel disk model
Online algorithm,Disk buffer,I/O scheduling,Scheduling (computing),Computer science,Parallel algorithm,Parallel computing,Stochastic process,Distributed computing,Computation,Competitive analysis
Conference
ISSN
ISBN
Citations 
0190-3918
0-8186-8650-2
13
PageRank 
References 
Authors
0.61
17
2
Name
Order
Citations
PageRank
Mahesh Kallahalla153934.54
Varman, P.J.215249.42