一种基于魂芯DSP的单模式位并行串匹配算法  

A SINGLE MODE BIT-PARALLEL STRING MATCHING ALGORITHM BASED ON HXDSP

作　　者：陈瑞 顾乃杰[1,2] 叶鸿[1,2] Chen Rui;Gu Naijie;Ye Hong(School of Computer Science and Technology,University of Science and Technology of China,Hefei 230027,Anhui,China;Anhui Key Laboratory of Computing and Communication Software,University of Science and Technology of China,Hefei 230027,Anhui,China)

机构地区：[1]中国科学技术大学计算机科学与技术学院,安徽合肥230027 [2]中国科学技术大学安徽省计算与通信软件重点实验室,安徽合肥230027

出　　处：《计算机应用与软件》2020年第7期246-252,共7页Computer Applications and Software

摘　　要：在多媒体技术飞速发展的今天,DSP处理器以其低功耗和高性能等特点在信号处理和图像检索领域有着重要的应用。串匹配作为信号处理和图像检索应用中的基本算法,其性能和效率也因此受到越来越多的关注。通过结合DSP处理器的分簇结构和零开销循环技术,并利用字符串分段的方法提出一种基于DSP的位并行串匹配算法EPSO。该算法可有效减少条件分支语句的时钟开销和分簇执行过程中的漏配次数,加速了串匹配过程。在国产魂芯DSP的仿真结果表明:EPSO算法的匹配速度是经典Shift-Or算法的7.8倍左右,串匹配效率得到有效提升;以KMP算法为基准,英文语料下该算法的平均匹配速度是KMP算法的6.3倍左右,DNA序列下是KMP算法的10.5倍左右,相比NEW、S2BNDM算法均具有显著的性能提升。As the rapid development of multimedia technology,DSP processors have important applications in signal processing and image retrieval with their low power consumption and high performance.String matching,the basic algorithm in signal processing and image retrieval applications,is gaining more and more attention to its performance and efficiency.Based on DSP,we propose a bit parallel string matching algorithm called EPSO by combining the clustering structure of DSP and zero-overhead loop technology and using string segmentation.It can effectively reduce the clock overhead of conditional branch statements and the missing allocation problem in the clustering process,and accelerate the string matching process.The experimental results of the algorithm in HXDSP emulator show that the matching speed of EPSO algorithm is about 7.8 times that of the classical Shift-Or algorithm,and the string matching efficiency is significantly improved.Based on KMP algorithm,the average matching speed of the algorithm in English text is about 6.3 times that of KMP algorithm.The DNA sequence is about 10.5 times that of KMP algorithm,which has significant performance improvement compared to NEW and S2BNDM algorithms.

关 键 词：串匹配 移位或算法 魂芯DSP 分簇 位并行 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]