高速缓存优化的并行连接算法  

Cache optimized parallel join algorithm

作　　者：胡泽林[1,2,3] 张云泉[1,2] 

机构地区：[1]中国科学院软件研究所计算机科学国家重点实验室,北京100190 [2]中国科学院软件研究所并行计算实验室,北京100190 [3]中国科学院研究生院信息学院,北京100049

出　　处：《计算机工程与设计》2009年第20期4581-4584,共4页Computer Engineering and Design

基　　金：国家自然科学基金项目(60303020);国家自然基金重点项目(60533020);国家973重点基础研究发展计划基金项目(2005CB321702);国家863高技术研究发展计划基金项目(2006AA01A102;2006AA01A125)

摘　　要：由于嵌套循环连接操作过程中存在较大的高速缓存缺失,严重影响了连接查询的性能。提出了一种基于缓冲的高速缓存参数无关的嵌套循环并行连接算法。通过高速缓存参数无关和缓冲技术,提高了连接算法的空间局部性和时间局部性。理论分析和实验结果表明,高速缓存优化后的串行连接算法的性能是原来的2倍,其并行算法效果近似线性加速比。Tremendous cache miss exists in nested-loop join query processing, which dramatically degrades the performance of join query processing. Through cache oblivious and buffering technique, the spatial locality and temporal locality of join algorithm are improved. A buffering based cache-oblivious nest-loop parallel join algorithm is proposed. The analysis and experiment demonstrate that one more performance is gained by the optimized sequential algorithm, and the parallel algorithm gets the near linear speedup.

关 键 词：存储层次 理想高速缓存模型 高速缓存参数无关 高度划分聚类 缓冲 并行化 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]