Disk-bound applications, increasingly common as faster computers and larger storage encourage users to manipulate more data, have their performance determined by storage rather than processor performance. While parallel storage systems are increasingly common, applications that exploit them well are not. Aggressive prefetching is a simple way to effectively utilize storage parallelism to reduce application latency, provided sufficiently detailed predictions of future accesses can be made sufficiently early.
This paper extends aggressive prefetching research with an automatic hint generation technique based on speculative pre-execution using mid-execution application state. Invoked only when the application is stalled waiting for I/O, speculative execution can add little or no observable overhead to the application. Provided that cycles are available in these time periods, speculative execution can discover future read accesses and issue hints to an aggressive prefetching system.
We have designed and implemented a binary modification tool that transforms
Digital UNIX binaries to automatically perform speculative execution.
Applied to a text search utility, a linker, and a 3-D visualization program,
our system demonstrated 29% to 70% reductions in execution time with a
four-disk array. A principle limitation of the current design is the lack
of more effective automatic mechanisms for limiting the penalty of erroneous
hinting due to data dependencies. The relatively large success of our
currently unsophisticated design demonstrates that speculative execution is
a promising new approach to aggressive I/O prefetching.