NDLI: Memory Efficient Parallelization for Aho-Corasick Algorithm on a GPU

Content Provider	IEEE Xplore Digital Library
Author	Nhat-Phuong Tran Myungho Lee Sugwon Hong Minho Shin
Copyright Year	2012
Abstract	Pattern matching is a commonly used operation in many applications including image processing, computer and network security, bioinformatics, among many others. Aho-Corasick (AC) algorithm is one of the well-known pattern matching techniques and it is intensively used in computer and network security. In order to meet the real-time performance requirements imposed on these security applications, developing a high-speed parallelization technique is essential for the AC algorithm. In this paper, we present a new memory efficient parallelization technique which efficiently places and caches the input text data and the reference data in the on-chip shared memories and texture caches of the Graphic Processing Unit (GPU). Furthermore, the new approach efficiently schedules memory accesses in order to minimize the overhead in loading data to the on-chip shared memories. The approach cuts down the effective memory access latencies and leads to significant performance improvements. Experimental results on Nvidia GeForce 9500GT GPU shows up to 15-times speedup compared with a serial version on 2.2Ghz Core2Duo Intel processor, and 15Gbps throughput performance.
Starting Page	432
Ending Page	438
File Size	502769
Page Count	7
File Format	PDF
ISBN	9781467321648
DOI	10.1109/HPCC.2012.65
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-06-25
Publisher Place	United Kingdom
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Aho-Corasick algorithm computer security Instruction sets Memory management AC machines Doped fiber amplifiers parallelization GPU Pattern matching Graphics processing unit
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

High Throughput Parallel Implementation of Aho-Corasick Algorithm on a GPU

Performance Optimization of Aho-Corasick Algorithm on a GPU

Multipattern string matching on a GPU

Parallel Implementation of Fuzzified Pattern Matching Algorithm on GPU

Aho-Corasick String Matching on Shared and Distributed-Memory Parallel Architectures

High performance string matching for security applications

GPU-to-GPU and Host-to-Host Multipattern String Matching on a GPU

The GPU-based String Matching System in Advanced AC Algorithm

Parallelization and characterization of pattern matching using GPUs

Memory Efficient Parallelization for Aho-Corasick Algorithm on a GPU

Similar Documents

High Throughput Parallel Implementation of Aho-Corasick Algorithm on a GPU

Performance Optimization of Aho-Corasick Algorithm on a GPU

Multipattern string matching on a GPU

Parallel Implementation of Fuzzified Pattern Matching Algorithm on GPU

Aho-Corasick String Matching on Shared and Distributed-Memory Parallel Architectures

High performance string matching for security applications

GPU-to-GPU and Host-to-Host Multipattern String Matching on a GPU

The GPU-based String Matching System in Advanced AC Algorithm

Parallelization and characterization of pattern matching using GPUs

Memory Efficient Parallelization for Aho-Corasick Algorithm on a GPU