首页|Blocking optimized SIMD tree search on modern processors

Blocking optimized SIMD tree search on modern processors

扫码查看
原文链接
  • NETL
  • NSTL
  • 万方数据
  • 维普
Tree search is a widely used fundamental algorithm.Modern processors provide tremendous computing power by integrating multiple cores,each with a vector processing unit.This paper reviews some studies on exploiting single instruction multiple date(SIMD)capacity of processors to improve the performance of tree search,and proposes several improvement methods on reported SIMD tree search algorithms.Based on blocking tree structure,blocking for memory alignment and dynamic blocking prefetch are proposed to optimize the overhead of memory access.Furthermore,as a way of non-linear loop unrolling,the search branch unwinding shows that the number of branches can exceed the data width of SIMD instructions in the SIMD search algorithm.The experiments suggest that blocking optimized SIMD tree search algorithm can achieve 1.6 times response speed faster than the un-optimized algorithm.

single instruction multiple date(SIMD)tree searchbinary searchstreaming SIMD extensions(SSE)Cell broadband engine(BE)

ZHANG Zhuo、LU Yu-fan、SHEN Wen-feng、XU Wei-min、ZHENG Yan-heng

展开 >

School of Computer Engineering and Science, Shanghai University, Shanghai 200072, P.R.China

Shanghai Leading Academic Discipline ProjectGraduate Student Innovation Foundation of Shanghai University

J50103SHUCX112167

2011

10.1007/s11741-011-0765-2

上海大学学报(英文版)
上海大学

上海大学学报(英文版)

影响因子：0.196
ISSN：1007-6417
年,卷(期)：2011.15(5)
  • 2
  • 1