Correlation-based hardware prefetching

Abstract

Correlation-based prefetching is a technique to observe and record spatial links between temporal events and address references in a processor with the goal of predicting what data will be needed by the processor. The main contribution of this dissertation is that correlation-based prefetching is shown to be an effective technique for prefetching data into a data cache, by observing the cache-miss traffic. This thesis examines the issues that are critical to the performance of correlation-based prefetching. First, intrinsic qualities of test programs are studied which indicate the potential for using correlations for prefetching. Metrics of linked and strided spatial locality indicate the potential of correlation-based prefetching. Hardware prefetching works because there often exists predictable patterns in the references of programs. Hardware correlation-based prefetching seeks to allow prefetching in the situations not easily handled by compilers or characterized by simple stride patterns. It is shown to be very efficient in such cases. Correlation-based prefetching is a complementary technique to compiler-controlled prefetching or stride-based prefetching done in hardware. Specifically, this thesis examines mechanisms for construction of temporal events that are used as triggers for prefetching. These temporal events should be good indicators of the context of a program. A flexible mechanism for pairing temporal events with addresses, called the horizon and skip model, is shown to be useful for increasing the accuracy of prefetching for some applications. Confirmation mechanisms are studied. They allow for a tradeoff between the coverage of memory accesses predicted and accuracy of prefetching. An important issue in prefetching is where to store the accumulated prefetching meta-data. We examine the effects of varying the capacity of a table used to store this meta-data as well as a novel mechanism for storing the meta-data in a large, pre-existing secondary cache. We examine an alternative approach involving a hybrid prefetcher that combines a stride and pure correlation-based prefetcher. The hybrid mechanism is shown to dramatically reduce the pair storage requirements of correlation-based prefetching.