Effective jump-pointer prefetching for linked data structures
Effective jump-pointer prefetching for linked data structures
复制标题
DOI：
10.1109/isca.1999.765944
复制
发表时间：
1999-05
期刊：
影响因子：
--
通讯作者：
A. Roth;G. Sohi
中科院分区：
文献类型：
--
作者：
A. Roth;G. Sohi
用于预取链接数据结构（LDS）的当前技术利用在一个循环迭代或递归调用中可用的工作来重叠指针追踪延迟。跳转指针提供了对非相邻节点的直接访问，当循环和递归过程体很小并且没有足够的工作来重叠长的延迟时，跳转指针可以用于预取。本文描述了一个跳转指针预取（JPP）的框架，支持四个预取习惯用法：队列，完整，链，根跳转和三个实现：纯软件，纯硬件，和一个合作的软件/硬件技术。在一套指针密集型程序，跳转指针预取减少了72%的软件，83%的合作和55%的硬件，产生15%，20%和22%的加速比的内存停滞时间。
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.