基于单指令级并行的快速求交算法  

Efficient multiple sets intersection using SIMD instructions

作　　者：宋省身[1] 杨岳湘[1] 江宇[2] SONG Xing-shen1, YANG Yue-xiang1, JIANG Yu2(1. College of Computer, National University of Defense Technology, Changsha 410000, Hunan, China; 2. Northwest Institute of Nuclear Technology, Xi＇an 710024, Shaanxi, Chin)

机构地区：[1]国防科学技术大学计算机学院,湖南长沙410000 [2]西北核技术研究所,陕西西安710024

出　　处：《山东大学学报（理学版）》2018年第3期54-62,共9页Journal of Shandong University(Natural Science)

基　　金：湖南省自然科学基金资助项目(2016JJ2007)

摘　　要：布尔查询中的求交操作被广泛应用于各种信息系统中,是进行文档检索的基本操作之一。其基本形式可以视作多个有序整数序列的交集问题,而提高求交运算的效率是当前研究的重点。在传统求交算法的基础上,利用单指令多数据流(single instruction multiple data,SIMD)并行指令集,针对其核心的搜索步骤,提出了两种基于SIMD的跳跃式搜索算法。该算法在提高性能的同时,能有效适配在传统多倒排链求交算法中。实验证明,优化后的算法相比未使用SIMD的情况下有了很大的提升,甚至优于SIMD优化后的两两相交算法,性能最高提升37.3%。Conjunctive Boolean query is one fundamental operation for document retrieval and widely used in many information systems and databases. In its most basic and popular form,a conjunctive query can be seen as the intersection problem of multiple sets of sorted integers,and howto improve its efficiency is becoming one important research highlight. Based on the traditional intersection algorithms,this paper proposes two optimizations on the essential searching algorithms using SIMD instructions. The optimized search algorithms are able to be adopted into various multiple sets intersection methods while improving intersection efficiency. Experiments showthat the optimized algorithms performs much better than the traditional ones,even outperform the recent SIMD intersection algorithms,and the improvement is up to 37. 3% at most.

关 键 词：求交算法 倒排索引 性能评价 并行处理 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]