Effective jump-pointer prefetching for linked data structures
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 111-121
- https://doi.org/10.1109/isca.1999.765944
Abstract
Current techniques for prefetching linked data structures (LDS) exploit the work available in one loop iteration or recursive call to overlap pointer chasing latency. Jump-pointers, which provide direct access to non-adjacent nodes, can be used for prefetching when loop and recursive procedure bodies are small and do not have sufficient work to overlap a long latency. This paper describes a framework for jump-pointer prefetching (JPP) that supports four prefetching idioms: queue, full, chain, and root jumping and three implementations: software-only, hardware-only, and a cooperative software/hardware technique. On a suite of pointer intensive programs, jump-pointer prefetching reduces memory stall time by 72% for software, 83% for cooperative and 55% for hardware, producing speedups of 15%, 20% and 22% respectively.Keywords
This publication has 12 references indexed in Scilit:
- Exploiting dead value informationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Cache-conscious structure layoutPublished by Association for Computing Machinery (ACM) ,1999
- Segregating heap objects by reference behavior and lifetimePublished by Association for Computing Machinery (ACM) ,1998
- Using generational garbage collection to implement cache-conscious data placementPublished by Association for Computing Machinery (ACM) ,1998
- Dependence based prefetching for linked data structuresPublished by Association for Computing Machinery (ACM) ,1998
- Compiler-based prefetching for recursive data structuresPublished by Association for Computing Machinery (ACM) ,1996
- SPAID: software prefetching in pointer- and call-intensive environmentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1995
- Supporting dynamic data structures on distributed-memory machinesACM Transactions on Programming Languages and Systems, 1995
- Skip lists: a probabilistic alternative to balanced treesCommunications of the ACM, 1990
- A nonrecursive list compacting algorithmCommunications of the ACM, 1970