《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 模擬設(shè)計(jì) > 設(shè)計(jì)應(yīng)用 > ßFA：一種基于向量指令集的高性能數(shù)據(jù)處理算法
ßFA：一種基于向量指令集的高性能數(shù)據(jù)處理算法
電子技術(shù)應(yīng)用
楊嘉佳，關(guān)健，李正，于增明，姚旺君
中國(guó)電子信息產(chǎn)業(yè)集團(tuán)有限公司第六研究所
摘要： 正則表達(dá)式匹配技術(shù)在數(shù)據(jù)清洗、解析提取等數(shù)據(jù)處理任務(wù)方面發(fā)揮重大作用。然而，由于匹配過(guò)程中存在數(shù)據(jù)強(qiáng)依賴關(guān)系和內(nèi)存訪問(wèn)不可預(yù)測(cè)等問(wèn)題，造成匹配性能較低。針對(duì)此問(wèn)題，提出一種基于向量指令集的高性能正則表達(dá)式數(shù)據(jù)處理算法，稱之為ßFA：通過(guò)向量指令一次性從內(nèi)存讀出若干連續(xù)字符，并與最常被訪問(wèn)狀態(tài)對(duì)應(yīng)的非信任字符集進(jìn)行向量匹配，利用內(nèi)置函數(shù)定位首個(gè)非信任字符的位置，獲得可直接跳過(guò)的字符數(shù)，從而實(shí)現(xiàn)匹配性能的加速。實(shí)驗(yàn)結(jié)果表明，ßFA算法的吞吐率優(yōu)于原始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)載。