Throughput-Oriented Optimization for Parallel Pattern Matching Algorithm on Multi-Core Gpu

[[abstract]]Network Intrusion Detection Systems (NIDS) have been widely used to protect computer systems from network attacks. The kernel of pattern matching dominates the performance of an NIDS to inspect packet content against thousands of predefined patterns. Due to the ever-increasing number of attacks and network complexity, traditional sequential pattern matching algorithms have become inadequate for the high-speed network.In this project, we carry out an in-depth study of the proposed algorithm performed on GPUs including thread divergence, memory organization, caching and locality, and memory bandwidth. Due to specific architecture of GPUs, to explore higher performance, it is imperative to study the implementation issues on GPUs. Considering the GPU architecture, we attempt to introduce several throughput-oriented techniques including reducing global memory transaction of input buffer, reducing latency of transition table lookup, avoiding bank-conflict of shared memory, and coalescing write to global memory in GPUs. Finally, we intend to deal with the memory limitation of GPUs by two ways. One is to utilize the memory of GPUs by optimizing the state transition table of our proposed algorithm. The other is to use multi-GPUs to increase throughput by distributing workload to multiple GPUs. In this part, we will detail the mechanism for binding GPU thread to CPU Pthreads, creating a task pool, and handling errors and exception conditions of joint CPU/GPU architecture.To demonstrate our algorithm, we will use attack patterns from Snort V2.8 and test the PFAC kernel using DEFCON packets which contains large amounts of attack patterns. Experimental results will be compared to the AC algorithm performed on multicore CPUs with OpenMP and Pthread as well as state-of-the-art GPU-based approaches.The research results have been presented at 2011 IEEE GLOBECOM, the 22nd VLSI Design/CAD Symposium, and 2012 GPU Technology Conference (GTC).