Automatic Prefetching of Induction Pointers
for Software Pipelining
Artour Stoutchinin, José Nelson Amaral, Guang R. Gao,
Jim Dehnert, Suneel Jain
We present an automatic approach to prefetch data for linked list data
structures. The main idea is based on the observation that code
operating on linked lists frequently generates a regular pattern of
memory references. For example, in a loop that traverses a linked
list, the effective addresses of the list elements accessed from one
iteration to another may be x, x+40, x+80, .... This
regularity in the memory footprint of linked lists inspired us to
develop a prefetching approach where the address of the element
accessed in one of the future iterations of the loop is speculatively
predicted based on its previous regular behavior.
The main contributions of this paper include:
\begin{enumerate}
- Automatic identification of pointer-chasing recurrences in
loops that access linked lists. This identification can be
achieved by a surprisingly simple method: simply looking for
induction pointers --- pointers that are updated in each
loop iteration by a load with a constant offset.
- Integration of induction pointer prefetching with
loop scheduling. Key intuition in our
framework is to insert prefetches only if there are extra
processor resources and memory bandwidth available. In order to
achieve that we estimate the number of potential cache misses
in one loop iteration. Our algorithm is based on an application
of graph coloring on a memory access interference graph derived
from a control flow graph.
- An implementation of the proposed scheme in an industry-strength
production compiler. We have performed experiments on seven benchmark
programs with linked lists and observed considerable performance
improvements in three of them.
Return to José
Nelson Amaral's Publications
Send comments to: amaral AT cs DOT ualberta DOC ca
Return to Amaral's home
page