《電子技術應用》
您所在的位置:首頁 > 模擬設計 > 設計應用 > 一種基于指令流水線的數據匹配算法
一種基于指令流水線的數據匹配算法
電子技術應用
楊嘉佳,李正,鄭兒,趙靜,燕瑋,劉金
中國電子信息產業集團有限公司第六研究所
摘要: 基于正則表達式的數據匹配技術在基礎數據治理和清洗方面有著重要的應用價值。然而,在高性能計算領域的數據處理過程中因算法匹配吞吐率低,無法滿足大數據處理環境下對算法的高性能要求,造成其應用范圍受限。針對此現象,提出一種基于指令流水線的數據匹配算法,稱之為γFA:利用Intel架構內置的向量指令流水式讀入若干字符段,通過大寬度向量比較函數進行字符段與非信任字符集的流水比值處理并轉換成整型向量,通過位置定位函數累加定位出所有整型向量的首個非信任字符位置,計算出可略過的總字符數,減少正則表達式匹配引擎因處理非信任字符集導致訪問低速內存而帶來巨大的時間開銷,實現正則表達式匹配算法的性能提升。實驗結果表明,γFA算法的吞吐率是原始DFA算法的15.88~53.06倍,相比于ßFA算法,吞吐率提升了35.12%~63.26%,取得較好的性能加速效果。此外,通過對γFA算法進行優化后,性能可接近100 Gb/s,為原始DFA匹配算法性能的15.88~64.94倍,相比于γFA算法性能提升了2.15%~43.09%。
中圖分類號:TP391.1 文獻標志碼:A DOI: 10.16157/j.issn.0258-7998.245345
中文引用格式: 楊嘉佳,李正,鄭兒,等. 一種基于指令流水線的數據匹配算法[J]. 電子技術應用,2025,51(2):81-85.
英文引用格式: Yang Jiajia,Li Zheng,Zheng Er,et al. A data matching algorithm based on instruction pipeline[J]. Application of Electronic Technique,2025,51(2):81-85.
A data matching algorithm based on instruction pipeline
Yang Jiajia,Li Zheng,Zheng Er,Zhao Jing,Yan Wei,Liu Jin
The Sixth Research Institute of China Electronics Corporation
Abstract: The data matching technology based on regular expressions has significant application value in basic data governance and cleaning. However, in the data processing process of high-performance computing, the low performance of algorithm matching cannot meet the high-performance requirements of algorithms in the big data processing environment, resulting in limited application scope. To address this issue, a high-performance data matching algorithm based on instruction pipelining is proposed, known as γFA. It utilizes the vector instruction pipelining built into the Intel architecture to read in multiple character segments, performs pipeline ratio processing of the character segments with untrusted character sets through a wide-width vector comparison function, and converts them into integer vectors. The position location function is then used to accumulate and locate the first untrusted character position in the integer vector, calculate the number of characters that can be skipped, and reduce the significant time overhead caused by the regular expression matching engine accessing slow memory when processing untrusted character sets. This achieves performance acceleration for the regular expression matching algorithm. Experimental results show that the γFA algorithm achieves a throughput rate that is 15.88 to 53.06 times higher than the original DFA algorithm. Compared to the ßFA algorithm, the throughput rate is improved by 35.12% to 63.26%, achieving a better performance acceleration effect. Furthermore, after optimizing the γFA algorithm, a performance close to 100 Gb/s can be achieved, which is 15.88 to 64.94 times better than the performance of the original DFA matching algorithm. This represents an improvement of 2.15% to 43.09% compared to the γFA algorithm.
Key words : regular expression matching;instruction pipeline;high-performance data matching

引言

數據匹配技術可應用于數據的清洗和治理,如基于正則表達式的數據匹配技術在基礎數據的過濾方面發揮重要作用,通過數據匹配可將無關數據剔除過濾,減少噪聲數據的干擾。正則表達式因具有強大的表征能力,適合用于匹配過濾真實環境下的復雜噪聲數據。例如,開源入侵檢測系統Bro IDS、Snort[1]等都使用了基于正則表達式的數據匹配功能。

基于正則表達式的數據匹配實現方式通常可分成兩種:基于非確定型有限自動機(NFA)和確定型有限自動機(DFA)。前者空間復雜度比較低,與正則表達式的長度呈線性關系,但因處理一個字符需激活多個狀態,造成匹配時間復雜性較大和匹配性能不穩定。相比而言,DFA的時間復雜性比較低,處理一個字符只需一次激活單個狀態,然而卻因規則的復雜性易導致狀態轉移空間膨脹甚至“爆炸”,造成巨大的空間開銷。

在大數據匹配環境中,DFA更多地被選擇與應用。DFA的匹配性能和空間消耗是基于正則表達式數據匹配技術的重要衡量因素。截至目前,DFA的空間消耗已有很多可行的算法被提出[2],因而不是本文研究重點。盡管已有若干算法對DFA的匹配性能進行研究,但性能低依舊是制約其廣泛應用的瓶頸因素。

針對此問題,本文基于單指令多數據流(Single Instruction Multiple Data)向量指令連續從內存中讀入若干字符段,然后分別與最常被訪問狀態(行)對應的非信任字符集進行字符并行比較操作,通過位置定位函數累加定位出首個非信任字符位置,獲取直接略過的總字符數,減少訪存次數,提高算法吞吐率。


本文詳細內容請下載:

http://m.rjjo.cn/resource/share/2000006330


作者信息:

楊嘉佳,李正,鄭兒,趙靜,燕瑋,劉金

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


Magazine.Subscription.jpg

此內容為AET網站原創,未經授權禁止轉載。
主站蜘蛛池模板: 欧美特黄特色aaa大片免费看 | 精品国产免费观看 | 欧美国产精品亚洲精品第一区 | 国产日韩亚洲不卡高清在线观看 | 日韩麻豆 | 精品国产一区二区二三区在线观看 | 91精品国产爱久久久久 | 在线欧美精品一区二区三区 | 99久久香蕉国产线看观香 | 日本在线观看www免费 | 亚洲精品午夜久久久伊人 | a毛片免费观看 | 国产亚洲欧美另类久久久 | 未成人做爰视频www 窝窝午夜精品一区二区 | 黄视频免费在线 | 男人操美女逼视频 | 亚洲欧美另类视频 | 完整日本特级毛片 | 久久久9视频在线观看 | 免费一级在线 | 日本一区午夜爱爱 | 在线视频日韩 | 国产成人a一在线观看 | 三级黄色在线 | 高清日本在线成人免费视频 | 手机在线精品视频 | 玖玖爱精品 | 久久久久国产一级毛片高清片 | 精品久久免费视频 | 一级毛片真人免费播放视频 | 99久久精品国产一区二区小说 | 2019国产精品| 91精品视频在线播放 | 一级一级特黄女人精品毛片 | 免费一级大毛片a一观看不卡 | 国产伦久视频免费观看视频 | 国产网曝手机视频在线观看 | 91精品国产爱久久久久 | 亚洲一区二区三区久久精品 | 欧美人成在线 | 亚洲一区精品在线 |