Dependance Based Prefetching for Linked Data Structures
Dependance Based Prefetching for Linked Data Structures
复制标题
链接数据结构的基于依赖性的预取
DOI：
10.1145/384265.291034
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
G. Sohi
中科院分区：
文献类型：
--
作者：
A. Roth;A. Moshovos;G. Sohi
我们引入了一个动态的计划，捕获的accesspat-pickup的链接数据结构，并可用于预测未来的访问具有很高的精度。我们的技术利用了产生地址的负载和消耗这些地址的负载之间存在的依赖关系。通过识别生产者-消费者对，我们为关联结构及其遍历构造了一个紧凑的内部表示。为了实现预取效果，小型预取引擎在执行程序之前推测性地遍历该表示。基于依赖的预取在一套指针密集型程序上实现了高达25%的加速。
We introduce a dynamic scheme that captures the accesspat-terns of linked data structures and can be used to predict future accesses with high accuracy. Our technique exploits the dependence relationships that exist between loads that produce addresses and loads that consume these addresses. By identzj+ing producer-consumer pairs, we construct a compact internal representation for the associated structure and its traversal. To achieve a prefetching eflect, a small prefetch engine speculatively traverses this representation ahead of the executing program. Dependence-based prefetching achieves speedups of up to 25% on a suite of pointer-intensive programs.