Cache Conscious Parallel Pattern Matching for Aho-Corasick Algorithm on a GPU
1
조회
0
다운로드
4
인용
0
참고문헌
키워드
초록
Pattern matching is a common and important operation in many applications including network security, bioinformatics, etc. Among many pattern matching algorithms, Aho-Corasick (AC) algorithm is intensively used in these applications. In order to speed up and meet the real-time performance requirement for AC algorithm, developing an efficient parallelization technique is essential. In this paper, we develop a new parallelization approach to cache both the input text data and the reference data organized as a 2-dimensional table in the on-chip memories (or caches) on the Graphic Processing Unit (GPU). The new approach also schedules memory accesses carefully to minimize the overhead in loading data to the on-chip shared memory. The approach significantly cuts down the memory latency to load the data and leads to impressive performance improvement. Experimental results on NVidia GT9500 GPU shows up to 15x speedup compared with a serial version on 2.2Ghz Core2Duo Intel processor.
Abstract
Pattern matching is a common and important operation in many applications including network security, bioinformatics, etc. Among many pattern matching algorithms, Aho-Corasick (AC) algorithm is intensively used in these applications. In order to speed up and meet the real-time performance requirement for AC algorithm, developing an efficient parallelization technique is essential. In this paper, we develop a new parallelization approach to cache both the input text data and the reference data organized as a 2-dimensional table in the on-chip memories (or caches) on the Graphic Processing Unit (GPU). The new approach also schedules memory accesses carefully to minimize the overhead in loading data to the on-chip shared memory. The approach significantly cuts down the memory latency to load the data and leads to impressive performance improvement. Experimental results on NVidia GT9500 GPU shows up to 15x speedup compared with a serial version on 2.2Ghz Core2Duo Intel processor.
참고문헌 (13)
- A.V. Aho, "Efficient string matching: An aid to bibliographic search", Communications of the ACM, 20(10), pp.761~772 (1977)
- Marc Norton, "Optimizing Pattern Matching for Intrusion Detection", ~
- NVIDIA, "CUDA Best Practices Guide: NVIDIA CUDA C Programming Best Practices Guide – CUDA Toolkit 4.0", ~ (2011)
- "NVidia gtx280"[URL]
- Giorgos Vasiliadis, "Gnort: High Performance Network Intrusion Detection Using Graphics Processors", RAID, pp.116~134 (2008)
- Soumya Sen, "Performance Charaterization and Improvement of Snort as an IDS", ~
- Fast Exact String Matching on the GPU, "Michael C. Schatz", Center for Bioinformatics and Computational Biology, ~ (2007)
- Cheng-Hung Lin, "Accelerating String Matching Using Multi-Threaded Algorithm on GPU", GLOBECOM 2010, 2010 IEEE Global Telecommunications Conference, pp.1~5 (2010)
- Tumeo, A., "Accelerating DNA analysis applications on GPU clusters", Application Specific Processors (SASP), 2010 IEEE 8th Symposium, pp.71~76 (2010)
- Xinyan Zha, "Multipattern string matching on a GPU", Computers and Communications (ISCC), 2011 IEEE Symposium on, pp.277~282 (2011)
- Tumeo, A., "Efficient Pattern Matching on GPUs for Intrusion Detection Systems", Proceedings of the 7th ACM international conference on computing frontiers
- V. Volkov, "Benchmarking GPUs to Tune Dense Linear Algebra", Proceedings of the ACM, 2008, pp.31, 1~11
- J. Jeon, "Financial Derivatives Modeling Using GPU", Journal of KINGPC (2009)