A prefetching technique for irregular accesses to linked data structures

Publisher Website
Google Scholar
Abstract
Prefetching offers the potential to improve the perfor-mance of linked data structure (LDS) traversals. How-ever, previously proposed prefetching methods only work well when there is enough work processing a node that the prefetch latency can be hidden, or when the LDS is long enough and the traversal path is known a priori. This pa-per presents a prefetching technique called prefetch arrays which can prefetch both short LDS, as the lists found in hash tables, and trees when the traversal path is not known a pri-ori. We offer two implementations, one software-only and one which combines software annotations with a prefetch engine in hardware. On a pointer-intensive benchmark suite, we show that our implementations reduce the mem-ory stall time by 23% to 51% for the kernels with linked lists, while the other prefetching methods cause reductions that are substantially less. For binary-trees, our hardware method manages to cut nearly 60% of the memory stall time even when the traversal path is not known a priori. However, when the branching factor of the tree is too high, our technique does not improve performance. Another con-tribution of the paper is that we quantify pointer-chasing found in interesting applications such as OLTP, Expert Sys-tems, DSS, and JAVA codes and discuss which prefetching techniques are relevant to use in each case.

This publication has 11 references indexed in Scilit: