基于SSE指令集的串匹配算法优化（.docx

基于SSE指令集的串匹配算法优化基金项目:国家973计划重点基础研究项目(2007CB311100);国家242信息安全计划项目((242)2009A43)
邵妍1,2,4, 刘燕兵1,3,4, 刘萍1,4,郭莉1,4
(1. 中国科学院计算技术研究所,北京 100190;2. 北京邮电大学,北京 100876;
3. 中国科学院研究生院,北京 100039;信息内容安全技术国家工程实验室,北京 100190);
摘要:串匹配是计算机研究领域的经典问题之一,在网络安全、计算生物学、信息检索等领域发挥着关键的作用。其中,基于位并行的串匹配算法所需存储空间小、匹配速度快,但由于受到机器字的限制,只适合小规模的串匹配。基于SSE系列指令集对经典的位并行算法Shift-And、BNDM进行了优化,优化算法利用SSE指令集提供的128位大位宽寄存器,将多个状态向量打包到SSE寄存器上,并通过SSE的位操作指令状态向量进行更新。在随机数据和真实数据上的测试结果显示,优化算法的匹配速度达到原算法的2倍以上。
关键词:串匹配算法;位并行;SSE指令集;Shift-And;BNDM
中图分类号:TP302 文献标识码:A 文章编号:
Optimizing String Matching Algorithms by Using SSE Instructions
SHAO Yan1,2,4, LIU Yan-bing1,3,4, LIU Ping1,4, GUO Li1,4
(1. Institute puting Technology Chinese Academy of Sciences, Beijing 100190, China;
2. Beijing University of Posts and munications, Beijing, 100876, China;
3. Graduate University of Chinese Academy of Sciences, Beijing 100039, China;
3. National Engineering Laboratory for Information Security Technologies, Beijing 100190, China)
Abstract: String matching is a classic research area puter science and plays an important role in various kind of fields, such as information security, computational biology, information retrial, etc. Bit-parallel string matching algorithms require less memory space and match patterns at a high speed. However, limited by the machine word, they are only suitable for small-scale string matching. We optimized the classic Shift-And algorithm and BNDM algorithm by using SSE instructions. We packed several bit-vectors into the 128-bit registers provided by SSE instruction set, and updated bit-vectors by using SSE instructions. We tested the optimized algorithms on random data set as well as real data set, and the results indicated that the matching speeds of the optimized algorithms were accelerated to at least twice as much as the original algorithms’.
Key words: string matching algorithms; bit parallel; SSE instruction set; Shift-And; BNDM
引言
精确串匹配(后面简称“串匹配”)问题是计算机科学研究领域的一个经典问题。它指在文本T=t1t2…tn中找出某个给定的模式串集合