Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture  

作　　者：谭光明 刘萍 卜东波 刘燕兵 

机构地区：[1]Key Laboratory of Computer System and Architecture,Institute of Computing Technology,Chinese Academy of Sciences [2]Key Laboratory of Network Technology,Institute of Computing Technology,Chinese Academy of Sciences

出　　处：《Journal of Computer Science & Technology》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

摘　　要：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.

关 键 词：parallel algorithm MULTI-CORE multiple pattern matching 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]