ßFA：一种基于向量指令集的高性能数据处理算法
电子技术应用
杨嘉佳，关健，李正，于增明，姚旺君
中国电子信息产业集团有限公司第六研究所
摘要： 正则表达式匹配技术在数据清洗、解析提取等数据处理任务方面发挥重大作用。然而，由于匹配过程中存在数据强依赖关系和内存访问不可预测等问题，造成匹配性能较低。针对此问题，提出一种基于向量指令集的高性能正则表达式数据处理算法，称之为ßFA：通过向量指令一次性从内存读出若干连续字符，并与最常被访问状态对应的非信任字符集进行向量匹配，利用内置函数定位首个非信任字符的位置，获得可直接跳过的字符数，从而实现匹配性能的加速。实验结果表明，ßFA算法的吞吐率优于原始DFA算法和αFA算法，是原始DFA算法的4.67~60倍以及ɑFA算法的4.37~7.82倍。
中圖分類號：TP391.1 文獻標志碼：A DOI: 10.16157/j.issn.0258-7998.245114
中文引用格式： 楊嘉佳，關健，李正，等. ?FA:一種基于向量指令集的高性能數據處理算法[J]. 電子技術應用，2024，50(11)：85-88.
英文引用格式： Yang Jiajia，Guan Jian，Li Zheng，et al. ?FA: a high-performance data processing algorithm based on vector instruction set[J]. Application of Electronic Technique，2024，50(11)：85-88.
中文引用格式： 楊嘉佳，關健，李正，等. ?FA:一種基于向量指令集的高性能數據處理算法[J]. 電子技術應用，2024，50(11)：85-88.
英文引用格式： Yang Jiajia，Guan Jian，Li Zheng，et al. ?FA: a high-performance data processing algorithm based on vector instruction set[J]. Application of Electronic Technique，2024，50(11)：85-88.
ßFA： a high-performance data processing algorithm based on vector instruction set
Yang Jiajia，Guan Jian，Li Zheng，Yu Zengming，Yao Wangjun
The Sixth Research Institute of China Electronics Corporation
Abstract： Regular expression matching technology plays a significant role in data processing tasks such as data cleaning, parsing, and extraction. However, due to issues such as strong data dependency and unpredictable memory access in the matching process, the matching performance is relatively low. In response to this problem, this paper proposes a high-performance regular expression data processing algorithm based on vector instruction set, which is called ßFA. By using vector instructions to read a sequence of consecutive characters at once, and performing vector matching with the non-trusted character set corresponding to the most frequently accessed state, built-in functions can be utilized to find the position of the first non-trusted character, thus obtaining the number of characters that can be skipped directly, thereby accelerating the matching performance. Experimental results show that the throughput of the ßFA algorithm is superior to the original DFA algorithm and the αFA algorithm, being 4.67~60 times faster than the original DFA algorithm and 4.37~7.82 times faster than the αFA algorithm.
Key words : regular expression matching；vector instruction set；high-performance data processing
引言
數據處理能力是大數據時代的核心要素之一，決定了真實數據環境下是否滿足數據線速處理的要求。正則表達式匹配技術可作為數據清洗、提取解析和數據檢測等數據處理任務的有效解決手段之一。例如，基于Linux系統的Awk、Vim、Perl工具以及開源網絡入侵檢測系統Bro IDS[1]等都使用了正則表達式的匹配功能。
正則表達式匹配的有效手段通常分為確定型有限自動機(Deterministic Finite Automata, DFA)和基于非確定型有限自動機(Nondeterministic Finite Automata, NFA)[2]。兩者各有其特點，NFA空間復雜性較低，但因為一次字符輸入可能會引發數目不定的多個狀態轉移，造成匹配時間復雜性較大。相反，原始DFA的時間復雜性低且為O(1)，但存在空間開銷大的問題。
在大數據處理背景下，正則表達式的匹配性能是最重要的衡量因素，因此DFA成為解決匹配性能方案的首選。針對DFA空間開銷大的問題，現已存在很多優秀的研究成果[3]。然而，DFA匹配過程中存在數據強依賴關系，造成其不能很好地適用于高性能數據處理環境。
因此，針對DFA匹配性能較低的問題，本文利用Intel的向量指令集對DFA匹配進行加速。通過一次性讀入若干連續字符，然后并行判斷其是否屬于最常被訪問狀態的非信任字符集，獲取無需訪問內存狀態轉移表即可直接跳過的字符數，從而減少匹配時間的消耗以達到性能加速目的。
本文詳細內容請下載：
http://www.tom3567.com/resource/share/2000006215
作者信息：
楊嘉佳，關健，李正，于增明，姚旺君
（中國電子信息產業集團有限公司第六研究所，北京 100083）
此內容為AET網站原創，未經授權禁止轉載。