《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 模拟设计 > 设计应用 > ßFA：一种基于向量指令集的高性能数据处理算法
ßFA：一种基于向量指令集的高性能数据处理算法
电子技术应用
杨嘉佳，关健，李正，于增明，姚旺君
中国电子信息产业集团有限公司第六研究所
摘要： 正则表达式匹配技术在数据清洗、解析提取等数据处理任务方面发挥重大作用。然而，由于匹配过程中存在数据强依赖关系和内存访问不可预测等问题，造成匹配性能较低。针对此问题，提出一种基于向量指令集的高性能正则表达式数据处理算法，称之为ßFA：通过向量指令一次性从内存读出若干连续字符，并与最常被访问状态对应的非信任字符集进行向量匹配，利用内置函数定位首个非信任字符的位置，获得可直接跳过的字符数，从而实现匹配性能的加速。实验结果表明，ßFA算法的吞吐率优于原始DFA算法和αFA算法，是原始DFA算法的4.67~60倍以及ɑFA算法的4.37~7.82倍。
中圖分類號(hào)：TP391.1 文獻(xiàn)標(biāo)志碼：A DOI: 10.16157/j.issn.0258-7998.245114
中文引用格式： 楊嘉佳，關(guān)健，李正，等. ?FA:一種基于向量指令集的高性能數(shù)據(jù)處理算法[J]. 電子技術(shù)應(yīng)用，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

引言

數(shù)據(jù)處理能力是大數(shù)據(jù)時(shí)代的核心要素之一，決定了真實(shí)數(shù)據(jù)環(huán)境下是否滿足數(shù)據(jù)線速處理的要求。正則表達(dá)式匹配技術(shù)可作為數(shù)據(jù)清洗、提取解析和數(shù)據(jù)檢測(cè)等數(shù)據(jù)處理任務(wù)的有效解決手段之一。例如，基于Linux系統(tǒng)的Awk、Vim、Perl工具以及開(kāi)源網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)Bro IDS[1]等都使用了正則表達(dá)式的匹配功能。

正則表達(dá)式匹配的有效手段通常分為確定型有限自動(dòng)機(jī)(Deterministic Finite Automata, DFA)和基于非確定型有限自動(dòng)機(jī)(Nondeterministic Finite Automata, NFA)[2]。兩者各有其特點(diǎn)，NFA空間復(fù)雜性較低，但因?yàn)橐淮巫址斎肟赡軙?huì)引發(fā)數(shù)目不定的多個(gè)狀態(tài)轉(zhuǎn)移，造成匹配時(shí)間復(fù)雜性較大。相反，原始DFA的時(shí)間復(fù)雜性低且為O(1)，但存在空間開(kāi)銷(xiāo)大的問(wèn)題。

在大數(shù)據(jù)處理背景下，正則表達(dá)式的匹配性能是最重要的衡量因素，因此DFA成為解決匹配性能方案的首選。針對(duì)DFA空間開(kāi)銷(xiāo)大的問(wèn)題，現(xiàn)已存在很多優(yōu)秀的研究成果[3]。然而，DFA匹配過(guò)程中存在數(shù)據(jù)強(qiáng)依賴關(guān)系，造成其不能很好地適用于高性能數(shù)據(jù)處理環(huán)境。

因此，針對(duì)DFA匹配性能較低的問(wèn)題，本文利用Intel的向量指令集對(duì)DFA匹配進(jìn)行加速。通過(guò)一次性讀入若干連續(xù)字符，然后并行判斷其是否屬于最常被訪問(wèn)狀態(tài)的非信任字符集，獲取無(wú)需訪問(wèn)內(nèi)存狀態(tài)轉(zhuǎn)移表即可直接跳過(guò)的字符數(shù)，從而減少匹配時(shí)間的消耗以達(dá)到性能加速目的。


本文詳細(xì)內(nèi)容請(qǐng)下載：

http://ihrv.cn/resource/share/2000006215


作者信息：

楊嘉佳，關(guān)健，李正，于增明，姚旺君

（中國(guó)電子信息產(chǎn)業(yè)集團(tuán)有限公司第六研究所，北京 100083）


Magazine.Subscription.jpg

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。