一种计算存储设备中的字符串并行匹配算法

来源：计算机技术与发展杂志2025年第08期北京时间：

作者：张东阳;刘东石;苏?攀;*;马玉梅;王其乐

单位：1. 华北电力大学 控制与计算机工程学院,河北 保定 071003;2. 河北省能源电力知识计算重点实验室,河北 保定 071000;3. 复杂能源系统智能计算教育部工程研究中心,河北 保定 071000;4. 中能电力科技开发有限公司,北京 100034

摘要：传统的字符串匹配算法在遭遇最不利情况时时间消耗显著攀升,成为性能瓶颈,此外还往往伴随大量数据的频繁迁移与操作,当面临数据密集型应用和输入输出(IO)性能限制时,其局限性愈发凸显。针对传统字符串匹配解决方案中的数据移动量大、最差情况下的性能瓶颈等问题,提出了基于计算存储设备(Computational Storage Device,CSD)的解决方法。该方法通过在存储器内部部署嵌入式处理引擎,将计算移动到存储端,大幅减少了数据在处理单元和存储单元之间的传输,从而显著提升了整体计算效率。将现场可编程门阵列(Field Programmable Gate Array,FPGA)作为CSD嵌入式处理引擎,利用其并行处理能力,设计了一种高效的精确字符串并行匹配算法。在FPGA读取数据的同时,完成字符串匹配工作,消除了字符串匹配过程中的额外时间开销。实验结果表明,基于CSD的解决方法展现出了显著的性能优势,为大数据环境下的字符串匹配问题提供了一种新的解决方案。

关键词：字符串匹配;计算存储设备;现场可编程门阵列;并行;算法