We provide a competitive analysis framework for online ptefetching and buffer management algorithms in parallel I/O systems, using a read-once model of block references. This has widespread applicability to key I/O-bound applications such as external merging and concurrent playback of multiple video streams. Two realistic lookahead models, global lookahead and local lookahead, am defined. Algorithms NOM and GREED based on these two forms of lookahead are analyzed for shared buffer and distributed buffer configurations, both of which occur frequently in existing systems. An important aspect of our work is that we show how to implement both the models of lookahead in practice using the simple techniques of forecasting and flushing. The increasing imbalance between the speeds of processors and I/O devices has resulted in the I/O subsystem becoming a bottleneck in many applications. The use of multiple disks to build a parallel I/O subsystem has been advocated to enhanceI/ performance and system availability [3] , and most current high-performance systems incorporate some form of parallel I/O. Given a D-disk parallel I/O system and a globally shared I/O buffer that can hold upto M disk blocks, we derive a lower bound of Q(a) on the competitive ratio of any deterministic online prefetching algorithm with O(M) lookahead. NOM is shown to match the lower bound using global M-block lookahead. In contrast, using only locallookahead results in an Q(D) competitive ratio. When the buffer is distributed into D portions of M/D blocks each, the algorithm GREED based on local lookahead is shown to be optimal, and NOM is within a constant factor of optimal. Thus we provide a theoretical basis for the intuition that global lookahead is more valuable for pmfetching in the case of a shared buffer configuration whereas it is enough to provide local lookaheadin case of the distributed configuration. Finally, we analyze the performance of these algorithms for reference strings generated by a uniformlyrandom stochastic process and we show that they achieve the minimal expected number of UOs. These results also give bounds on the worst-case expected performance of algorithms which employ randomization in the data layout Ptefetching is a powerful technique to reduce the JfO latency seen by an application. This is particularly true in a parallel I/O system where prefetching can be effectively used to obtain parallelism in disk access, so that the disks are most efficiently used. To fully exploit this potential, it is important to design and implement prefetching and buffer management algorithms that ensure that the most useful blocks are fetched and retained in the I/O buffer. We consider a parallel l/O system consisting of D independent disks that can be accessed in parallel [12] . The data for the computation is spread out among the disks in units of blocks. A block is the unit of access from a disk As far as I/O is concerned, the computation is characterized by a reference string consisting of an ordered sequence of blocks that the computation accesses. In general, the reference string corresponding to a computation can consist of an arbitrary interleaving of reference strings of several concurrent applications. For the computation to successfully access a data-block, it should be resident in the internal memory of the computer system. By serving a reference string, we refer to the act of carrying out a series of UO operations that make it possible for the computation to access blocks in the order specified by the reference string. A recent study [6] focussed on the off-line problem of serving an arbitrary but fully known reference string of blocks spread across D parallel, independent disks using parallel prefetchmg in conjunction with page replacement t. The authors presented and analyzed a very clever but somewhat complicated approximation algorithm for this problem. However, the practical issue of devising an online algorithm in the framework of competitive analysis [9] for the same problem was not addressed. Permission to make digitnlihnrd copies ofall or part ofthis nmtcrial tbr pcrsonnl or classroom use is granted without l>c provided 111:tt tltc cop& nrc not made or distributed for profit or connncrcinl ndvnn~agc. 111~' copyright notice, the title of 1111: publication and its dntc nppcnr. and notice is given lbnt copyrigh1 is by permission of lhc ACAI. Inc. To copy olltcnvise, to republish, to post on scnvrs or to rcdistribtnl: to lists. rcquircs specilic pemiission nndIor fee Copyright 19.97 ACM U-89731~9GG-1/97/l I ..$3.50 The performance of parallel versions of LRU and MIN [2] was analyzed in [l 11. Modeling a distributed parallel Y/O system, with independent disks and a partitioned I/O buffer, they defined a parallel version of MIN, and showed that it is optimal. The performance of online algorithms in a more tightly coupled system where the buffer can be shared by the different disks was not considered. In this paper we present a competitive analysis framework for parallel prefetching algorithms on parallel disk systems for a re-'NotethatnplacementdecisionsareneccssitatedbythefactthattbeUObuffercan hold only some fixed number, say M. of pages.
The problem of online scheduling of read-once reference strings in a multiple-disk system was first addressed in REF .
Competitive parallel disk prefetching and buffer management
IOPADS '97
Computer Science