Markov model prediction of I/O requests for scientific applications.
Given the increasing performance disparity between processors and storage devices, exploiting knowledge of spatial and temporal I/O requests is critical to achieving high performance, particularly on parallel systems. Although perfect foreknowledge of I/O requests is rarely possible, even estimates of request patterns can potentially yield large performance gains. This paper evaluates Markov models to represent the spatial patterns of I/O requests in scientific codes. The paper also proposes three algorithms for I/O prefetching. Evaluation using I/O traces from scientific codes shows that highly accurate prediction of spatial access patterns, resulting in reduced execution times, is possible.
INTRODUCTION
The disparity between processor and disk performance
continues to increase, driven by market economics that reward
high-performance processors and high-capacity storage
devices. As parallel systems (e.g., clusters) are increasingly
constructed using large numbers of commodity components,
This work was supported in part by the National Science
Foundation under grants NSF ASC 97-20202, NSF ASC 99-
75248 and NSF EIA-99-72884; by the Department of Energy
under contracts LLNL B341494 and LLNL B505214; and by
the NSF Alliance PACI Cooperative Agreement.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
ICS'02, June 22-26, 2002, New York, New York, USA.
I/O has become a performance bottleneck for many scientic
applications. Characterization of application I/O patterns
has shown that many of these applications have complex,
irregular I/O patterns [4, 18], mediated by multilevel I/O
libraries, that are ill-suited to le system policies optimized
for simple sequential patterns (i.e., sequential read ahead
and write behind).
Patterson et al [12] showed that large I/O performance
gains are possible using hints to advise le systems and
I/O libraries of anticipated I/O accesses. Given foreknowledge
of temporal and spatial I/O patterns, one can schedule
prefetching and write behind requests to ameliorate or
eliminate I/O stalls. Indeed, with foreknowledge, optimal
le cache replacement decisions are possible under restricted
conditions [8].
Unfortunately, perfect foreknowledge is rarely possible.
An application's I/O access stream may be data dependent,
or it may change due to user interactions. Moreover, for
complex, irregular patterns, an enumeration of the complete
request stream often requires multilevel instrumentation to
capture and record I/O patterns for reuse when guiding future
executions. Not only is such instrumentation expensive,
it requires storing the access pattern.
Rather than specifying a complex I/O pattern exactly,
probabilistic models can potentially capture the salient features
more compactly by describing likely request sequences.
Although statistical characterization of I/O patterns is less
accurate than enumeration, it is compact and, as we shall
see, can be used to guide caching, prefetching, and write
behind decisions. Hence, this paper explores techniques for
constructing compact, Markov models of spatial access pat-
terns, evaluating the e-cacy of the predictions using I/O
traces drawn from large-scale scientic codes.
The remainder of the paper is organized as follows. In x2,
we outline Markov model construction techniques. This is
followed in x3{x4 by a description of our implementation and
test suite. In x5, we describe the results of trace-driven simulations
that evaluate the performance of several prediction
algorithms, as well as timing experiments using scientic
codes. Finally, in x6{x7, we summarize related work and
results, and we outline plans for future work.
2. MARKOV MODEL PREDICTION
One of the lessons from experimental analysis of I/O patterns
in parallel codes is that their behavior is far more
complex than originally expected [4, 16, 14, 18, 13]. Unlike
sequential I/O patterns on vector systems, parallel I/O
1.5e+062.5e+063.5e+064.5e+060 2000 4000 6000 8000 10000 12000 14000 16000
Initial
offset
(bytes)
Request number

Figure

1: Initial CONTINUUM I/O Request Osets
patterns are often strided or irregular and vary widely in
size.
2.1 I/O Pattern Complexity
Simple approaches to le system tuning such as N-block
read ahead work well for sequential access patterns, but they
are inappropriate for more irregular patterns. As an example

Figure

1 shows the initial le osets for requests from
execution of CONTINUUM, a parallel, unstructured mesh
code whose I/O behavior was captured using our Pablo I/O
characterization toolkit [4]. Fewer than half the I/O requests
follow sequentially from the previous request.
Complex patterns such as those in CONTINUUM cannot
be reduced to simple rules (i.e., sequential or strided) and
can only be captured by more powerful and expressive meth-
ods. Moreover, such complex patterns are common when
application I/O requests are mediated by multilevel I/O libraries

2.2 Markov Models
To capture non-sequential I/O patterns, we have chosen
to model an application's I/O access stream as a Markov
model. A Markov model with N states can be fully described
by its transition matrix P . Each value P ij of this N by N
matrix represents the probability of a transition to state j
from the current state i. Because the transition probabilities
depend only on the current state, the transition path to the
current state does not aect future state transitions; this
characteristic is known as the Markov property [7].
Given a le system block size, we create a state for every
block associated with each le. Because application I/O requests
are not normally expressed as block osets, but rather
as byte osets, we convert each request into the sequence of
blocks that must be accessed to satisfy the application re-
quest. Hence, multiple requests to the same block result in
the block number being repeated in the access stream. A
transition occurs whenever a le block is accessed, and the
model's transition matrix is created by setting each P ij to
the fraction of times that state j is accessed immediately
after state i.
Consider two illustrative examples. First, a simple, sequential
access pattern is represented by a cyclic matrix {
each block is accessed once in succession. Second, Figure
2 illustrates a simple strided pattern that repeats multiple0 1
6 10135791111311From
To

Figure

2: Strided I/O Pattern and Transitions
times. Both of these examples highlight a key aspect of
Markov transition matrices, the matrices are sparse for all
but the most complex, irregular patterns. Consequently, one
can compactly represent access patterns for even large les.
However, the Markov property that allows compact representation
is also a potential error source. Because a block
access depends solely on the immediately preceding access,
the history of accesses is lost. For example, consider the
following pattern of block accesses: 0, 1, 0, 2, 0, 3, 0, 4.
The Markov model for this pattern has four transitions from
block zero, each with probability 0.25. Therefore, the model
implies that accesses to blocks one through four are equally
likely after access to block zero. However, if block three has
already been accessed, the next block to follow block zero is
block four.
2.3 Prediction Strategies
Given an I/O access pattern Markov model, it can be
used during a subsequent application execution to predict
future I/O accesses. Several dierent prediction strategies,
based on the Markov model, are possible, ranging in complexity
from simply following the most likely sequence of single
step state transitions (greedy prediction) to more complex
schemes that predict the most likely N-step path. Each
diers in implementation complexity, execution overhead,
and associated predictive power.
Greedy Prediction. The simplest prediction method chooses
a sequence of le blocks by repeatedly nding the most likely
transition from the current state s. This approach builds
directly on N-step transition models from Markov theory.
Hence, we call this algorithm greedy-xed.
The sequence of predicted blocks stops when a specied
number of blocks is reached, though other terminating conditions
are possible. For instance, the sequence might be
terminated when the total likelihood of the sequence drops
below a given threshold. This results in predictions of varying
length. In either case, the greedy-xed prediction strategy
provides a (possibly variable length) le block sequence
that can be used for prefetching or write behind.
Path Prediction. Greater prediction accuracy may be possible
by choosing a sequence with the highest total likeli-
hood, rather than choosing the most likely sequence of single
step transitions. This method treats the Markov model
as a graph and performs a depth-limited search, beginning
at the current state, to nd the most likely path. We call
this path-xed prediction. It can choose less likely initial
transitions if they lead to high probability sequences.
Amortized Prediction. For I/O access patterns that revisit
a block many times, the most likely predicted path may not
visit the block. However, enough alternate paths may visit
the block to cause it to be accessed more often during the
application execution. To explore the eectiveness
of such a approach, we propose a method called amortized
prediction, so named because the value of predicting a block
is in a sense amortized over the entire execution rather than
just over the next L blocks.
Amortized prediction creates the state occupancy probability
vectors (t) for each of the next L time steps and
chooses the most likely state in each vector as the prediction
for that time step. The initial probability vector (0)
is zero except for element s (0), which is set to one. The
vectors (1) through (L) are generated by repeated application
of the Kolmogorov equation
P is the model's transition matrix. Block j of the prediction
sequence is chosen as the state with the greatest probability
in (j).
3. ASSESSMENT INFRASTRUCTURE
To assess the e-cacy of Markov models in predicting I/O
access patterns within scientic applications, we have relied
on three approaches: trace-driven simulation, cache simula-
tion, and experimental measurement within a research le
system.
3.1 Trace-Driven Assessment
We constructed Markov models using a sparse matrix
strategy to represent the Markov model's transition matrix
and reduce storage requirements. Many scientic applications
typically have regular, though not sequential, le access
patterns. With such regularity, only a few transitions
occur for each state. If the average number of transitions
from a source state is bounded above by a small constant,
the size of the matrix will grow linearly, rather than quadrat-
ically, with the size of the le.
Our trace-driven simulator accepts these sparse matrix
Markov models, a prediction strategy, and an application
I/O trace in the Pablo Self-Dening Data Format (SDDF)
[1], and then computes prediction accuracies. Figure 3 details
the simulator's operation.
3.2 Cache Simulation
We also developed a simple le cache simulator with LRU
replacement of xed-size blocks. After each request to the
cache is satised, either by a cache hit or by loading the requested
block, the cache prefetches additional blocks specied
by a prediction algorithm.
Application
Trace File
Library
Markov
Model
Builder
Markov Model
I/O Request
Algorithm
Prediction
Predicted
Sequences
Comparison
Prediction
Accuracy
Results

Figure

3: Trace-Driven Simulator Structure2e+066e+061e+071.4e+07
Initial
offset
(bytes)
Request number

Figure

4: Cactus I/O Request Pattern (Detail)
3.3 File System Measurement
To explore the thesis that performance is best maximized
by tuning le system policies to application behavior, we
also developed a portable parallel le system (PPFS2) that
consists of a portable, user-level input/output library with a
variety of le caching, prefetching, and data policies. PPFS2
executes atop a Linux cluster and uses the underlying le
system for I/O. We have used PPFS2 to study temporal
access pattern prediction via time series [19, 20].
In conducting experiments, we used a cluster of 32 dual
processor, 933 MHz Intel Pentium III systems linked though
Gigabit Ethernet. Each machine contained 1 GB of memory
and ran the Linux 2.2 kernel. Disk requests were serviced
by an on each machine.
4. SCIENTIFIC APPLICATION SUITE
To assess the accuracy of compact Markov models for
I/O prediction and their utility for le block prefetching,
we chose a suite of six scientic applications. These parallel
applications have been the subject of extensive analysis [4,
16, 14] and were chosen for their large size and variety of
I/O request characteristics.
All I/O traces were obtained using our Pablo I/O characterization
toolkit [4]. For simplicity, we have used the I/O
trace data from a single node of each parallel application
execution, and we model the application's requests to a sin-
0Request
size
(bytes)
Request number

Figure

5: CONTINUUM Request Sizes
gle le. Each application code is brie
y described in the
paragraphs below.
Cactus. The Cactus code [2] is a modular environment for
developing high-performance, multidimensional simulations,
particularly for numerical relativity; the test problem used
to obtain the I/O trace was a black hole simulation.
The read requests for this test problem were all extremely
small, with the largest being a mere sixteen bytes, though
the le request osets span almost a gigabyte. Over percent
of the requests are sequential, and almost 98 percent
are within 50 bytes of the previous request. However, the
remaining requests are to regions at least 1 MB from the previous
request and often greater than 10 MB away. Figure 4
shows a detailed view of the rst six hundred requests.
CONTINUUM. CONTINUUM 1 is an unstructured mesh
continuum mechanics code. CONTINUUM's I/O requests
are primarily restricted to the rst eighth of the le, as
shown in Figure 1. However, end of the le accesses occur
at regular intervals.
Over 57 percent of the accesses are non-sequential, but the
seek distances within the rst eighth of the le are small.
Most interestingly, Figure 5 shows that the request sizes
vary widely, ranging from less than 10 bytes to more than
100,000 bytes.
Dyna3D. Dyna3D is an explicit nite-element code for analyzing
the transient dynamic response of three-dimensional
solids and structures. This application generates a long
sequence of sequential requests; one processor sequentially
reads the rst 2 MB of a large input le a single byte at a
time.
Hartree-Fock. The Hartree-Fock code [5] calculates interactions
among atomic nuclei and electrons in reaction paths,
Trace data for the CONTINUUM and HYDRO codes are
taken from codes that use an existing serial I/O library.
Developers analyzed this library and determined it to be
unsuitable for a parallel environment. Developers of the
replacement I/O library expect a very dierent pattern of
I/O once the new library is integrated into the codes.1e+063e+065e+060 50 100 150 200 250 300 350 400
Initial
offset
(bytes)
Request number

Figure

Hartree-Fock I/O Request Pattern1e+063e+065e+067e+060 100 200 300 400 500 600
Initial
offset
(bytes)
Request number

Figure

7: HYDRO I/O Request Pattern
storing numerical quadrature data for subsequent reuse. I/O
requests each retrieve 80 KB of data, and the le is accessed
sequentially six times. Figure 6 shows the le osets and
data reuse.
HYDRO. HYDRO 1 is a block-structured mesh hydrodynamics
code with multi-group radiation diusion. The majority
of I/O accesses are to three widely separated regions of
the le. Sixty-seven percent of the accesses follow sequentially
from the previous access, but seeks of up to almost
eight million bytes also occur. The distribution of the request
sizes ranges from one byte to almost one million bytes.
SAR. The SAR (synthetic aperture radar) code produces
surface images from aircraft- or satellite-mounted radar data.
As

Figure

8 shows, the application issues two sequential re-
quests, followed by a seek to the next portion of the le.
Request sizes range from 370 KB to almost 2 MB.
5. EXPERIMENTAL ASSESSMENT
Given the simulation infrastructure of x3 and I/O traces
from the application suite of x4, we built Markov models for
Request
position
and
extent
(bytes)
Request number

Figure

8: SAR I/O Request Pattern
the associated I/O patterns and analyzed the accuracy of
these models by comparing model predictions with actual
I/O requests. We also investigated the eect of le block
sizes on model size and complexity and analyzed prediction
accuracy for both single and multiple block predictions.
5.1 Prediction Accuracy
Because Markov models are a lossy representation of application
I/O patterns, the simplest metric of prediction accuracy
is the dierence between model predictions and application
request streams. This approach allows one to assess
e-cacy as a function of spatial I/O patterns.
The simulator of Figure 3 generates a prediction sequence
of length L before each application block request is pro-
cessed. The accuracy of the prediction sequence is the fraction
of the predicted blocks that exactly match the blocks
requested during the next L timesteps. The overall accuracy
is the arithmetic mean across all predicted request se-
quences, capturing the eects of le block size, prediction
length, and prediction algorithm.
Block Size. The most basic choice when building Markov
models of I/O activity is the choice of block size. Matching
the model's block size to le cache or disk block size is the
most natural choice. Intuitively, larger block sizes reduce
the model's storage requirements, but they provide weaker
bounds on the range of bytes requested. Larger blocks provide
implicit prefetching, which interacts with access pattern
sequentiality and request size.

Figure

9 shows the single step (i.e., greedy with a single
block lookahead) prediction accuracy of each I/O trace
as a function of block size. The CONTINUUM, HYDRO,
Cactus, and Dyna3D codes all show high accuracy for each
block size, and this accuracy is near constant across block
sizes.
In contrast, the prediction accuracy for the SAR code declines
sharply as the block size increases due to repeated le
seeks. The large, 80 KB requests by the Hartree-Fock code
create non-linear behavior; large blocks prefetch data that is
unused when the stride boundaries of Figure 6 are crossed.
More generally, this behavior is a consequence of the regularity
of application request patterns and the proximity of0.550.650.750.850.954096 8192 16384 32768 65536 131072 262144
Prediction
accuracy
Block size (bytes)
Cactus
CONTINUUM
Dyna3d
Hartree-Fock
HYDRO

Figure

9: One Step Accuracy (Multiple Block Sizes)0.20.61
Prediction
accuracy
Prediction length
Cactus
CONTINUUM
Dyna3d
Hartree-Fock
HYDRO

Figure

10: Greedy Fixed Accuracy (64 KB Blocks)
the block size to the request size. As the block size approaches
the request size from above, each state in the associated
Markov model has a single transition to the next
state and fewer transitions back to itself. From the other
side, self-transitions interrupt the procession from one state
to another more frequently. These factors result in a model
where the most likely state transition has a low probability
compared to other models. This suggests that the block
size should be some reasonable multiple of the application
request size that amortizes disk I/O overhead unless the application
request sizes are very large.
Prediction Length. For prefetching to be eective, it must
accurately predict the access pattern for a request sequence;
only with such predictions can the I/O system stage data
for requests. Figure 10 shows the eect of prediction path
length for a 64 KB block size and a greedy-xed prediction
strategy.
Not surprisingly, prediction accuracy generally decreases
as prediction length increases. The prominent exception is
again the Hartree-Fock code. Because the single step prediction
accuracy for 64 KB blocks is low, the multiplicative
eect of a prediction sequence is also low. Even for 4 KB
blocks (not shown), where Hartree-Fock has a single step
accuracy of over 90 percent, the prediction accuracy is only
percent when predicting 25 steps ahead.
Prediction Algorithm. The multi-step prediction errors for
the SAR and Hartree-Fock codes illustrate the information
loss from the compact Markov model { the memoryless property
means that certain seek patterns, can trigger mispredictions
for greedy lookahead strategies. This is the rationale
for the path-xed and amortized strategies described in x2.3.
We tested each prediction strategy on multiple block sizes
and prediction lengths up to 25 steps. In most cases, the
three algorithms resulted in similar prediction accuracy, with
all declining in accuracy as the sequence length increased.
However, Figure 11 shows a wide gap between performance
of the amortized, greedy xed, and path xed strategies for
the Hartree-Fock code and two large block sizes.
The reason for this striking dierence is that after a few
steps using amortized prediction, enough probability mass
has moved to a succeeding state to cause the predicted state
to change for the following steps. Greedy xed, and to a
lesser degree path xed, continue following the most likely
transition and will not account for multiple paths to another
state.
5.2 Cache Behavior
Access prediction accuracy is but one metric of Markov
model utility. To assess the benets of Markov models for
predicting I/O requests, we also simulated a simple client
cache and compared prefetching using the Markov model to
using a baseline N block read ahead strategy.
The simulated cache requests a prediction of length N
after each block request, and the predicted blocks are loaded
if not already there. Replacement is via a standard LRU
policy, with predicted blocks already present in the cache
placed with newly fetched blocks at the end of the LRU
list. We conducted experiments using block sizes of 1 KB,
4 KB, 16 KB, and 64 KB, a variety of le cache sizes, and
prediction horizons from 1 to 10 blocks.
Given the relatively strong sequentiality in the application
I/O access patterns, all three prediction strategies yield relatively
high cache hit ratios. Figures 12{13 show the cache
hit ratios for two typical cases, the HYDRO and Cactus
codes. Here, the greedy and amortized prediction strategies
always perform better than N block read ahead when
prefetching multiple blocks, and they often perform better
when predicting only one or two steps ahead.
5.3 File System Measurements
The true test of any I/O prediction strategy is its performance
as part of a parallel le system. Only such tests
capture the interplay of application and system features.
Hence, we also conducted experiments using Cactus and a
synthetic application similar to Hartree-Fock. Both were
modied to use PPFS2, the user-level parallel le system
of x3. PPFS2 was extended to support N block read ahead
and our Markov model prediction methods, and to use these
policies for block prefetching decisions.
To assess the benets of Markov model prediction over
standard prefetch policies, we ran experiments using the
Cactus code on a 50x50x50 grid for 2000 iterations. This results
in over 2 million block read requests distributed across
a 2 GB data le. We congured our PPFS2 testbed to use a
le cache with 4 KB and 8 KB blocks, an LRU cache0.960.981
Hit
rate
Prefetch depth
N-block readahead
Greedy-fixed
Amortized

Figure

12: HYDRO Cache Hit Ratios0.960.981
Hit
rate
Prefetch depth
N-block readahead
Greedy-fixed
Amortized

Figure

13: Cactus Cache Hit Ratios
replacement strategy, and a prefetch depth that ranged from
blocks. Only read requests were cached; write requests
were sent directly to the underlying le system, which
for our purposes was a single local disk. The Markov model
predictions were computed using greedy-xed, the simplest
prediction strategy.

Figure

14 shows the results of these experiments for a variety
of prefetch distances. The experiments using Markov
model prediction showed a performance improvement over
all tested prefetch depths when compared to both N block
readahead and no prefetching. Total application execution
time decreased by up to 10% over the no prefetching case
when using 8 KB blocks, and up to 3% when using 4 KB
blocks. N block readahead yielded substantially poorer performance
than either of the other two methods, which conrms
our assertion that le system policies designed for sequential
access patterns can be inappropriate for scientic
codes. The data from Figure 14 also show that the overhead
for using the Markov model is small and that the overhead
is repaid by improved prefetch predictions.

Figure

15 shows the cache hit rates recorded during these
tests. For both block sizes, Markov model prediction achieves
Prediction
accuracy
Prediction sequence length
Greedy-fixed
Path-fixed
Prediction
accuracy
Prediction sequence length
Greedy-fixed
Path-fixed
Amortized-fixed
(a) 64 KB Block Size (b) 256 KB Block Size

Figure

11: Hartree-Fock Strategy Comparison2006001000
Time
Prefetch depth (blocks)
N-block
N-block (4KB)
prefetching (8KB)
prefetching (4KB)
Markov
Markov (4KB)

Figure

14: Cactus Execution Time
a hit rate of over 99.99%. N block readahead achieves a hit
rate of over 98%, but the large performance dierence between
the two methods indicates that N block readahead is
prefetching many blocks that go unused.
To further quantify the overhead of Markov models, we
wrote a synthetic code that issues requests in the Hartree-Fock
pattern of x4. This synthetic code reads the 2.64 MB
input le sequentially six times via 396 requests. Each 80
KB request is followed by a loop that iterates for approximately
one millisecond, simulating a compute cycle. This
pattern is ideally suited to N Block readahead, and any large
overhead in the Markov model approach will be apparent.

Figure

shows the results of this experiment for a 1 MB
cache and 8 KB blocks. Markov model prediction performs
just as well as N block readahead for this request pattern.
The two algorithms also result in a decreased execution time
compared to the no prefetching case, with the time savings
reaching over 13% when prefetching 10 blocks at a time.0.9750.9850.9951 2 3
Cache
hit
rate
Prefetch depth (blocks)
Markov (4KB)
Markov
N-block (4KB)
N-block

Figure

15: Cactus Cache Hit Rate
5.4 Experiment Summary
Our results have shown high prediction accuracy across a
large range of block sizes and look ahead lengths using sim-
ple, greedy prediction strategies for most application I/O
patterns. However, because the amortized strategy yielded
results equal to those for greedy strategies in most cases and
substantially better performance in some others, we believe
the additional complexity of non-greedy strategies is justi-
ed. In addition, our timing experiments, using a user-level
le system modied with Markov models, demonstrate that
our approach can noticeably reduce the execution time of a
sample scientic application. We also demonstrate that the
overhead is very low.
6. RELATED WORK
Many groups have examined the spatial and temporal I/O
patterns of scientic applications. Smirni et al [17, 16, 15,
characterized the I/O accesses in a suite of scientic ap-0.8
Time
Prefetch depth (blocks)
prefetching
N-block
Markov

Figure

Hartree-Fock Execution Time
plications drawn from the Scalable I/O initiative [4]. Characterization
showed that the applications exhibited access
patterns ranging from simple sequential accesses to interleaved
patterns across processors. Although simple descriptions
are su-cient to describe these patterns, introduction
of higher-level I/O libraries such as FlexIO [11] has led to
even more complicated patterns.
Patterson et al [12] used application-provided hints to
guide prefetching and caching decisions. Their integrated
caching and prefetching system used a cost-benet analysis
to decide when to prefetch and which blocks to replace in
the cache.
Vellanki and Chervenak [21] used an approach similar
to Patterson's but replaced application-provided hints with
an automatically-generated probabilistic model of the access
stream. They built and used a prefetch tree using the
Lempel-Ziv scheme from Duke [22, 6]. In addition to reducing
the size of the access stream, this tree allowed prediction
of future accesses based on likely paths through the tree. Restricting
the width of the tree allowed them to decrease its
storage requirements at the cost of additional inaccuracy in
the predicted accesses. Our use of Markov models builds
on many of these ideas but emphasizes congurability and
compatibility with temporal prediction schemes [19].
Articial neural networks (ANNs) have been used previously
in I/O pattern characterization. Madhyastha and
Reed [10, 9] used ANNs and hidden Markov models to assign
the request pattern a simple qualitative classication
such as \sequential" or \variably-strided." Markov models
have also been used by Cortes and Labarta [3] to identify
and predict strided access patterns. Our work diers by providing
an explicit prediction of which blocks to expect next
and to represent arbitrary access patterns.
7. CONCLUSIONS AND FUTURES
We have outlined an approach to access pattern prediction
based on Markov models and several associated prediction
strategies. Using I/O traces from large scientic ap-
plications, our experiments explored the eects of varying
the block size used to build the model, the length of the
predicted I/O stream, and the algorithm used to generate
predictions.
The experimental data suggests that for the irregular I/O
patterns found in today's scientic applications, Markov
models strike an eective balance between implementation
complexity and predictive power. For reasonable block sizes,
performance is largely independent of block size, allowing le
system designers to choose a set of defaults, while achieving
high performance. This allows users of these models to
choose a block size appropriate to their tasks without affecting
prediction accuracy to a large degree. Finally, an
amortized path scheme is generally more eective in predicting
access patterns than simple greedy schemes.
Several opportunities exist for future study, including more
extensive experiments with scientic applications. Also, our
current techniques assume that one or more previous runs
are available to generate the Markov model; allowing the
model to be created and used online may provide benets
over uninformed prefetching and caching even though large
parts of the application pattern have not yet been integrated
into the model. Finally, in cases where hints are provided
about future I/O accesses, Markov models can be used to
establish the accuracy of those hints to be measured. This
would allow an adaptive le system to decide if using the
hinted sequence for further prefetching or caching is likely
to provide benet.
8.



--R

The Pablo Self-De ning Data Format
Three Dimensional Numerical Relativity with a Hyperbolic Formulation.
Linear Aggressive Prefetching: a Aay to Increase Performance of Cooperative Caches.
Characterization of a Suite of Input/Output Intensive Applications.
Input/Output Characteristics of Scalable Parallel Applications.
Practical Prefetching via Data Compression.
The Art of Computer Systems Performance Analysis.
A Trace-Driven Comparison of Algorithms for Parallel Prefetching and Caching
Automatic Classi
Input/Output Access Pattern Classi
Diving deep: Data-management and visualization strategies for adaptive mesh re nement simulations
Informed prefetching and caching.
Scalable Input/Output: Achieving System Balance.
A Comparison of Logical and Physical Parallel I/O Patterns.
I/O Requirements of Scienti
Performance Modeling of a Parallel I/O System: An Application Driven Approach.
Workload Characterization of Input/Output Intensive Parallel Applications.
Lessons from Characterizing the Input/Output Behavior of Parallel Scienti
ARIMA Time Series Modeling and Forecasting for Adaptive I/O Prefetching.
Automatic ARIMA Time Series Modeling and Forecasting for Adaptive Input/Output Prefetching.
Prefetching Without Hints: A Cost-Bene t Analysis for Predicted Accesses
Optimal prefetching via data compression.
--TR
Practical prefetching via data compression
Informed prefetching and caching
Input/output characteristics of scalable parallel applications
Optimal prefetching via data compression
A trace-driven comparison of algorithms for parallel prefetching and caching
Input/output access pattern classification using hidden Markov models
Lessons from characterizating the input/output behavior of parallel scientific applications
series modeling and forecasting for adaptive I/O prefetching
Diving Deep
Linear Aggressive Prefetching
Workload Characterization of Input/Output Intensive Parallel Applications
I/O Requirements of Scientific Applications
Automatic classification of input/output access patterns
Automatic arima time series modeling and forecasting for adaptive input/output prefetching

--CTR
Nancy Tran , Daniel A. Reed, Automatic ARIMA Time Series Modeling for Adaptive I/O Prefetching, IEEE Transactions on Parallel and Distributed Systems, v.15 n.4, p.362-377, April 2004
Yifeng Zhu , Hong Jiang, CEFT: a cost-effective, fault-tolerant parallel virtual file system, Journal of Parallel and Distributed Computing, v.66 n.2, p.291-306, February 2006
storage;markov model;parallel computing