ß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://m.rjjo.cn/resource/share/2000006215
作者信息：
楊嘉佳，關健，李正，于增明，姚旺君
（中國電子信息產業集團有限公司第六研究所，北京 100083）
此內容為AET網站原創，未經授權禁止轉載。