A Fast Scalable Automaton-Matching Accelerator for Embedded Content Processors

被引:2
|
作者
Tseng, Kuo-Kun [1 ]
Lai, Yuan-Cheng [2 ]
Lin, Ying-Dar [3 ]
Lee, Tsern-Huei [4 ]
机构
[1] Hungkuang Univ, Dept Comp & Informat Engn, Taichung 433, Taiwan
[2] Natl Taiwan Univ Sci & Technol, Dept Informat Management, Taipei 106, Taiwan
[3] Natl Chiao Tung Univ, Dept Comp & Informat Sci, Hsinchu 300, Taiwan
[4] Natl Chiao Tung Univ, Dept Commun Engn, Hsinchu 300, Taiwan
关键词
Algorithms; Performance; Design; String matching; content filtering; automaton; Aho-Corasick; Bloom filter;
D O I
10.1145/1509288.1509291
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Home and office network gateways often employ a cost-effective embedded network processor to handle their network services. Such network gateways have received strong demand for applications dealing with intrusion detection, keyword blocking, antivirus and antispam. Accordingly, we were motivated to propose an appropriate fast scalable automaton-matching (FSAM) hardware to accelerate the embedded network processors. Although automaton matching algorithms are robust with deterministic matching time, there is still plenty of room for improving their average-case performance. FSAM employs novel prehash and root-index techniques to accelerate the matching for the nonroot states and the root state, respectively, in automation based hardware. The prehash approach uses some hashing functions to pretest the input sub-string for the nonroot states while the root-index approach handles multiple bytes in one single matching for the root state. Also, FSAM is applied in a prevalent automaton algorithm, Aho-Corasick (AC), which is often used in many content-filtering applications. When implemented in FPGA, FSAM can perform at the rate of 11.1Gbps with the pattern set of 32,634 bytes, demonstrating that our proposed approach can use a small logic circuit to achieve a competitive performance, although a larger memory is used. Furthermore, the amount of patterns in FSAM is not limited by the amount of internal circuits and memories. If the high-speed external memories are employed, FSAM can support up to 21,302 patterns while maintaining similar high performance.
引用
收藏
页数:30
相关论文
共 50 条
  • [21] Fast FPGA-Based Fault Injection Tool for Embedded Processors
    Shirazi, Mohammad Shokrolah
    Morris, Brendan
    Selvaraj, Henry
    PROCEEDINGS OF THE FOURTEENTH INTERNATIONAL SYMPOSIUM ON QUALITY ELECTRONIC DESIGN (ISQED 2013), 2013, : 476 - 480
  • [22] A fast asynchronous Huffman decoder for compressed-code embedded processors
    Benes, M
    Nowick, SM
    Wolfe, A
    ADVANCED RESEARCH IN ASYNCHRONOUS CIRCUITS AND SYSTEMS - FOURTH INTERNATIONAL SYMPOSIUM, 1998, : 43 - 56
  • [23] Scalable FPGA-Based Convolutional Neural Network Accelerator for Embedded Systems
    Zhao, Jingyuan
    Yin, Zhendong
    Zhao, Yanlong
    Wu, Mingyang
    Xu, Mingdong
    2019 4TH INTERNATIONAL CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND APPLICATIONS (ICCIA 2019), 2019, : 36 - 40
  • [24] FPGA emulation methodology for fast and accurate power estimation of embedded processors
    Hesselbarth, S.
    Schewior, G.
    Blume, H.
    JOURNAL OF SYSTEMS ARCHITECTURE, 2017, 77 : 14 - 25
  • [25] A platform-based SoC design and implementation of scalable automaton matching for deep packet inspection
    Lin, Ying-Dar
    Tseng, Kuo-Kun
    Lee, Tsern-Huei
    Lin, Yi-Neng
    Hung, Chen-Chou
    Lai, Yuan-Cheng
    JOURNAL OF SYSTEMS ARCHITECTURE, 2007, 53 (12) : 937 - 950
  • [26] Fast software multiplication in F2[x] for embedded processors
    Erdem, Serdar Suer
    TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES, 2012, 20 (04) : 593 - 605
  • [27] FAST: A Scalable Subgraph Matching Framework over Large Graphs
    He, Jiezhong
    Liu, Zhouyang
    Chen, Yixin
    Pan, Hengyue
    Huang, Zhen
    Li, Dongsheng
    2022 IEEE HIGH PERFORMANCE EXTREME COMPUTING VIRTUAL CONFERENCE (HPEC), 2022,
  • [28] Fast and scalable pattern matching for network intrusion detection systems
    Dharmapurikar, Sarang
    Lockwood, John W.
    IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2006, 24 (10) : 1781 - 1792
  • [29] Fast and scalable approximate spectral graph matching for correspondence problems
    Kang, U.
    Hebert, Martial
    Park, Soonyong
    INFORMATION SCIENCES, 2013, 220 : 306 - 318
  • [30] Overlay Automata and Algorithms for Fast and Scalable Regular Expression Matching
    Liu, Alex X.
    Torng, Eric
    IEEE-ACM TRANSACTIONS ON NETWORKING, 2016, 24 (04) : 2400 - 2415