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}

Return to José Nelson Amaral's Publications

Send comments to: amaral AT cs DOT ualberta DOC ca

Return to Amaral's home page