COMPILER-BASED PREFETCHING FOR RECURSIVE DATA-STRUCTURES

Software-controlled data prefetching offers the potential for bridging the ever-increasing speed gap between the memory subsystem and today' s high-performance processors. While prefetching has enjoyed considera ble success in array-based numeric codes, its potential in pointer-bas ed applications has remained largely unexplored. This paper investigat es compiler-based prefetching for pointer-based applications - in part icular, those containing recursive data structures. We identify the fu ndamental problem in prefetching pointer-based data structures and pro pose a guideline for devising successful prefetching schemes. Based on this guideline, we design three prefetching schemes, we automate the most widely applicable scheme (greedy prefetching) in an optimizing re search compiler; and we evaluate the performance of all three schemes on a modern superscalar processor similar to the MIPS R10000. Our resu lts demonstrate that compiler-inserted prefetching can significantly i mprove the execution speed of pointer-based codes - as much as 45% for the applications we study. In addition, the more sophisticated algori thms (which we currently perform by hand, but which might be implement ed in future compilers) can improve performance by as much as twofold. Compared with the only other compiler-based pointer prefetching schem e in the literature, our algorithms offer substantially better perform ance by avoiding unnecessary overhead and hiding more latency.