Fast GPU bounding boxes on tree-structured scenes

Do not nerd snipe me! There's tons of juice left on the CPU side. Again I recommend Metamath Zero (which is somewhat of an opposite direction as HoTT), as it's able to check the entire Metamath proof database in a few hundred milliseconds. This is orders of magnitude faster than most other proof systems. If you did want to manipulate trees on the GPU, then my stack monoid work[1] might be a good basis for it. Of course, a whole nother direction is to use AI to develop proofs, which is a fascinating and growing area (see Holophrasm[2] and DeepMind work[3]). That of course runs on the GPU. [1]: https://arxiv.org/abs/2205.11659 [2]: https://arxiv.org/abs/1608.02644 [3]: https://www.deepmind.com/publications/proving-theorems-using...

Another one if you enjoy this sort of thing like me is Raph Levien's work on the stack monoid; this [1] blog post and this [2] ArXiV paper are great places to look. [1]: https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html [2]: https://arxiv.org/abs/2205.11659

There's a bit more information at [1], but I think the details are not public. The hardware is tracking a separate program counter (and call stack) for each thread. So in the CAS example, one thread wins and continues making progress, while the other threads loop. There seems to some more detail in a Bachelors thesis by Phillip Grote[2], with lots of measurements of different synchronization primitives, but it doesn't go too deep into the hardware. [1]: https://arxiv.org/abs/2205.11659 [2]: https://www.clemenslutz.com/pdfs/bsc_thesis_phillip_grote.pd...

I'm not aware of any similarly mature GPU-based JSON parser, but I believe such a thing is possible. My stack monoid work [1] contains a bunch of ideas that may be helpful for building one. I've thought about pursuing that, but have kept focus on 2D graphics as it's clearer how that will actually be useful. [1]: https://arxiv.org/abs/2205.11659

Not sure why this is popping up now, but people should know there's been quite a bit of followup work. One is a draft paper (not yet polished for publication), on arXiv[1]. I have an issue on my blog[2], and one of these days I intend to get back to it. It's also in use in Vello for the clip stack, in particular computing the intersection of bounding boxes of all clip paths in the spine of the tree from the leaf draw object to the root (clips can be nested to considerable depth). In any case, happy to talk about it. [1]: https://arxiv.org/abs/2205.11659 [2]: https://github.com/raphlinus/raphlinus.github.io/issues/66

It is possible but you have to do things very differently, for example use monoids. There are a few compilers implemented on GPU, including Aaron Hsu's co-dfns and Voetter's compiler project[1]. The parentheses matching problem itself (the core of parsing) has long known efficient parallel algorithms and those have been ported to compute shaders[2] (disclosure: blatant self-promotion). [1]: https://dl.acm.org/doi/pdf/10.1145/3528416.3530249 [2]: https://arxiv.org/pdf/2205.11659.pdf

> PS, is your monoid work online, is it this https://arxiv.org/abs/2205.11659 ? I'm interested in monoids on GPUs. Yes, that's the draft on arXiv, and I have a blog post in the pipeline[1] explaining it to a more general audience. And thanks for the other advice, I'll consider it! [1] https://github.com/raphlinus/raphlinus.github.io/issues/66