| Memory latency is currently one of the largest limitations for high-performance computers. Memory prefetching attempts to reduce the memory latency by moving data from memory closer to the processor. Different prefetching mechanisms tend to model memory access patterns. For example, a stride prefetcher assumes that programs will access memory in a linear pattern. In applications that utilize a large number of dynamically allocated objects, the memory access patterns can become irregular, and difficult to model.; This dissertation proposes Content-Sensitive Data Prefetching , a novel method of data prefetching that attempts to overcome the problems introduced by the irregular memory access patterns seen in pointer-intensive applications, thus allowing prefetches of pointer-chasing references. Content-sensitive prefetching works by examining the content of data as it is moved from the memory to the caches. Data values that are likely to be addresses are then translated and prefetch requests are issued for the candidate addresses. Content-sensitive data prefetching has the capability to prefetch sparse data structures, including graphs, lists and trees. This scheme is hardware-only and it requires no additional structures beyond the requirements for a traditional stride-based hardware prefetcher.; A cycle-accurate simulator that includes both an out-of-order processor model and a detailed memory model is used to validate the effectiveness of the content-sensitive prefetcher from both a functional and a performance perspective. It will be shown that given the proper address prediction heuristic, both accurate and timely prefetches can be initiated in the context of pointer-intensive applications. |
