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 条
  • [1] Scalable vector processors for embedded systems
    Kozyrakis, CE
    Patterson, DA
    IEEE MICRO, 2003, 23 (06) : 36 - 45
  • [2] A loop accelerator for low power embedded VLIW processors
    Mathew, B
    Davis, A
    INTERNATIONAL CONFERENCE ON HARDWARE/SOFTWARE CODESIGN AND SYSTEM SYNTHESIS, 2004, : 6 - 11
  • [3] PERG: A Scalable Pattern-Matching Accelerator
    Ho, Johnny Tsung Lin
    Lemieux, Guy G. F.
    2008 1ST MICROSYSTEMS AND NANOELECTRONICS RESEARCH CONFERENCE, 2008, : 29 - 32
  • [4] A Fine-Granularity Image Pyramid Accelerator for Embedded Processors
    Tsai, Chun-Jen
    Wang, Chiang-Yi
    EMBEDDED COMPUTER SYSTEMS: ARCHITECTURES, MODELING, AND SIMULATION, SAMOS 2020, 2020, 12471 : 84 - 95
  • [5] Optimized memory based accelerator for scalable pattern matching
    Vespa, Lucas
    Weng, Ning
    Soewito, Benfano
    MICROPROCESSORS AND MICROSYSTEMS, 2009, 33 (7-8) : 469 - 482
  • [6] A fast block matching for SIMD processors using subsampling
    Moschetti, F
    Debes, E
    ISCAS 2000: IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS - PROCEEDINGS, VOL IV: EMERGING TECHNOLOGIES FOR THE 21ST CENTURY, 2000, : 321 - 324
  • [7] Fast Montgomery Modular Multiplication and Squaring on Embedded Processors
    Li, Yang
    Wang, Jinlin
    Zeng, Xuewen
    Ye, Xiaozhou
    IEICE TRANSACTIONS ON COMMUNICATIONS, 2017, E100B (05) : 680 - 690
  • [8] Fast Signature Matching Using Extended Finite Automaton (XFA)
    Smith, R.
    Estan, C.
    Jha, S.
    Siahaan, I.
    INFORMATION SYSTEMS SECURITY, PROCEEDINGS, 2008, 5352 : 158 - +
  • [9] Broadening the Exploration of the Accelerator Design Space in Embedded Scalable Platforms
    Piccolboni, Luca
    Mantovani, Paolo
    Di Guglielmo, Giuseppe
    Carloni, Luca P.
    2017 IEEE HIGH PERFORMANCE EXTREME COMPUTING CONFERENCE (HPEC), 2017,
  • [10] An Automaton for Fast Multi-streams Content Inspection
    Xu Kefu
    Qi Deyu
    Xiang Jun
    Qian Zhengping
    Zheng Weiping
    2008 7TH WORLD CONGRESS ON INTELLIGENT CONTROL AND AUTOMATION, VOLS 1-23, 2008, : 8805 - 8810