Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture

• Author: 谭光明 刘萍 卜东波 刘燕兵
• Subjects: Algorithms ; Artificial Intelligence ; Central processing units ; Computer programming ; Computer Science ; CPUs ; Data Structures and Information Theory ; Decomposition ; Dynamic programming ; Experiments ; Heuristic ; Heuristic methods ; Information Systems Applications (incl.Internet) ; Keywords ; Laboratories ; Optimization ; Parallel processing ; Pattern matching ; Pattern recognition ; Pattern search ; Science ; Search algorithms ; Software Engineering ; Studies ; Theory of Computation ; 功能分解 ; 多核心 ; 多模式匹配算法 ; 执行时间 ; 架构设计 ; 模式搜索 ; 模式设置 ; 网络入侵检测
• Is Part Of: Journal of computer science and technology, 2011-09, Vol.26 (5), p.866-874
• Notes: 11-2296/TP
  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.
  Guang-Ming Tan 1,Member,CCF,ACM,Ping Liu 2,Member,CCF,ACM Dong-Bo Bu 2,Member,CCF,ACM,and Yan-Bing Liu 2,Member,CCF,ACM1 Key Laboratory of Computer System and Architecture,Institute of Computing Technology,Chinese Academy of Sciences Beijing 100190,China 2 Key Laboratory of Network Technology,Institute of Computing Technology,Chinese Academy of Sciences Beijing 100190,China
  parallel algorithm; multi-core; multiple pattern matching
  
• Description: 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.
  
• Publisher: Boston: Springer US
  
• Language: English