DSP处理器上的高效串匹配实现

Efficient String Matching Algorithm for DSP Processor

字符串匹配是生物识别、入侵检测的基础,也是大数据互联网时代的研究热点.随着现代信息技术的发展,日常工作生活中移动及手持小型化设备的使用越发普遍.这些设备的应用场景中包含大量有关串匹配的需求,如人脸识别、实时数据查询等.串匹配算法的实时和准确性决定了使用场景的范围,因此在DSP处理器等移动小型化设备的嵌入式处理器上实现高效串匹配算法的问题变得十分迫切.该文针对DSP处理器因缺乏逻辑判断与跳转指令,难以支持高效串匹配运算的问题,提出了一种基于DSP平台特点的改进串匹配算法.该算法采用位并行的思路,在DSP处理器上实现了串匹配算法的并行化.同时通过前序启动、基于VLIW的数学运算替代逻辑判断、Q-grams等优化手段,提高该算法对于DSP平台的适应性与执行效率,最终实现了一种基于HXDSP的高效串匹配算法VBNDM2.实验结果表明,本算法针对DSP平台,有效地提高了串匹配的效率,实现了算法的高效并行化.

String matching is the basis of biometrics and intrusion detection,and it is also a research hotspot in the era of big data Internet.With the development of modern information technology,the use of mobile and handheld miniaturized devices in daily work and life is becoming more common.The application scenarios of these devices include a large number of requirements related to string matching,such as face recognition and real-time data query.The real-time and accuracy of the string matching algorithm determines the range of use scenarios,so the problem of implementing an efficient string matching algorithm on an embedded processor of a mobile miniaturized device such as a DSP processor becomes very urgent.Aiming at the problem that DSP processors lack support for efficient string matching operations due to lack of logical judgment and jump instructions,this paper proposes an improved string matching algorithm based on the characteristics of the DSP platform.This algorithm adopts the idea of bit parallelism,and realizes the parallelization of the string matching algorithm on the DSP processor.At the same time,through the pre-launch,VLIW-based mathematical operations instead of logical judgments,Q-grams and other optimization methods,the algorithm’s adaptability and execution efficiency for the DSP platform are improved.Finally,an efficient string matching algorithm VBNDM2 based on HXDSP is implemented.Experimental results show that this algorithm is aimed at the DSP platform,which effectively improves the efficiency of string matching and achieves efficient parallelization of the algorithm.