资源描述：
《基于sse指令集的串匹配算法优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、基于SSE指令集的串匹配算法优化基金项目：国家973计划重点基础研究项目（2007CB311100）；国家242信息安全计划项目（（242）2009A43）邵妍1,2,4,刘燕兵1,3,4,刘萍1,4,郭莉1,4（1.中国科学院计算技术研究所，北京100190；2.北京邮电大学，北京100876；3.中国科学院研究生院，北京100039；信息内容安全技术国家工程实验室，北京100190）；摘要：串匹配是计算机研究领域的经典问题之一，在网络安全、计算生物学、信息检索等领域发挥着关键的作用。其中，基于位并行的串匹配算法所需存储空间小、匹配速度快，但由于受
2、到机器字的限制，只适合小规模的串匹配。基于SSE系列指令集对经典的位并行算法Shift-And、BNDM进行了优化，优化算法利用SSE指令集提供的128位大位宽寄存器，将多个状态向量打包到SSE寄存器上，并通过SSE的位操作指令状态向量进行更新。在随机数据和真实数据上的测试结果显示，优化算法的匹配速度达到原算法的2倍以上。关键词：串匹配算法；位并行；SSE指令集；Shift-And；BNDM中图分类号：TP302文献标识码：A文章编号：OptimizingStringMatchingAlgorithmsbyUsingSSEInstructionsSH
3、AOYan1,2,4,LIUYan-bing1,3,4,LIUPing1,4,GUOLi1,4(1.InstituteofComputingTechnologyChineseAcademyofSciences,Beijing100190,China;2.BeijingUniversityofPostsandTelecommunications,Beijing,100876,China;3.GraduateUniversityofChineseAcademyofSciences,Beijing100039,China;3.NationalEnginee
4、ringLaboratoryforInformationSecurityTechnologies,Beijing100190,China)Abstract:Stringmatchingisaclassicresearchareaincomputerscienceandplaysanimportantroleinvariouskindoffields,suchasinformationsecurity,computationalbiology,informationretrial,etc.Bit-parallelstringmatchingalgori
5、thmsrequirelessmemoryspaceandmatchpatternsatahighspeed.However,limitedbythemachineword,theyareonlysuitableforsmall-scalestringmatching.WeoptimizedtheclassicShift-AndalgorithmandBNDMalgorithmbyusingSSEinstructions.Wepackedseveralbit-vectorsintothe128-bitregistersprovidedbySSEins
6、tructionset,andupdatedbit-vectorsbyusingSSEinstructions.Wetestedtheoptimizedalgorithmsonrandomdatasetaswellasrealdataset,andtheresultsindicatedthatthematchingspeedsoftheoptimizedalgorithmswereacceleratedtoatleasttwiceasmuchastheoriginalalgorithms’.Keywords:stringmatchingalgorit
7、hms;bitparallel;SSEinstructionset;Shift-And;BNDM1引言精确串匹配（后面简称“串匹配”）问题是计算机科学研究领域的一个经典问题。它指在文本T=t1t2…tn中找出某个给定的模式串集合P={p1,p2,…,pr}的所有出现位置，其中T和pi(1≤i≤r)是在有限字符表∑上的字符序列。串匹配技术广泛应用于网络信息安全领域，典型的应用包括：入侵检测/防御系统（IDS/IPS）、反病毒和反垃圾邮件检测（AV/AS）、网络带宽管理和服务质量（QoS）、统一威胁管理（UTM）等。近年来，随着宽带技术的发展和多媒体应用
8、的广泛流行，互联网技术得到极大的普及和发展。由于互联网协议和计算机系统的漏洞，网络安全形势日趋严峻。传统的网
