Parallel Parentheses Matching

Also see Fast GPU bounding boxes on tree-structured scenes[1] (unpublished paper) and notes toward a blog post[2]. This is a highly tuned GPU implementation of parentheses matching. It's actually used in Vello (the classic version in which we offload basically all the work to the GPU, not the newer CPU-GPU hybrid version in which tracking the blend stack is done on the CPU).

Earlier versions of the work were featured on HN [3][4], but this is much more sophisticated. (plus a few more zero-comment submissions)

The basic idea (bicyclic semigroup and binary search) is the same as the submission. I think earliest attribution is to Bar-On and Vishkin[5] from 1985. Another implementation of this idea is in pareas[6], an experimental GPU-accelerated compiler.

I believe this work is publishable and would love to work with a student to resubmit it. Especially if you're a student or prof in Sydney, please reach out.

[1]: https://arxiv.org/abs/2205.11659

[2]: https://github.com/raphlinus/raphlinus.github.io/issues/66

[3]: https://news.ycombinator.com/item?id=24385095

[4]: https://news.ycombinator.com/item?id=27164009

[5]: https://dl.acm.org/doi/10.1145/3318.3478

[6]: https://github.com/Snektron/pareas

Getting to discover Oleg Kiselyov's work for the first time is such a treat. His web archive is incredible! I'm envious of the author and anyone else discovering it today.

https://okmij.org/ftp/

Fun article and worth the read, but sadly none of the LaTeX was rendered for me (assuming it was supposed to).