Towards practical i/o prefetching
Wei Jin, Jeffrey S. Chase · 2000
Prefetching is an increasingly important technique to overcome the I/O bottleneck caused by the growing gap in access times to internal memory and external storage. The prefetching problem consists of three key subproblems: prediction, hinting, and prefetch scheduling. Progress with these subproblems requires new solutions and new tools to evaluate solutions experimentally and theoretically. The goal of this dissertation is to develop tools and techniques to improve the practicality of I/O prefetching along each of the dimensions listed above. In particular, it addresses issues for virtual memory-based data-intensive applications—virtual out-of-core (VOOC) applications. This dissertation makes significant steps forward in the design and evaluation of prefetch scheduling algorithms, compiler-based prediction for VOOC applications, and efficient integration of I/O prediction, hinting and prefetch scheduling schemes. (1) It classifies practical prefetch scheduling algorithms, discuss crucial features, proves new performance bounds, and quantifies the crucial role of replacement in prefetch scheduling. (2) It proposes a prefetch scheduling algorithm (BOUNDED-DEPTH) that has not been previously studied, and shows that it delivers competitive performance without requiring timing information in the predicted reference sequence. (3) It proposes a prefetch-safe trace reduction algorithm, FASTSLIM , that reduces the overhead of simulation and hinting while provably preserving the exact behavior of a broad range of prefetch scheduling schemes, replacement policies and system architectures. (4) It presents and evaluates a framework, called Dynamic Hinting Framework for Integrated Prefetching (DHIP), for practical use of prefetch scheduling. DHIP provides an interface and infrastructure to coordinate the operation of chosen prediction mechanisms and prefetch scheduling policies with program execution. DHIP drives generation of prefetching and replacement hints as needed by the prefetch scheduler, while minimizing hinting overhead. (5) It proposes a compiler-based prediction scheme that provides hints for both prefetch and replacement decisions. This prediction scheme used in DHIP enables a class of regular matrix applications to improve performance substantially, reaching up to 270% speedup over an existing prefetching scheme, for the applications and the system configurations studied. Taken together, these contributions deepen understanding of prefetching behavior, and advance the state of knowledge towards the central goal of practicality of largescale predictive prefetching in real I/O systems.