Tight Bounds for Prefetching and Buffer Management Algorithms for Parallel I/O Systems.
AbstractThe I/O performance of applications in multiple-disk systems can be improved by overlapping disk accesses. This requires the use of appropriate prefetching and buffer management algorithms that ensure the most useful blocks are accessed and retained in the buffer. In this paper, we answer several fundamental questions on prefetching and buffer management for distributed-buffer parallel I/O systems. First, we derive and prove the optimality of an algorithm, P-min, that minimizes the number of parallel I/Os. Second, we analyze P-con, an algorithm that always matches its replacement decisions with those of the well-known demand-paged MIN algorithm. We show that P-con can become fully sequential in the worst case. Third, we investigate the behavior of on-line algorithms for multiple-disk prefetching and buffer management. We define and analyze P-lru, a parallel version of the traditional LRU buffer management algorithm. Unexpectedly, we find that the competitive ratio of P-lru is independent of the number of disks. Finally, we present the practical performance of these algorithms on randomly generated reference strings. These results confirm the conclusions derived from the analysis on worst case inputs.
Introduction
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 increase
I/O performance and system availability [5], and most high-performance
systems incorporate some form of I/O parallelism. Performance is improved by
overlapping accesses at several disks using judicious prefetching and buffer management
algorithms that ensure that the most useful blocks are accessed and
retained in the buffer.
A parallel I/O system consists of D independent disks, each with its own disk
buffer, that can be accessed in parallel. The data for the computation is spread
out among the disks in units of blocks. A block is the unit of retrieval from a
disk. The computation is characterized by a computation sequence, which is the
ordered sequence of blocks that it references. In our model all accesses are read-
only. Prefetching (reading a data block before it is needed by the computation)
Research partially supported by a grant from the Schlumberger Foundation
?? Research partially supported by NSF grant CCR-9303011
is a natural mechanism to increase I/O parallelism. When the computation demands
a disk-resident block of data, concurrently a data block can be prefetched
from each of the other disks in parallel, and held in buffer until needed. This
requires discarding a block in the buffer to make space for the prefetched block.
Some natural questions that arise are: under what conditions is it worthwhile to
discard a buffer-resident block to make room for a prefetch block which will be
used only some time later in the future? And, if we do decide to discard a block,
what replacement policy should be used in choosing the block to be replaced.
In this paper we answer several fundamental questions on prefetching and
buffer management for such parallel I/O systems. The questions we address are:
what is an optimal prefetch and buffer management algorithm, and how good
are the algorithms proposed earlier for sequential (single) disk systems in this
context. We obtain several interesting results, which are informally stated below
and more precisely stated in Section 2. We find and prove the optimality of an
algorithm, P-MIN, that minimizes the number of parallel I/Os. This contrasts
with the recent results on prefetching to obtain CPU-disk overlap [4], where
no efficient algorithm to find the optimal policy is known. Secondly, we show
that P-CON, an algorithm that attempts to optimize the number of I/Os on
each disk, can have very poor parallel performance. Finally we investigate the
behavior of semi-on-line algorithms using parallel I/O. The concept of semi-online
algorithms that we consider in this paper captures the dual requirements
of prefetching (which needs some future knowledge) and on-line behavior (no
future knowledge). We define and analyze P-LRU, a semi-on-line version of the
traditional Least Recently Used (LRU) buffer-management algorithm. We find
the performance of P-LRU is independent of the number of disks, in contrast
to P-CON where the performance can degrade in proportion to the number of
disks.
In contrast to single-disk systems (sequential I/O) for which these issues have
been studied extensively (e.g. [2, 6]), there has been no formal study of these
issues in the parallel I/O context. In the sequential setting the number of block
(or I/Os) is a useful performance metric; scaling by the average block
access time provides an estimate of the I/O time. In contrast, in the multiple-
disk case there is no direct relationship between the number of I/Os and the I/O
time, since this depends on the I/O parallelism that is attained. The goals of
minimizing the number of I/Os done by each disk and minimizing the parallel
I/O time can conflict. Traditional buffer management algorithms for single-disk
systems have generally focused on minimizing the number of I/Os. In the parallel
context it may be useful to perform a greater than the absolute minimal (if the
disk were operated in isolation) number of I/Os from each disk, if this allows a
large number of them to be overlapped.
The rest of the paper is organized as follows. Section 1.1 summarizes related
work. Section 2 develops the formal model and summarizes the main results. In
Section 3.1 we derive a tight upper bound for P-CON algorithm. In Section 3.2
we prove the optimality of P-MIN. Section 3.3 analyzes the performance of the
semi-on-line algorithm P-LRU.
1.1 Related Work
In single-disk systems, buffer management (or paging problem) algorithms were
studied [2, 6, 11], and several policies (LRU, FIFO, Longest Forward Distance,
etc.) were proposed and analyzed. The Longest Forward Distance [2] policy minimizes
the number of page faults, and is therefore called the MIN algorithm. All
these policies use demand I/O and deterministic replacement, i.e. they fetch
only when the block being referenced is not in the buffer, and the choice of
the replaced block is deterministic. (Randomized replacement algorithms, e.g.
see [8], are beyond the the scope of this paper.) In the sequential case, it is well
known [11] that prefetching does not reduce the number of I/Os required.
Sleator and Tarjan [11] analyzed the competitive ratio of on-line paging algorithms
relative to the off-line optimal algorithm MIN. They showed that LRU's
performance penalty can be proportional to the size of fast memory, but no other
on-line algorithm can, in the worst case, do much better. These fundamental results
have been extended in several ways, most often to include models that allow
different forms of lookahead [3, 1, 9, 7]. All these works deal with the question of
which buffer block to evict. In contrast, in our situation the additional question
that arises is when to fetch a block and evict some other.
Cao et al. [4] examined prefetching from a single disk to overlap CPU and I/O
operations. They defined two off-line policies called aggressive and conservative,
and obtained bounds on the elapsed time relative to the optimal algorithm.
We use prefetching to obtain I/O parallelism with multiple disks, and use the
number of parallel I/Os (elapsed I/O time) as the cost function. The P-MIN
and P-CON algorithms analyzed here generalize the aggressive and conservative
policies respectively. However, while aggressive is suboptimal in the model of [4],
P-MIN is proved to be the optimal algorithm in our model. The prefetching
algorithm for multiple disks analyzed in [10] assumed a global buffer and read-once
random data.
We also investigate semi-on-line algorithms using parallel I/O. Since prefetching
involves reading blocks that are required in the future (relative to where the
computation has progressed), this presents a natural situation where lookahead
is necessary. This inspires us to define a lookahead version of LRU, P-LRU, in
which the minimum possible lookahead of one block beyond those currently in
the buffer is known for each disk. 3 We find the performance of P-LRU is independent
of the number of disks, in contrast to P-CON whose performance can
degrade in proportional to the number of disks.
Preliminaries
The computation references the blocks on the disks in an order specified by the
consumption sequence, \Sigma . When a block is referenced the buffer for that disk is
checked; if the block is present in the buffer it is consumed by the computation,
Recently, Breslauer [7] arrived at this lookahead definition independently in a sequential
demand context.
which then proceeds to reference the next block in \Sigma . If the referenced block is
not present in the disk buffer, then an I/O (known as a demand I/O) for the
missing block is initiated from that disk. If only demand I/Os were initiated,
then the other disks in the system would idle while this block was being fetched.
However, every demand I/O at a disk provides a prefetch opportunity at the
other disks, which may be used to read blocks that will be referenced in the near
future. For example, consider a 2-disk system holding blocks (a 1 ; a 2 ) and (b
on disks 1 and 2 respectively. If strictly demand I/O
would require four non-overlapped I/Os to fetch the blocks. A better strategy
is to overlap reads using prefetching. During the demand I/O of block a 1 , the
second disk could concurrently prefetch b 1 ; after a 1 and b 1 have been consumed,
a demand I/O for block b 2 will be made concurrently with a prefetch of block
a 2 . The number of parallel I/Os in this case is now two.
While prefetching can increase the I/O parallelism, the problem is complicated
by the finite buffer sizes. For every block read from a disk some previously
fetched block in the corresponding buffer must be replaced. For prefetch blocks
the replacement decision is being made earlier than is absolutely necessary, since
the computation can continue without the prefetched block. These early replacement
choices can be much poorer than replacement choices made later, since
as the computation proceeds, other, more useful replacement candidates may
become available. Of course, once a block becomes a demand block then the
replacement cannot be deferred. A poor replacement results in a greater number
of I/Os as these prematurely discarded discarded blocks may have to be fetched
repeatedly into the buffer. Thus there is a tradeoff between the I/O parallelism
that can be achieved (by using prefetching), and the increase in the number of
I/Os required (due to poorer replacement choices).
2.1 Definitions
The consumption sequence \Sigma is the order in which blocks are requested by the
computation. The subsequence of \Sigma consisting of blocks from disk i will be
denoted by \Sigma i . Computation occurs in rounds with each round consisting of an
I/O phase followed by a computation phase. In the I/O phase a parallel I/O is
initiated and some number of blocks, at most one from any disk, are selected
to be read. For each selected disk, a block in the corresponding disk buffer is
chosen for replacement. When all new blocks have been read from the disks,
the computation phase begins. The CPU consumes zero or more blocks that are
present in the buffer in the order specified by \Sigma . If at any point the next block of
\Sigma is not present in a buffer, then the round ends and the next round begins. The
block whose absence forced the I/O is known as a demand block; blocks that are
fetched together with the demand block are known as prefetch blocks. An I/O
phase may also be initiated before the computation requires a demand block. In
this case all the blocks fetched in are prefetch blocks. We will often refer to the
I/O phase of a round as an I/O time step.
An I/O schedule with makespan T , is a sequence hF
where F k is the set of blocks (at most one from each disk) fetched by the parallel
I/O at time step k. The makespan of a schedule is the number of I/O time steps
required to complete the computation.
valid schedule is one in which axioms A1 and A2 are satisfied.
block must be present in the buffer before it can be consumed.
- A2: There are at most M , where M is the buffer size, blocks in any disk buffer
at any time.
- An optimal schedule is a valid schedule with minimal makespan among all valid
schedules.
- A normal schedule is a valid schedule in which each F k , 1  k  T , contains
a demand block.
- A sequential schedule is a valid schedule in which the blocks from each disk i
are fetched in the order of \Sigma i .
At the start of a round, let U i denote the next referenced block of \Sigma i that is not
currently in the buffer of disk i. Define a min-block of disk i, to be the block in
disk i's buffer with the longest forward distance to the next reference.
is a normal, sequential
schedule in which at I/O step k, U i 2 F k unless all blocks in disk i's buffer are
referenced before U i . If U i 2 F k , then replace the min-block of disk i with U i .
is a normal, sequential
schedule in which at every I/O step k, U i 2 F k provided the min-block of disk i
now is the same as the min-block if U i were fetched on demand. If U
replace the min-block of disk i with U i .
is a normal, sequential
schedule in which at every I/O step k, U i 2 F k unless all blocks in disk i's buffer
are referenced before U i . If U i 2 F k then from among the blocks in the buffer
whose next reference is not before that of U i choose the least recently used block
and replace it with U i .
Notice that all three schedules defined above are normal. That is in every I/O
step, one disk is performing a demand fetch and the rest are either performing
a prefetch or are idle. Of these P-MIN and P-LRU are greedy strategies, and
will almost always attempt to prefetch the next unread block from a disk. The
only situation under which a disk will idle is if every block in the buffer will be
referenced before the block to be fetched. Note that this greedy prefetching may
require making "suboptimal" replacement choices, that can result in an increase
the number of I/Os done by that disk. We show, however, that P-MIN policy
has the minimal I/O time, and is therefore optimal.
An example with presented below. Let the blocks on
disk 1 (2) be a
Round Disk 1Disk 2 CPU
P-MIN Schedule
Round Disk 1Disk 2 CPU
P-CON Schedule
Round Disk 1Disk 2 CPU
9 \Gamma=\Gamma b3=b4 b3 ;
P-LRU Schedule
Fig. 1. Examples of I/O Schedules

Figure

1 shows the I/O schedule using different policies for the example se-
quence. The entries in the second and third columns indicate the blocks that are
fetched and replaced from that disk at that round. Bold and italic faced blocks
indicate a demand block, and a prefetch block respectively.
In contrast to P-MIN, the conservative strategy [4] P-CON, is pessimistic.
It does not perform a prefetch unless it can replace the "best" block, so that
the number of I/Os done by any disk is the smallest possible. However, while
minimizing the number of I/Os done by a disk, it may result in serialization of
these accesses, and perform significantly worse than the optimal algorithm. Note
that in Figure 1 at step 4, no block is fetched from disk 2 by P-CON. This is
because the only candidate for replacement at this time (the current min-block)
is block b 1 ; however, if b 4 were a demand block, the min-block would be b 3 .
To take advantage of a prefetch opportunity, any algorithm must know which
is the next unread block in \Sigma i . That is, it requires to have a lookahead upto at
least one block beyond those currently in its buffer. The replacement decision
made by P-LRU is based solely by examining the current blocks in the buffer,
and tracking which of them will be referenced before the next unread block.
From those whose next reference is not before that of the next unread block, the
least recently consumed block is chosen as the replacement candidate. If P-LRU
is applied to the sequence \Sigma used for P-MIN and P-CON, a schedule of 12 I/O
steps will be obtained (see Fig. 1). In the next section, we quantify precisely the
performance of these three algorithms.
2.2 Summary of Results
Let TP\GammaMIN , TP\GammaCON and TP\GammaLRU be the number of I/O time steps required by
P-MIN, P-CON and P-LRU respectively. Let T opt be the number of I/O steps
required by an optimal schedule. Let N denote the length of \Sigma ; also recall that
D is the number of disks and M the size of each disk buffer in blocks. The
technical results of the paper are as follows.
1. The worst-case ratio between the makespan of a P-CON schedule and the
corresponding optimal schedule is bounded by D. That is, at worst P-CON
can serialize all disk accesses without increasing the number of I/Os performed
by any disk (see Theorem 7).
2. The worst-case bound of P-CON stated above is tight. That is, there are
consumption sequences, for which P-CON completely serializes its accesses
(see Theorem 8).
3. P-MIN is an optimal schedule. That is it minimizes the number of parallel
time steps over all other valid schedules (see Theorem 11.)
4. The worst-case ratio between the makespan of a P-LRU schedule and the
corresponding optimal schedule is bounded by M . That is, at worst P-LRU
can inflate the number of I/Os performed by any disk to that done by a
serial LRU algorithm (see Theorem 13).
5. The worst-case bound of P-LRU stated above is tight. That is, there are
consumption sequences, for which P-LRU does inflate the accesses for each
disk by a factor of M (see Theorem 14).
3 Detailed Results
3.1 Bounds for P-CON
We begin with a simple upper bound for TP\GammaCON . Let TMIN denote the maximum
number of I/Os done by the sequential MIN algorithm to a single disk.
Theorem 7. For any consumption sequence, TP\GammaCON  D T opt .
Proof. We show that TP\GammaCON  DTMIN  DT opt . The I/Os made by P-CON to
disk i for consumption sequence \Sigma , are exactly the I/Os done by the sequential
MIN algorithm to disk i for sequence \Sigma i . Hence the number of I/Os performed
by any disk in P-CON is bounded by TMIN . At worst, none of the accesses of
any of the disks can be overlapped whence the first inequality follows. Finally,
the second inequality follows since the optimal parallel time for D disks cannot
be smaller than the minimal number of I/Os for a single disk. ut
Theorem 8. The bound of Theorem 7 is tight.
Proof (sketch). Construct the following four length-M sequences, where B i (j) is
the j th block on disk i. Aslo define \Sigma as follows, where (u) N means N repetitions
of the parenthesized sequence.
It can be argued that for \Sigma ,
1, and that the P-MIN schedule has length 2NM
1. Thus, TP\GammaCON =T opt is lower bounded by
3.2 Optimality of P-MIN
In this section we show that P-MIN requires the minimal number of parallel I/O
steps among all valid schedules. For the proof, we show how to transform an
optimal schedule OPT with makespan L, into a P-MIN schedule with the same
makespan.
Schedules ff and fi are said to match for time steps [T ], if for
every t, t 2 the blocks fetched and replaced from each disk in the two
sequences are the same.
Lemma 10. Assume that ff is a valid schedule of length W . Let fl be another
schedule which matches ff for [T \Gamma 1]. After the I/O at time step T , the buffers
of ff and fl for some disk i differ in one block: specifically ff has block V but not
block U , and fl has block U but not block V . Assume that V is referenced after
U in the consumption sequence following the references at time T \Gamma 1. We can
construct a valid schedule fi of length W , such that fi and ff match for
and fi and fl match at time step T .
Proof. Let be the first time step after T that ff fetches or discards
either block V or U . It can either discard block V , or fetch block U , or do both,
at Construct schedule fi as follows: fi matches ff for time steps [W ] except
at time steps T and
At T , fi fetches and replaces the same blocks as fl. At one of the
following must occur:
- ff fetches a block Z 6= U and discards block then in the construction fi
will also fetch block Z, but will discard block U .
- ff fetches block U and discards block Z, Z
and will also discard block Z.
- ff fetches block U and discards block does not fetch or discard
any block.
In all three cases above, following the I/O at will have the
same blocks in the buffer. Since fi fetches and replaces the same blocks as ff for
the buffers of ff and fi will be the same for all time
steps after the I/O at
At each time step t, 1  t  W , fi will consume the same blocks as done
by ff at t. Clearly, fi satisfies axiom A2. We show that fi is a valid schedule by
showing that axiom A1 is satisfied for all blocks consumed by fi.
Since ff and fi have the same buffer before the I/O at T and after the I/O at
the blocks consumed by ff at any time step t, t
also be consumed by fi at the same time step.
be the first time step after the I/O at T that either block U
or V is consumed by ff. Since ff does not have U in buffer till at least after the
I/O at and by the hypothesis, V is consumed after U , T Hence
only blocks, X 6= U; V can be consumed by ff at time steps t, T  t
Since the buffers of ff and fi agree except on fU; V g, X can also be consumed
by fi at the same time step. Since ff is a valid schedule, all consumptions of fi
also satisfy axiom A1. Hence, fi is a valid schedule. ut
Theorem11. P-MIN is an optimal schedule.
Proof. Let \Delta
and\Omega denote the schedules created by P-MIN and OPT algorithms
respectively. We successively
transform\Omega into another valid schedule
that matches \Delta and has the same length
as\Omega . This will show that the P-MIN
schedule is optimal.
The proof is by induction. For the Induction Hypothesis assume that at time
step
t,\Omega has been transformed to a valid
schedule\Omega t which matches \Delta at time
steps [t]. We show how to
to\Omega t+1 below.
We discuss the transformation for an arbitrary disk at time step t + 1. The
same construction is applied to each disk independently. If \Delta
and\Omega t match at
let\Omega t+1 be the same
as\Omega t . Suppose \Delta
and\Omega t differ at time step
one of the following three cases must occur at 1: We consider
each case separately.
but\Omega t does not fetch any block: Let \Delta fetch
block P and discard block Q at t + 1. Since \Delta always fetches blocks in the
order in which they are referenced, P will be referenced before Q. From the
Induction Hypothesis, \Delta
and\Omega t have the same buffer at the start of time
Hence after the I/O at t
and\Omega t differ in one block: \Delta has
block P but not block Q,
while\Omega t has Q but not P .
Using Lemma 10 with ff
we can construct valid
schedule\Omega t+1 that
matches\Omega t at time steps [t] and
\Delta at time t + 1. Hence, the Induction Hypothesis is satisfied for t + 1.
-\Omega t fetches a block but \Delta does not fetch any block: Since \Delta does
not fetch any block at time step t + 1, every block in the buffer at the start
of time step t will be consumed before any block not currently in the
buffer is referenced.
and\Omega t have the same buffer at the start of time step t
brings in a fresh block (P ) at must discard some block (Q). Since
\Delta chose to retain block Q in preference to fetching block P , then either Q
must be referenced before P , or neither P nor Q will be referenced again.
In the first case, using Lemma 10 with ff
1, we can
construct\Omega t+1 , a schedule that satisfies the Induction
Hypothesis for t + 1.
In the second
case,\Omega t+1 is the same
as\Omega t , except that at time step t
\Omega t+1 does not fetch any block. Since, the buffers
and\Omega t+1 agree on
all blocks except P and Q, and these two blocks are never referenced again,
all blocks consumed
by\Omega t at a time step can also be consumed
by\Omega t+1 at
that time.
and\Omega t fetch different blocks: Suppose that \Delta fetches block P
and discards block Q at t
and\Omega t fetches block Y and discards block Z
at t + 1. Assume that Q 6= Z, since otherwise the buffers
of\Omega t and \Delta differ
in just the pair of blocks fP; Y g, and we can easily
construct\Omega t+1 as before
by using Lemma 10 with ff
By the Induction Hypothesis, \Delta
and\Omega t have the same buffer at the start of
time step t + 1. Hence after the I/O at t
and\Omega t differ in two blocks;
specifically,
is the set of blocks in the buffer of schedule \Theta.
be the first time after
fetches or replaces
a block W 2 fP; Q; Y; Zg. It can either discard block Q or Y , or fetch
block P or Z, or some appropriate combination of these (see cases below),
at Construct
t+1 as
matches\Omega t at all time
steps
fetches P and discards Q,
following the actions of \Delta at this time step. Hence after the I/O at
Zg.
one of the following will occur:
ffl\Omega t fetches block
discards Q:
t+1 also fetches S,
but discards Z. After the I/O at
ffl\Omega t fetches P and discards Q:
fetches Y and discards Z. After
the I/O at
buffer(\Omega t ).
ffl\Omega t fetches Z and discards Q:
does nothing at this step. After
the I/O at
ffl\Omega t fetches
t+1 also fetches S, but
discards P . After the I/O at t+ ffi ,
fZg.
t+1 does not fetch any block at this
time step. After the I/O at
fZg.
ffl\Omega t fetches Z and discards Y :
fetches Q and discards P . After
the I/O at
buffer(\Omega t ).
ffl\Omega t fetches P and discards block
fetches Y and
discards block S. After the I/O at
ffl\Omega t fetches Z and discards block
fetches Q and
discards block S. After the I/O at
Consider the consumptions made
by\Omega t at time steps T , t+1  T  t+
Notice that in the consumption sequence P must precede both Q and Y ,
and Z must precede Q. The constraints on P follow since \Delta fetches P and
discards Q, and fetches P in preference to Y . The constraint on Z follows
since \Delta discards Q rather than Z.
We now show how to
to\Omega t+1 . If the buffers
are the same after the I/O at
t+1 . Otherwise, the
buffers must differ in either the pair of blocks fQ; Zg or fY; Pg.
We will
construct\Omega t+1 by concatenating the prefix
steps 1 and t schedule fi that will be constructed using
Lemma 10, as described below.
Let ff and fl be, respectively, the schedules consisting of the suffixes
t+1 for time steps greater than or equal to t . If at the end of the
I/O at the buffers
t+1 differ in fY; Pg, then let
they differ in fQ; Zg, then let
Applying Lemma 10 with construct the desired sequence fi.
\Omega t+1 is obtained by concatenating the prefix
with fi.
The consumptions of blocks
in\Omega t+1 are as follows: for time steps T , 1
the consumptions are those
consumptions are determined by fi. All consumptions from 1 till t are valid
since\Omega t is a valid schedule,
and\Omega t+1
and\Omega t match for [t]. By construction
blocks consumed after are valid. We need to show
can consume the same blocks
as\Omega t at time steps T ,
does not have P or Z in buffer at the end of the I/O at t + 1, it can
consume P or Z only after the I/O at time t later. Also, since Q and
Y must be consumed after P , none of the blocks can be consumed
before the I/O at after the I/O at t + 1, the buffers
and\Omega t+1 agree except on fP; Q; Y; Zg, all blocks consumed
can also be consumed
by\Omega t+1 at that time step.
This concludes the proof. ut
3.3 Bounds for P-LRU
We now obtain an upper bound on the worst-case performance of P-LRU, and
show that this bound is tight. We use the following lemma whose proof is omitted
for brevity.
Lemma 12. Let S be a contiguous subsequence of \Sigma which references M or less
distinct blocks from some disk i. Then in consuming S, none of these blocks will
be fetched more than once by P-LRU.
Theorem13. For all consumption sequences, TP\GammaLRU  MT opt .
Proof. Inductively assume that consumptions made in the first t steps by P-MIN
can be done in M t or less steps by P-LRU. (This holds for be the
set of references made by P-MIN at , since at most
distinct blocks can be consumed from any disk at a time step of P-MIN.
Since P-LRU will fetch a block of U i at most once (Lemma 12), all P-MIN's
consumptions at t + 1 can be done in at most an additional M steps. ut
Theorem 14. The worst-case bound of Theorem 13 is tight.
Proof (sketch). We show the construction of \Sigma for two disks; a i and b i are blocks
from disks 1 and 2 respectively. Note that after the first M accesses of \Sigma (com-
mon to both P-LRU and P-MIN), P-LRU makes M accesses for every access of
P-MIN.
In this paper we defined a model for parallel I/O systems, and answered several
fundamental questions on prefetching and buffer management for such systems.
We found and proved the optimality of an algorithm, P-MIN, that minimizes
the number of parallel I/Os (while possibly increasing the number of I/OS done
by a single disk). In contrast, P-CON, an algorithm which always matches its
replacement decisions with with those of the well-known single-disk optimal al-
gorithm, MIN, can become fully serialized in the worst case. The behavior of
an on-line algorithm with lookahead, P-LRU was analyzed. The performance of
P-LRU is independent of the number of disks. Similar results can be shown to
hold for P-FIFO, a parallel version of FIFO with lookahead.



--R

The influence of lookahead in competitive paging algorithms.
A Study of Replacement Algorithms for Virtual Storage.
A New Measure for the Study of On-Line Algo- rithms
A Study of Integrated Prefetching and Caching Strategies.

Operating Systems Theory.
On competitive on-line paging with lookahead
Competitive Paging Algorithms.
Beyond competitive analysis.
Markov Analysis of Multiple-Disk Prefetching Strategies for External Merging
Amortized Efficiency of List Update and Paging Rules.
--TR

--CTR
Mahesh Kallahalla , Peter J. Varman, Analysis of simple randomized buffer management for parallel I/O, Information Processing Letters, v.90 n.1, p.47-52, 15 April 2004
Mahesh Kallahalla , Peter J. Varman, Optimal prefetching and caching for parallel I/O sytems, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.219-228, July 2001, Crete Island, Greece
Mahesh Kallahalla , Peter J. Varman, PC-OPT: Optimal Offline Prefetching and Caching for Parallel I/O Systems, IEEE Transactions on Computers, v.51 n.11, p.1333-1344, November 2002
Michael Penner , Viktor K. Prasanna, Cache-Friendly implementations of transitive closure, Journal of Experimental Algorithmics (JEA), 11, 2006
Kai Hwang , Hai Jin , Roy S.C. Ho, Orthogonal Striping and Mirroring in Distributed RAID for I/O-Centric Cluster Computing, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.26-44, January 2002
external memory;competitive ratio;prefetching;algorithms;multiple-disk systems;buffer management;caching;Parallel I/O