中文引用格式: 楊嘉佳,關(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.
引言
數(shù)據(jù)處理能力是大數(shù)據(jù)時代的核心要素之一,決定了真實數(shù)據(jù)環(huán)境下是否滿足數(shù)據(jù)線速處理的要求。正則表達(dá)式匹配技術(shù)可作為數(shù)據(jù)清洗、提取解析和數(shù)據(jù)檢測等數(shù)據(jù)處理任務(wù)的有效解決手段之一。例如,基于Linux系統(tǒng)的Awk、Vim、Perl工具以及開源網(wǎng)絡(luò)入侵檢測系統(tǒng)Bro IDS[1]等都使用了正則表達(dá)式的匹配功能。
正則表達(dá)式匹配的有效手段通常分為確定型有限自動機(jī)(Deterministic Finite Automata, DFA)和基于非確定型有限自動機(jī)(Nondeterministic Finite Automata, NFA)[2]。兩者各有其特點,NFA空間復(fù)雜性較低,但因為一次字符輸入可能會引發(fā)數(shù)目不定的多個狀態(tài)轉(zhuǎn)移,造成匹配時間復(fù)雜性較大。相反,原始DFA的時間復(fù)雜性低且為O(1),但存在空間開銷大的問題。
在大數(shù)據(jù)處理背景下,正則表達(dá)式的匹配性能是最重要的衡量因素,因此DFA成為解決匹配性能方案的首選。針對DFA空間開銷大的問題,現(xiàn)已存在很多優(yōu)秀的研究成果[3]。然而,DFA匹配過程中存在數(shù)據(jù)強(qiáng)依賴關(guān)系,造成其不能很好地適用于高性能數(shù)據(jù)處理環(huán)境。
因此,針對DFA匹配性能較低的問題,本文利用Intel的向量指令集對DFA匹配進(jìn)行加速。通過一次性讀入若干連續(xù)字符,然后并行判斷其是否屬于最常被訪問狀態(tài)的非信任字符集,獲取無需訪問內(nèi)存狀態(tài)轉(zhuǎn)移表即可直接跳過的字符數(shù),從而減少匹配時間的消耗以達(dá)到性能加速目的。
本文詳細(xì)內(nèi)容請下載:
http://ihrv.cn/resource/share/2000006215
作者信息:
楊嘉佳,關(guān)健,李正,于增明,姚旺君
(中國電子信息產(chǎn)業(yè)集團(tuán)有限公司第六研究所,北京 100083)