pareas

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

Also, while not exactly the algorithm Raph is looking for, here is a bracket matching function (from Pareas, which he also mentions in the talk) in Futhark: https://github.com/Snektron/pareas/blob/master/src/compiler/... I haven't studied it in depth, but it's pretty readable.

Compared to Halide: * Futhark does not expose a scheduling language that gives you precise control over code generation. This is probably the main selling point of Halide. * Futhark has a much broader focus than Halide, which is mainly oriented towards image processing. Futhark wants to support arbitrary data parallel computation. E.g. see this compiler written in Futhark: https://github.com/Snektron/pareas Compared to Sycl: * Futhark is a non-embedded language that is more high level than Sycl. The goals are similar in the sense that both systems to try make (data) parallel programming more accessible. The vision behind Futhark is that the conventional functional programming vocabulary is actually a pretty good fit for parallelism, and that an aggressively optimising compiler can reduce or eliminate the overhead of abstraction. I d