Speculative Prefetching of Induction Pointers
| Autor: | José Nelson Amaral, Guang R. Gao, Alban Douillet, Artour Stoutchinin, James C. Dehnert, Suneel Jain |
|---|---|
| Rok vydání: | 2001 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783540418610 CC |
| DOI: | 10.1007/3-540-45306-7_20 |
| Popis: | We present an automatic approach for prefetching data for linked list data structures. The main idea is based on the observation that linked list elements are frequently allocated at constant distance from one another in the heap. When linked lists are traversed, a regular pattern of memory accesses with constant stride emerges. This regularity in the memory footprint of linked lists enables the development of a prefetching framework where the address of the element accessed in one of the future iterations of the loop is dynamically predicted based on its previous regular behavior. We automatically identify pointer-chasing recurrences in loops that access linked lists. This identification uses a surprisingly simple method that looks for induction pointers -- pointers that are updated in each loop iteration by a load with a constant offset. We integrate induction pointer prefetching with loop scheduling. A key intuition incorporated in our framework is to insert prefetches only if there are processor resources and memory bandwidth available. In order to estimate available memory bandwidth we calculate the number of potential cache misses in one loop iteration. Our estimation algorithm is based on an application of graph coloring on a memory access interference graph derived from the control flow graph. We implemented the prefetching framework in an industry-strength production compiler, and performed experiments on ten benchmark programs with linked lists. We observed performance improvements between 15% and 35% in three of them. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|