USENIX Technical Program - Paper - Proceedings of the Third Symposium on Operating Systems Design and Implementation
[Technical Program]
| Pp. 1–14 of the Proceedings |  |
  
Next: Introduction
Automatic I/O Hint Generation through Speculative Execution
Fay Chang and Garth A. Gibson
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
{fwc,garth}@cs.cmu.edu
Abstract
Aggressive prefetching is an effective technique for reducing the
execution times of disk-bound applications; that is, applications that
manipulate data too large or too infrequently used to be found in file or
disk caches. While automatic prefetching approaches based on static
analysis or historical access patterns are effective for some workloads,
they are not as effective as manually-driven (programmer-inserted)
prefetching for applications with irregular or input-dependent access
patterns. In this paper, we propose to exploit whatever processor cycles
are left idle while an application is stalled on I/O by using these cycles
to dynamically analyze the application and predict its future I/O accesses.
Our approach is to speculatively pre-execute the application's code in order
to discover and issue hints for its future read accesses. Coupled with an
aggressive hint-driven prefetching system, this automatic approach could be
applied to arbitrary applications, and should be particularly effective for
those with irregular and, up to a point, input-dependent access patterns.
We have designed and implemented a binary modification tool, called
``SpecHint'', that transforms Digital UNIX application binaries to perform
speculative execution and issue hints. TIP [Patterson95], an informed
prefetching and caching manager, takes advantage of these application-generated
hints to better use the file cache and I/O resources. We evaluate our
design and implementation with three
real-world, disk-bound applications from the TIP benchmark suite. While our
techniques are currently unsophisticated, they perform surprisingly well.
Without any manual modifications, we achieve 29%, 69% and 70% reductions
in execution time when the data files are striped over four disks, improving
performance by the same amount as manually-hinted prefetching for two of our
three applications. We examine the performance of our design in a variety
of configurations, explaining the circumstances under which it falls short
of that achieved when applications were manually modified to issue hints.
Through simulation, we also estimate how the performance of our design will
be affected by the widening gap between processor and disk speeds.
Next: Introduction
Fay Chang
Tue Jan 5 18:05:04 EST 1999
|
Technical Program