raphlinus.github.io

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

Yes, absolutely. If GPUs where as accessible and stuff as stable and standardized as in CPU land many of the above caveats would not apply. The memory barrier may still be there but my guy feeling is we would have so much more code running on GPU then that there would have been solutions developed for this, too, long ago. Raph Linus is currently writing a blog post from the perspective of someone who has been working on GPU-accelerated 2D vector rendering. It echos some of the issues I touched on above. Well worth reading when it is released (probably will hit HN front page anyway): https://github.com/raphlinus/raphlinus.github.io/pull/104

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

I am. It is relevant to the topic, and I cite it in the (now two year old) outline for the blog post I intend to write on the topic[1]. I'll point out that Yuksel's spline is not closed under subdivision, which is a pretty big flaw. To be fair, the current version of hyperbezier also has that flaw, but I now believe it can be fixed. [1]: https://github.com/raphlinus/raphlinus.github.io/issues/40

> 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

The short answer is no, but the long answer is that this is a very complex tradeoff space. Going forward, we may see more of these types of tasks moving to GPU, but for the moment it is generally not a good choice. The GPU is incredible at raw throughput, and this particular problem can actually implemented fairly straightforwardly (it's a stream compaction, which in turn can be expressed in terms of prefix sum). However, where the GPU absolutely falls down is when you want to interleave CPU and GPU computations. To give round numbers, the roundtrip latency is on the order of 100µs, and even aside from that, the memcpy back and forth between host and device memory might actually be slower than just solving the problem on the CPU. So you only win when the strings are very large, again using round numbers about a megabyte. Things change if

Followup: I've changed the language a bit, I hope you agree it's an improvement. https://github.com/raphlinus/raphlinus.github.io/commit/6b92...