###### tags: `pattern-matching`

# Parallel Failure less AC algorithm

by Yoona

這裡會介紹 AC 算法是如何演變成 PFAC 的，另外也提供了直觀的想法可以理解~

本篇參考 : http://rportal.lib.ntnu.edu.tw/bitstream/20.500.12235/35334/1/ntnulib_tp_E0213_04_003.pdf

### intro
由於網路攻擊手法及傳輸資料的速度近來大幅上升，因此我們也必須 升級 = 加速 我們的字串匹配算法以抵禦攻擊
升級的方法有很多種，包括對不同算法結合不同硬體方面的研究，那這邊我們探討的方式是 AC 算法搭配 GPU 的特性而開發出的 PFAC 算法~ (好像看論文的時候有看到這種 演算法 & 硬體 的搭配改良過後效能是相較於其他搭配更有效率的說法)

### AC 算法的缺點 & GPU 的特性

1. AC 算法有許多 failure links 的連接，這些連接在後續 process 中的 state 的儲存會耗費大量記憶體空間

2. 另外 AC 對字串的處理模式比較像是單線程的處理到底
但 GPU 的運作模式是"同時多線程"的去處理許多簡單的問題，所以我們++勢必得將 AC 的運算過程拆成多區塊去交給 GPU 處理++，以利用 GPU 的性質節省大量的匹配時間

3. 我們後面會發現多線程處理模式下的 failure links 反而是增加時間的累墜，而非像其在單線程模式下是減少時間花費的

4. 因此 failure links 在多線程下會被拿掉，但我們會用多線程步驟下的其他處理方式補足其功能

### PFAC 的演變
#### 1. 拆解原字串分配下去同時比對
將原字串分成 n 等分，將時間縮短為 1/n

* 問題 : 卡在邊界的字串不會被偵測到 - boundary detection problem

#### 2. 每個分段增加其比對範圍涵蓋到他去塊以解決問題
Every thread scans across the boundary to resolve the boundary detection problem

至於涵蓋範圍要多長呢，則跟建立的匹配字典樹深度有關，其長度為字典樹最深的 pattern 長度 -1
所以整個最小匹配長度為 : ( 切割長度 + 最長 pattern - 1 )

* 問題 :
1. 多次的切割再交給 GPU 處理的過程可能造成匹配 ++錯誤率大幅上升++
2. overlap 的部分會造成計算量大幅上升，字串吞吐量會存在瓶頸
3. 此時還未解決如何去掉 failure links 的問題 ( failure links 會用掉大量的儲存空間 )


所以目前整體還是個尚未理想的狀態，那有什麼樣的切割方式才能更完美呢?~(切割以工作分配是 GPU 的精隨，所以專注於探討如何用切割方式突破)

#### 3. PFAC 的誕生
就是每個字元都用一顆字典樹下去戳
解決了
1. ++boundary detection 的問題++，因為不會有被跳過的邊界，每個邊界都會被匹配到
2. failure links 的問題，因為不會有需要簡化匹配、"單一線程到底"的部分，所以 ++failure links 可以拿掉以節省記憶體空間++

疑惑 : 這樣不會大幅增加需要處理的事情嗎?~
A : 其實不會，因為大多數的匹配在前面第一 or 二個字元時就會匹配失敗，此時就可以 drop 掉它們不需要去處理了，反而更省事
而且其 worse case 的時間表現也比最原始 AC 算法中，需要透過 failure links 連來連去的++時間快上許多++，同時也比 segment 切段快

至於 drop 掉 thread 的部分在 GPU 內部是會有一些問題存在的，而根據 GPU 內部處理程序的特性我們還可以將其處理程序繼續優化，這部分就留到另一篇解析

### 直觀的想法
其實整件事就是將字串的匹配回歸到 ++字典樹++ 的出發點
因為今天我們有 GPU 可以協助"同時做大量及簡單的事情"，所以就可以請 GPU 對整個長字串，從 ++每個位置++ 出發去用++字典樹++去看有無我們要找的字串，而不需去考慮因為不能同步且大量同時匹配而需節省後續時間的問題, which is 單一線程需考慮的問題，所以 KMP & failure links 的部分可以被 drop 掉