# Length-Bounded Hybrid CPU/GPU Pattern Matching Algorithm for Deep Packet Inspection
## 2 Related Work  
Pattern matching algorithms can be categorized as single-pattern matching and multi-pattern matching. The former finds a single pattern within a string at one time; for instance, the Knuth-Morris-Pratt (KMP) [11] and the Boyer-Moore (BM) [12] algorithms are well known. The latter can recognize multiple patterns within a string simultaneously, in which the Aho-Corasick (AC) [13] and Wu-Manber (WM) [14] algorithms are widely used. Implementing the algorithms by software on general-purpose processors (GPPs) is a trend that presents the advantages of lower cost and higher scalability than implementing it by hardware. Earlier, some algorithms were carried out on the central processing units (CPUs) [15; 16; 17] to handle the incoming packets; nevertheless, such processing did not satisfy the required performance for high speed networks. Therefore, some studies began to focus on developing pattern matching algorithms using graphical processing units (GPUs), which offer superior parallel processing power compared to CPUs. Related studies with regard to designing algorithms on GPUs include [PERSON] and [PERSON] [18] proposing a modified KMP algorithm \"PixelSnort\", which was based on the conventional Snort [19] system. PixelSnort involved off-loading packet processing to the GPU by respectively encoding the packets and patterns into pixels and textures to perform full matching. The result showed that their method outperformed Snort by up to 40% in terms of packet processing rate, but the improvement occurred only in heavy-load conditions. [PERSON] et al. also modified the Snort and proposed a novel system \"Gonort\" [20], in which the AC algorithm was ported to the GPU. The input packets were transferred to the GPU for full pattern matching, and the matched results were sent back to the CPU. The maximum throughput of 2.3 Gbps in the synthetic traffic was achieved, which was two times faster than the Snort in real traffic. [PERSON] et al. further proposed one more parallel processing architecture named \"MIDeA\" [21] that optimized the parallelism of network interface card (NIC), CPUs and GPUs to improve the processing performance. With real traffic input, MIDeA presented the throughput of 5.2 Gbps in off-the-shelf equipment. [PERSON] and [PERSON] [22] presented an optimized pattern matching algorithm \"GPEP\", which achieves higher efficiency by means of low operational complexity and small-size state transition tables. [PERSON] et al. presented a software-based pattern matching method named \"Kargus\" [23] processed by CPU and GPU, which also involved off-loading packet processing to the GPU. The result presented that Kargus outperformed the existing state-of-the-art software IDS by 1.9 to 4.3 times. [PERSON] et al. [24] focused on porting nondeterministic finite automaton (NFA) to the GPU platform. Their proposed data structure and parallel processing achieved a throughput of 10 Gbps. [PERSON] and [PERSON] [25] studied more optimal porting to the GPU platform for deterministic finite automaton (DFA) and NFA. They pointed that using small data tables was not the only way to improve the matching efficiency; the pros and cons of porting automaton to GPU were also described. On the other hand, some literature focused on porting algorithms to other processors [26] and optimizing NFA [27] to further improve efficiency. However, even though GPUs feature superior parallel processing power, the data transfer latency between CPU and GPU impacts the overall performance of pattern matching algorithms. Literature [28] showed that, in GPU program development, the GPU overhead (i.e., kernel launch latency and data transfer latency) should be taken into account. The former indicates the latency of the triggering kernel (the function executed by GPU), and the latter indicates the latency of data transfer between CPU and GPU via PCIe channels. Especially, the data transfer latency is higher than the kernel launch latency.