Anton Wijs: Inner-most Term Rewriting on GPUs

Event Details

We present a way to implement term rewriting on a GPU. We do this by letting the GPU repeatedly perform a massively parallel evaluation of all subterms. We experimentally compared inner-most term rewriting with a relaxed form of inner-most rewriting, and designed and experimented with two different garbage collection mechanisms, to remove terms that are no longer needed. We find that if the term rewrite systems exhibit sufficient internal parallelism, GPU rewriting substantially outperforms the CPU. Both relaxed inner-most rewriting and garbage collection further improves this performance. Since we expect that our implementation can be even further optimized, and because in any case GPUs will become much more powerful in the future, this suggests that GPUs are an interesting platform for term rewriting. As term rewriting can be viewed as a universal programming language, this also opens a route towards programming GPUs by term rewriting, especially for irregular computations.

This is joint work with Johri van Eerd, Jan Friso Groote, Pieter Hijma, Jan Martens and Muhammad Osama.