Thread divergence free and space efficient GPU implementation of NFA AC

Yogesh, C (2015) Thread divergence free and space efficient GPU implementation of NFA AC. Masters thesis, Indian Institute of Technology Hyderabad.

Preview

Text
CS13M1007.pdf - Submitted Version
Download (2MB) | Preview

Abstract

Multipattern String Matching problem reports all occurrences of a given set or dictionary of patterns in a document. Multipattern string matching problems are used in databases, data mining, DNA and protein sequence analysis, Intrusion detection systems (IDS) for applications (APIDS), networks (NIDS), protocols (PIDS), Host-based IDS, antivirus softwares, and machine learning problems. Parallel algorithm for multipattern string matching can be useful for above mentioned application because by using parallel platforms large number of threads can be executed parallelly and these thread can search for patterns in parallel. One of the multipattern search algorithm is a Aho- Corasick (AC) is a multipattern search algorithm. AC algorithm has two versions : NFA AC and DFA AC. DFA AC and NFA AC have matching automata to perform multipattern searching. NFA AC automata takes less memory then DFA AC automata. Many parallel implementations for AC algorithm are available.

[error in script]

IITH Creators: