面向链式数据结构的间隔预取策略

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (24): 57-61.

面向链式数据结构的间隔预取策略

朱会东1，段赵磊1，黄艳1，2

1.郑州轻工业学院计算机与通信工程学院，郑州 450002
2.北京理工大学计算机学院，北京 100081

出版日期:2012-08-21 发布日期:2012-08-21

Skip threaded prefetching method for linked data structures

ZHU Huidong1, DUAN Zhaolei1, HUANG Yan1，2

1.School of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China
2. School of Computer, Beijing Institute of Technology, Beijing 100081, China

Online:2012-08-21 Published:2012-08-21

摘要/Abstract

摘要： 由于链式数据结构的存储缺乏空间局部性，导致程序执行过程中对链式数据的访问会发生严重的Cache缺失行为。通过对面向链式结构的线程预取性能分析，研究链式数据结构程序热点循环的计算任务量与访存任务量比例特征对线程预取性能的影响。结合多核处理器平台特点，实现了一种适用于链式数据结构的帮助线程间隔预取方法。实验结果进一步验证了计算任务量与访存任务量比例特征对间隔预取性能的影响，表明间隔预取相比于传统线程预取技术有明显的性能优势。

关键词: 链式数据结构, 片上多处理系统, 帮助线程, 数据预取

Abstract: Applications with Linked Data Structures（LDS） usually suffer heavy last level Cache misses due to the lack of spatial locality. By analyzing the relationship between computation task and memory access task in hot loop, this paper investigates the impact of operation characteristic on the performance of threaded prefetching technique. Combining the features of CMP, this paper has implemented a staggered threaded prefetching technique for applications with LDS. The experiment results prove that the ratio of computation task and memory access task actually gives rise to significant effects on staggered threaded prefetching, and staggered threaded prefetching always outperforms conventional threaded prefetching techniques.

Key words: linked data structures, Chip Multiprocessors（CMP）, helper thread, data prefetching

朱会东1，段赵磊1，黄艳1，2. 面向链式数据结构的间隔预取策略[J]. 计算机工程与应用, 2012, 48(24): 57-61.

ZHU Huidong1, DUAN Zhaolei1, HUANG Yan1，2. Skip threaded prefetching method for linked data structures[J]. Computer Engineering and Applications, 2012, 48(24): 57-61.

[1]	杨莹，李雪，杨蕊. 矩形二叉树实现海量地形数据组织与管理[J]. 计算机工程与应用, 2009, 45(20): 169-172.
[2]	朱鸿宇,刘瑰,唐福华,陈左宁. 一种自适应的数据预取与缓冲算法 [J]. 计算机工程与应用, 2006, 42(24期): 13-.