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

Efficient String Matching Algorithm for DSP Processor

作　　者：叶鸿[1] 顾乃杰[1] 林传文 YE Hong;GU Nai-jie;LIN Chuan-wen(School of Computer Science and Technology,University of Science and Technology of China,Hefei 230027,China;Department of Computer Science and Technology,Hefei University,Hefei 230601,China)

机构地区：[1]中国科学技术大学计算机科学与技术学院,合肥230027 [2]合肥学院计算机科学与技术系,合肥230601

出　　处：《小型微型计算机系统》2021年第4期847-852,共6页Journal of Chinese Computer Systems

基　　金：安徽省科技重大专项项目(18030901011)资助;合肥学院科研发展基金项目(19ZR03ZDA)资助。

摘　　要：字符串匹配是生物识别、入侵检测的基础,也是大数据互联网时代的研究热点.随着现代信息技术的发展,日常工作生活中移动及手持小型化设备的使用越发普遍.这些设备的应用场景中包含大量有关串匹配的需求,如人脸识别、实时数据查询等.串匹配算法的实时和准确性决定了使用场景的范围,因此在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.

关 键 词：DSP 串匹配 VLIW SIMD 位并行 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]