Compiler-based prefetching for recursive data structures
Authors:
Open Access
- 1 September 1996
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 30 (5) , 222-233
Abstract
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 considerable success in array-based numeric codes, its potential in pointer-based applications has remained largely unexplored. This paper investigates compiler-based prefetching for pointer-based applications---in particular, those containing recursive data structures. We identify the fundamental problem in prefetching pointer-based data structures and propose 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 research compiler, and we evaluate the performance of all three schemes on a modern superscalar processor similar to the MIPS R10000. Our results demonstrate that compiler-inserted prefetching can significantly improve the execution speed of pointer-based codes---as much as 45% for the applications we study. In addition, the more sophisticated algorithms (which we currently perform by hand, but which might be implemented in future compilers) can improve performance by as much as twofold. Compared with the only other compiler-based pointer prefetching scheme in the literature, our algorithms offer substantially better performance by avoiding unnecessary overhead and hiding more latency.Keywords
This publication has 15 references indexed in Scilit:
- Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C1996
- Interleaving1994
- Compiler optimizations for improving data locality1994
- A general data dependence test for dynamic, pointer-based data structures1994
- Context-sensitive interprocedural points-to analysis in the presence of function pointers1994
- Interprocedural modification side effect analysis with pointer aliasing1993
- Sharlit---a tool for building optimizers1992
- An effective on-chip preloading scheme to reduce data access penalty1991
- A data locality optimizing algorithm1991
- APRIL1990