Seeking Feedback on a Silly Idea (E-graphs on the GPU)

[c0nn3r]

I have been wondering if e-graphs are a good fit for GPU compute. It seems like since disjoint-sets are typically just backed with arrays that isn't problematic (and there has been further work on disjoint-set data structures designed for GPUs). What seems to be potentially problematic is how to implement hashcons in a fast way?

Also, it seems like the main advantage of GPUs would be that it could significantly speed up relational e-matching?

Just curious to hear some more experienced options before attempting this. :)

[mwillsey]

It definitely seems like it would be challenging, but of course I won't say it can't be done.

Implementing a hashcons on the GPU would be tricky because it's inherently per-e-graph mutable state. E-matching would tricky as well: right now it involves a lot of lookups/pointer-chasing, which I believe are not super well-suited to GPUs.

As of right now, I don't have a compelling reason to think that GPU acceleration would lead to much speedup.

However, our recent paper on Relational E-matching re-frames e-matching as a database problem. I know there has been some work on GPU accelerating certain kinds of SQL queries, so maybe there something there.

[c0nn3r]

Yeah, that's why I mentioned relational e-matching, I agree that it would be horrible without doing that. 😄

[mwillsey]

Whoops, I missed that! So yes, it does seem like it's possible! I'm not up-to-date on the GPU-SQL stuff; I imagine there are certain kinds of queries it's good at and some it's bad at (compared to CPU). Not sure which bucket we would fall in.

[RDambrosio016]

Just wanted to briefly mention that you can try using rust-cuda for this, if you split your core logic into a no_std-able crate you can share that crate with cpu and gpu just fine. Just so you don’t need to potentially duplicate a lot of logic.