期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture 被引量：2

Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture
原文传递
导出
摘要 Due to the huge size of patterns to be searched,multiple pattern searching remains a challenge to several newly-arising applications like network intrusion detection.In this paper,we present an attempt to design efficient multiple pattern searching algorithms on multi-core architectures.We observe an important feature which indicates that the multiple pattern matching time mainly depends on the number and minimal length of patterns.The multi-core algorithm proposed in this paper leverages this feature to decompose pattern set so that the parallel execution time is minimized.We formulate the problem as an optimal decomposition and scheduling of a pattern set,then propose a heuristic algorithm,which takes advantage of dynamic programming and greedy algorithmic techniques,to solve the optimization problem.Experimental results suggest that our decomposition approach can increase the searching speed by more than 200% on a 4-core AMD Barcelona system. Due to the huge size of patterns to be searched,multiple pattern searching remains a challenge to several newly-arising applications like network intrusion detection.In this paper,we present an attempt to design efficient multiple pattern searching algorithms on multi-core architectures.We observe an important feature which indicates that the multiple pattern matching time mainly depends on the number and minimal length of patterns.The multi-core algorithm proposed in this paper leverages this feature to decompose pattern set so that the parallel execution time is minimized.We formulate the problem as an optimal decomposition and scheduling of a pattern set,then propose a heuristic algorithm,which takes advantage of dynamic programming and greedy algorithmic techniques,to solve the optimization problem.Experimental results suggest that our decomposition approach can increase the searching speed by more than 200% on a 4-core AMD Barcelona system.
作者 谭光明 刘萍 卜东波 刘燕兵
机构地区 Key Laboratory of Computer System and Architecture Key Laboratory of Network Technology
出处 《Journal of Computer Science & Technology》 SCIE EI CSCD 2011年第5期866-874,共9页 计算机科学技术学报（英文版）
基金 supported by the National Natural Science Foundation of China under Grant Nos.60803030,60925009,60921002 the National Basic Research 973 Program of China under Grant No.2011CB302502
关键词 parallel algorithm MULTI-CORE multiple pattern matching parallel algorithm multi-core multiple pattern matching
分类号 TP393.08 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献19

  • 1Snort: Open-source network ids/ips, http://www.snort.org,2011.
  • 2Villa O, Scarpazza D P, Petrini F. Accelerating real-time string searching with multicore processors. Computer, 2008, 41(4): 42-50.
  • 3Bu L, Chandy J A. A cam-based keyword match processor architecture. Journal of Microelectronics, 2006, 37(8): 828-836.
  • 4Sourdis I, Pnevmatikatos D. Pre-decoded cams for efficient and high-speed nids pattern matching. In Proc. the 12th Ann. IEEE Symp. Field-Programmable Custom Computing Machines (FCCM2004), Napa, USA, Apr. 20-23, 2004, pp.258-267.
  • 5Antonatos S, Anagnostakis K C, Markatos E P, Polychronakis M. Performance analysis of content matching intrusion detection systems. In Proc. 2004 Syrup. Applications and the Internet (SAINT2004), Tokyo, Japan, Jan. 26-30, 2004, pp.208-218.
  • 6Chang C, Paige R. From regular cxpressions to DFA's using compressed NFA's. In Proc. the 3rd Ann. Syrup. Combinatorial Pattern Matching ( CPM 1992), Tucson, USA, Apr. 29- May 1, 1992, pp.88-108.
  • 7Sidhu R, Prasanna V K. Fast regular expression matching using FPGAs. In Proc. the 9th Ann. IEEE Symp. Field- Programmable Custom Computing Machines (FCCM2001), Rohnert, USA, Mar. 29-Apr. 2, 2001, pp.227-238.
  • 8Hutchings B L, Franklin R, Carver D. Assisting network intrusion detection with reconfigurable hardware. In Proc. the 10th Ann. IEEE Symp. Field-Programmable Custom Computing Machines (FCCM2002), Napa, USA, Apr. 22-24, 2002, pp.111-120.
  • 9Jung H J, Baker Z K, Prasanna V K. Performance of FPGA implementation of bit-split architecture for intrusion detection systems. In Proc. the 20th Int. Symp. Parallel and Distributed Processing Syrup. (IPDPS 2006), Rhodes Island, Greece, Apr. 25-29, 2006, p.189.
  • 10Kaushik R, Govindarajan R. Two-level mapping based cache index selection for packet forwarding engines. In Proc. the 15th International Conference on Parallel Architectures and Compilation Techniques (PACT2006), Seattle, USA, Sept. 16-20, 2006, pp.212-221.

同被引文献19

引证文献2

二级引证文献2

Journal of Computer Science & Technology
2011年 第5期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部