[neel_k]

In the conclusion, raph writes:

> I am even more convinced than before that efficient parsing is possible on GPU.

IMO, the place to start looking for GPU-friendly parsing algorithms is Valiant's algorithm, which is asymptotically the fastest known general CFG parsing algorithm, and is implemented in terms of Boolean matrix multiplication.

The intuition is that bottom-up parsing is basically a transitive closure computation, which is basically the same as solving systems of linear equations over a Boolean ring, which can be sped up using Strassen's algorithm.

A bit of Googling suggests that people have looked at optimising Boolean matrix multiplication on GPUs, but I have no idea what the state of the art here is.

[082349872349872]

Didn't SIGFPE's blog cover this years ago?

Bonus clip: https://www.youtube.com/watch?v=j4YNPhllDXU