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

# PFAC's optimized implementation on GPGPU - Two-Phase PFAC

參考 : https://www.mdpi.com/2079-9292/8/3/270
by Yoona

### intro
GPU 的內部執行模式是，最基本的計算單位為一個 thread，而 GPU 會把多個 thread 包成一個 warp，執行順序是一個 warp 一個 warp 來

warp 會有整體性，也就是說等到所有其包含的 thread 都執行完畢後才會換下一個 warp 執行

根據我們前一篇對 PFAC 的分析，若把匹配過程分給各個 thread 執行，我們會發現 :
1. 大部分 thread 會在匹配前一到兩個字元時就匹配失敗
2. 但這些 thread 可能會四散在各個 warp 內

-> 也就是說如果 ++不++ 將 "有效 thread (active thread)" 在匹配過程中++持續匯整到同一個 warp 內的話++，那會造成每個 warp 內執行率可能才 20% 且持續大幅下降，但總共有非常多個 warp 內有少量 active thread 需要繼續進行匹配的工作，這樣會造成

1. warp 內資源未被有效利用
2. 因為 warp 之間彼此的獨立性，執行需互相等待，所以 process 時間也會被拉的很長


另外就是，因為整個 PFAC 的 state stable 會太大，塞不進去可以比較快存取的 shared memory, 只能存在 global or texture memory 內
但其實很多條 thread 只會用到 state table 最前面的++兩步++匹配然後就失敗了，也就是說，我們可以透過前面兩步的部分 state stable 就排除大部分的 thread ， in other words, 最前面兩步的 state stable 是使用率最高的部分且有區別 thread 的功效，而且因為只有一小部分的 table，所以它是放得進去 shared memory 的

綜合以上特性，這篇論文提出了
Two-Phase PFAC Algorithm for Multiple Patterns Matching on CUDA GPUs
也就是說，配合 GPU 將 PFAC 的 process 分成"++兩個階段++"去執行已達成 資源 & 效率的最大化

### Two-Phase PFAC
#### 第一階段
1. 將前兩步的 state stable 存在 shared memory 裡面以方便查找
2. 分散在不同 warp 內的 thread 會透過標記 & 前綴和的方式達到判別
(1) 是否為 active thread
(2) 對 active thread 進行新的 warp 分組 (前綴和)
-> merge thread 的 compression procedure

* 一次用兩個首字母進行查表，非零的才是有下一 state


* incomplete 的標記為 1 並記錄前綴和
* 可以對其設定吞吐量上限，前綴和編號 mod 多少以內要為一組


#### 第二階段
就是接手第一階段的後續處理，並且會有許多後面的 warp 是被閒置的，不用被執行，process 時間會大幅減少