HCDL：基於CPU/GPU協同合作架構之字串比對演算法

Abstract

字串比對演算法(pattern matching algorithm, PMA)為一項搜尋演算法，能找出特定內容(patterns)是否包含在資料字串(data string)內之技術。字串比對演算法於電腦科學與生物資訊等諸多領域中扮演著重要的角色。其中，以網路安全為例，字串比對演算法可以被應用在網路封包內容(payload)檢查、下載檔案內容檢查等用途。近年來因網路的快速發展，安全方面的重要性與日俱增，如市面上產品之桌上型電腦、筆記型電腦與行動電話等，也逐漸需要這樣的檢測功能以強化網路安全。這些產品裝置具備了多核心通用處理器之運算單元，因此以軟體開發字串比對演算法，為一項可行的解決方案，具備了低成本且易撰寫程式與可彈性開發的優勢。目前最常見如採用中央處理器(CPU)或是通用圖形處理器(GPGPU, GPU)來執行字串比對演算法。 本研究提出「HCDL：基於CPU/GPU協同合作架構之字串比對演算法」，對應因單獨採用CPU執行已無法滿足速度需求且運算能力未完整發揮、以及單獨採用GPU執行產生的額外時間成本進而限制整體效能之二大問題。HCDL包含了四大部份：(1)複合式中央處理器/圖形處理器字串比對演算法(Hybrid CPU/GPU PMA)，此為HCDL內部的基底元件，其運作方式為CPU對於外部輸入之資料字串流先行做快速前置過濾的處理，並將可能包含有害內容的資料字串送至GPU進行完整比對。本研究設計之演算法與資料結構，使得CPU可進行足夠快速的前置過濾，大幅減少需送至GPU進行完整字串比對的資料字串數量，進而平衡因為傳輸大量資料至GPU須花費的過量額外時間成本，提升比對之整體效能；(2)基於能力之選項(Capability-based Option)，此為HCDL內部用於輔助基底之子元件之一，針對各種產品具不同配備規格的狀況，採用此元件能對於目標產品中的CPU與GPU的能力(處理字串速度)進行事先的測定。於檢測資料字串時，基於測定結果進行處理方式之切換(是否啟動CPU前置過濾之切換)，以達可配合不同產品設備之需求；(3)動態反應之選項 (Dynamic-reacted Option)，亦為HCDL內部用於輔助基底子元件之一，相對於基於能力之選項處理切換為固定的設計，採用此元件能將處理切換轉為動態運作，根據感測當下接收資料字串流的狀況，以達更加適當的處理模式切換，進而補足處理效能；(4)長度界定之選項 (Length-bounded Option)，也是HCDL內部用於輔助基底子元件之一，採用此選項元件能對於不同的輸入資料字串長度，進行適當的檢測方式分配(決定該資料字串先送至CPU前置過濾或直接在GPU完整比對)，改善因資料字串長度不一而影響整體處理效能之問題，達到更佳的處理效能。在此論文中，本研究以檢查網路封包內容為應用案例，評估此HCDL之效能。實驗結果顯示HCDL執行之CPU/GPU的協同合作是有效的，優於CPU與GPU單獨執行之效能。此外，藉由HCDL內部的四項元件設計，使得HCDL在各種不同的狀況下能維持較好的效能。

Pattern matching algorithm (PMA) is a mechanism that inspects specific contents (patterns) in data strings. PMA is widely-used in several areas such as computer science and bioinformatics, in which there are many candidate applications. For instance, in network security, PMA can be applied to check whether the packet payloads or downloaded files contain any abnormal contents to ensure the security. More and more commodity devices such as desktop computers, notebook computers and mobile phones also need such functionality for security enhancement. Since these devices are usually equipped with multi-core general-purpose processors (GPPs), software-based implementation becomes a feasible solution that features lower cost and programmability. GPPs such as central processing units (CPUs) and graphics processing units (GPUs) have been used in many studies; for better efficiency, PMAs are developed by means of parallel processing. In this dissertation, HCDL, a PMA based on CPU/GPU cooperative architecture is investigated. HCDL consists of four parts: (1) a base component named Hybrid CPU/GPU Pattern Matching Algorithm, in which the CPU processes the input data strings by pre-filtering first, then the pre-filtered data (the strings possibly containing any pattern) are delivered to the GPU and processed with full pattern matching method. A sufficiently small data structure and pre-filtering mechanism were designed to enable fast pre-filtering and reducing GPU overhead; (2) a sub-component named Capability-based Option, which enables adapting commodity devices with different specification by estimating the CPU/GPU processing capability in advance, and performs automatic processing mode selection; (3) a sub-component named Dynamic-reacted Option, which enables more dynamic reactions for processing mode selection according to the input data strings sensed in runtime; (4) a sub-component named Length-bounded Option, which enables reducing the performance degradation caused by input data strings with varied lengths. Here, the inspection of packet payloads is taken as an example application to present the experimental evaluation. The results show that this CPU/GPU cooperation in HCDL is effective; namely, performing better than CPU and GPU individual processing. Besides, with this four-component design, HCDL can achieve higher performance under various conditions.