《電子技術應用》
您所在的位置:首頁 > 模擬設計 > 設計應用 > ßFA:一種基于向量指令集的高性能數(shù)據(jù)處理算法
ßFA:一種基于向量指令集的高性能數(shù)據(jù)處理算法
電子技術應用
楊嘉佳,,關健,,李正,,于增明,姚旺君
中國電子信息產(chǎn)業(yè)集團有限公司第六研究所
摘要: 正則表達式匹配技術在數(shù)據(jù)清洗,、解析提取等數(shù)據(jù)處理任務方面發(fā)揮重大作用,。然而,由于匹配過程中存在數(shù)據(jù)強依賴關系和內(nèi)存訪問不可預測等問題,,造成匹配性能較低,。針對此問題,,提出一種基于向量指令集的高性能正則表達式數(shù)據(jù)處理算法,,稱之為ßFA:通過向量指令一次性從內(nèi)存讀出若干連續(xù)字符,并與最常被訪問狀態(tài)對應的非信任字符集進行向量匹配,,利用內(nèi)置函數(shù)定位首個非信任字符的位置,,獲得可直接跳過的字符數(shù),從而實現(xiàn)匹配性能的加速,。實驗結(jié)果表明,,ßFA算法的吞吐率優(yōu)于原始DFA算法和αFA算法,是原始DFA算法的4.67~60倍以及ɑFA算法的4.37~7.82倍,。
中圖分類號:TP391.1 文獻標志碼:A DOI: 10.16157/j.issn.0258-7998.245114
中文引用格式: 楊嘉佳,,關健,李正,,等. ?FA:一種基于向量指令集的高性能數(shù)據(jù)處理算法[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

引言

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

正則表達式匹配的有效手段通常分為確定型有限自動機(Deterministic Finite Automata, DFA)和基于非確定型有限自動機(Nondeterministic Finite Automata, NFA)[2],。兩者各有其特點,,NFA空間復雜性較低,但因為一次字符輸入可能會引發(fā)數(shù)目不定的多個狀態(tài)轉(zhuǎn)移,,造成匹配時間復雜性較大,。相反,原始DFA的時間復雜性低且為O(1),,但存在空間開銷大的問題,。

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

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


本文詳細內(nèi)容請下載:

http://forexkbc.com/resource/share/2000006215


作者信息:

楊嘉佳,關健,李正,,于增明,,姚旺君

(中國電子信息產(chǎn)業(yè)集團有限公司第六研究所,北京 100083)


Magazine.Subscription.jpg

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