Prefetching by self-contained variables - a generalization from array to recursive data structures

Abstract

Data prefetching has been proven to be effective in hiding the memory latency from the program execution time. Most current data prefetching schemes target only for array references with constant strides. For array references with non-constant strides, they lose most of their effectiveness. In this paper, we propose a novel data prefetching scheme based on a property, called the Self-Containness of Variables, which is widely available in most loop-rich applications. We observed that the update pattern of a self-contained variable in a loop can be accurately predicted. The predicated value can then be used for accurate data prefetching if the variable is the only loop-variant component of an address expression in a memory access instruction. With suitable hardware support, this scheme can be used to prefetch data from recursive data structures in additional to array elements. Moreover, the coverage of this scheme is highly selectable. It can be customized easily to fit the cost-performance requirements of different processors that are designed for different applications.