Paper Info
Title
PC-OPT: optimal offline prefetching and caching for parallel I/O systems
Abstract
We address the problem of prefetching and caching in a parallel I/O system and present a new algorithm for parallel disk scheduling. Traditional buffer management algorithms that minimize the number of block misses are substantially suboptimal in a parallel I/O system where multiple I/Os can proceed simultaneously. We show that in the off line case, where a priori knowledge of all the requests is available, PC-OPT performs the minimum number of I/Os to service the given I/O requests. This is the first parallel I/O scheduling algorithm that is provably offline optimal in the parallel disk model. In the online case, we study the context of global L-block lookahead, which gives the buffer management algorithm a lookahead consisting of L distinct requests. We show that the competitive ratio of PC-OPT, with global L-block lookahead, is Θ(M - L + D), when L ≤ M, and Θ(MD/L), when L > M, where the number of disks is D and buffer size is M.
Year
DOI
Venue
2002
10.1109/TC.2002.1047757
Computers, IEEE Transactions
Keywords
Field
DocType
cache storage,input-output programs,parallel algorithms,processor scheduling,PC-OPT,buffer management algorithms,competitive ratio,global L-block lookahead,optimal offline caching,optimal offline prefetching,parallel I/O system,parallel disk model,parallel disk scheduling,requests
Online algorithm,Algorithm design,I/O scheduling,Computer science,Parallel algorithm,Parallel computing,Input/output,Real-time computing,Greedy algorithm,Parallel I/O,Competitive analysis
Journal
Volume
Issue
ISSN
51
11
0018-9340
Citations 
PageRank 
References 
18
0.69
22
Authors
2
Name
Order
Citations
PageRank
Mahesh Kallahalla153934.54
Varman, P.J.215249.42