Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture

doi:10.1007/s11390-011-0185-0

	Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture
	Tan, Guang-Ming 1; Liu, Ping 2; Bu, Dong-Bo 2; Liu, Yan-Bing 2
	2011-09-01
发表期刊	JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
ISSN	1000-9000
卷号	26 期号:5 页码:866-874
摘要	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
DOI	10.1007/s11390-011-0185-0
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[60803030] ; National Natural Science Foundation of China[60925009] ; National Natural Science Foundation of China[60921002] ; National Basic Research 973 Program of China[2011CB302502]
WOS研究方向	Computer Science
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Software Engineering
WOS记录号	WOS:000297212300012
出版者	SCIENCE PRESS
引用统计	被引频次：6[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/12869
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Tan, Guang-Ming
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Key Lab Comp Syst & Architecture, Beijing 100190, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Key Lab Network Technol, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Tan, Guang-Ming,Liu, Ping,Bu, Dong-Bo,et al. Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture[J]. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,2011,26(5):866-874.
APA	Tan, Guang-Ming,Liu, Ping,Bu, Dong-Bo,&Liu, Yan-Bing.(2011).Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture.JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,26(5),866-874.
MLA	Tan, Guang-Ming,et al."Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture".JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 26.5(2011):866-874.