高效KD树并行算法优化  

Parallelization Optimization of KD-Tree Building Algorithm

作　　者：李天驹 张铮[4] 张为华 

机构地区：[1]复旦大学软件学院,上海201203 [2]上海市数据科学重点实验室(复旦大学),上海201203 [3]复旦大学并行处理研究所,上海201203 [4]解放军信息工程大学数学工程与先进计算国家重点实验室,郑州450001

出　　处：《计算机系统应用》2015年第8期1-9,共9页Computer Systems & Applications

基　　金：上海市科委科技攻关项目(13DZ1108800);国家高技术研究发展计划(863)(2012AA010901);国家自然科学基金(61370081)

摘　　要：KD树作为一种用于查询高维键值的流行算法,由于其准确性高、可扩展性强与较快的查询速度而应用于多媒体检索领域,但缓慢的建树效率已不能很好的满足当前的应用场景.针对KD树的低效建树过程,作者探寻并分析了KD树建树现存的并行潜能并提出了一种面向KD树建树过程的多核并行算法—Par K(Parallel KD-Tree).Par K探求了不同的并行模式来充分利用现代硬件中的计算资源,并在此基础上提出了一种新的内存分配策略来解决并行处理中的数据争用状况.实验结果表明Park相比于原始串行版本最高能够在16核的服务器上达到21.75倍的加速.In recent years, multimedia data has become one of the major data types transferred and processed on the Internet. K dimensional tree is one of the most popular tree structures for searches involving a multidimensional search key, which is similar to feature points extracted from multimedia data, due to its good accuracy, scalability and fast retrieval speed. However, its slow building speed limits its application area, especially with large dataset. Fortunately, Modern processors provide tremendous computing power by integrating multiple or many cores. In this paper, we explore and analyze the existing potential parallel in KD-Tree building process. Then we present Par K, a customized parallel solution that exploits multi-core CPUs to accelerate KD-Tree building process. Par K exploits different parallel models to fully utilize computation resource in modern hardware and solves data race by presenting a new memory allocation strategy. The final experimental results show Par K achieves about 21.75 X speedup compared to original serial version on 16-core server.

关 键 词：多媒体检索 KD树 多核 并行 

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