前幾年有人嘗試了GPU解析CSV格式文件，但是不乏質疑（Show HN: Parsing CSV files with GPU）。最近又看到兩篇blog：A sketch of string unescaping on GPGPU 和 Towards GPGPU JSON parsing ，作者討論了用GPU對JSON進行parsing的方式。各位如何看待？理論上是否成立？實踐上是否有效？能否適用於更複雜的情況，比如編程語言的AST解析？

---

可行！但是也有一些小問題。

可行：

各種解析都是基於狀態機(FSM)。在CPU和GPU上實現狀態機的一種做法就是狀態表查找，本質上就是pointer chasing模式的內存訪問。

如果並行，其實有很多種思路。

其中一個很常見的思路是對FSM做變換，讓每次只接受一個輸入字元的FSM變成接受多個字元。然後就可以利用SIMD一次完成多個輸入。（這個FSM的術語叫啥忘了。。）

另一個非常容易忽略的思路是，很多輸入可以通過觀察某些字元（如
等，不同的應用有不同的分割符號）很方便的切割成獨立的字元串。這樣不同的並行單元（CPU上的core或者GPU上的PU）同時處理不同的輸入段，也實現了並行。

最後還有一個看起來很蠢但是實際上有人拿來發paper的並行思路。類似於第二種思路，將字元串切割，但是可以在任意位置切。這樣的問題在於，切出來的中間部分缺少起始狀態，所以需要在並行的同時*枚舉*所有可能的其實狀態。

這個東西是PPoPP16的keynote（Keynote I: Madan Musuvathi, Microsof）。我在Micro18搞了一個基於speculative computation的東西（http://alchem.usc.edu/~youwei/publication.html）。

小問題：

應用場景不清晰。如果輸入字元很多，GPU內存不大，PCIe成為瓶頸，有點不太適合這種大數據處理。如果輸入字元很少，在CPU上已經足夠快，也沒有用並行（GPU）的需求。

補充：

有人覺得FSM裡面很多if分支可能會導致divergent。這是一個常見的誤解。如果if的條件對於同一個warp是相同的，那是不會有divergent的。在FSM這個例子里，if的條件通常是輸入字元，其實可以是相同的。

---

其實這就是一個並行parse的問題，從傳統的文法解析和自動機角度來說，這個過程的並行化程度有限，頂多取代部分回溯操作。但是如果我們拋棄常規思維的話，會發現還是有很多地方可以改為並行化的。典型的來說，每個源代碼文件就可以作為獨立的單元並行解析。當然，我認為目前的分析簡單的分為詞法分析和語法分析還是很糙的。要最大可能擴大並行度，我們要分層解析，原理是每一層負責將要解析的文本拆分成多個獨立的解析單元以擴大並行度。解析單元如json的{}，HTML的標籤，CSV的行。

當然，很顯然不是所有的語言解析都可以面向並行優化，但是在多核多線程的今天，如何提高編譯並行度以充分利用硬體性能是很重要的。

以C#語言為例，我所構思的分層解析可以這樣：

第一層：字元串和注釋以及條件編譯符號解析，語句塊和語句解析。

經過第一層解析之後的結果是語句樹，每一個葉節點是一條語句，每一個非葉節點是一個語句塊，語句中可能包含字元串。

第二層A：語句和表達式解析，將每一條語句解析為初步AST，此時符號尚未綁定。因為這一層面向語句，並行度極高。

第二層B：語句塊解析，語句塊符號表綁定。

第二層A和第二層B操作可以同時進行。

第三層：根據第二層處理的語句塊符號表，將AST中的符號與具體的元素（類型、方法、欄位、變數、運算符等）進行綁定。

第四層：語法檢查，對AST進行語法檢查，提取語法錯誤，並將AST進一步修繕為最終表達式樹。

舉例說明：

using System;

namespace MyTest
{

public class Test
{
private String str = "123";
//get a string;
public string GetString()
{
return str;
}
}

}

第一層解析後的結果為：

S:using System;

B:namespace MyTest
{

B:public class Test
{
S:private String str = T:"123";
B:public string GetString()
{
S:return str;
}
}

}

第二層A，提取所有語句解析為初步AST：

S:using System; =&> using ( System )
S:private String str = T:"123"; =&> modifier:private, type:String, name:str, value:T"123"
S:return str =&> return, value:str


第二層B：

B:namespace MyTest
{
imported: namespace System
namespace: MyTest
}

B:public class Test
{
impoerted: namespace System
namespace: MyTest
class: Test
}

B:public string GetString()
{
impoerted: namespace System
namespace: MyTest
class: Test
}

第三層：

S:using System; =&> using ( namespace:System )
S:private String str = T:"123"; =&> modifier:private, type:System.String, name:str, value:C:"123":string
S:return str =&> return, value:field:str


---

據我所知，Parsing一般是有大量if的，所以這應該是很難的。

不過也有人弄出了Parallel Parsing，所以不能否認這種可能性。

---

讓我異想天開的話覺得可行，如很多回答一樣主要問題在於切割，分成許多較為獨立的部分並行解析再合結果。

只是第一步如何分割是個麻煩，可能的方案是有個主線程不停地讀取，同時做簡單狀態機識別。

比如js比較影響的有字元串和正則，初始按照這種互斥影響分割開來，分出一塊就交給並行線程局部解析。

這樣等完全讀完源碼的時候前面的也解析差不多了，然後拼接在一起再次解析即可。

但這只是前端部分，而且性能主要卡在io讀取上。後端部分並行並不了解。

---

沒有用，GPU 長於純粹的算數，並不擅長分支判斷，另外對於什麼項目來說 parse 和編譯是問題？一般要是 FLAG 這種體量了，他們都沒有搞，或許這條路是走不通的

---

推薦閱讀：

相关文章