前几年有人尝试了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 这种体量了，他们都没有搞，或许这条路是走不通的

---

推荐阅读：

相关文章