We are interested in finding a programming model to employ the power of Graphics Processing Units (GPUs) more easily than via traditional programming. We propose to express computations in the form of

term rewrite systems. 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 find that if the term rewrite systems exhibit sufficient internal parallelism, GPU rewriting substantially outperforms the CPU. As we expect that our implementation can be further optimized, and because in any case GPUs will become much more powerful in the future, this paves a very interesting step towards running more common programs on GPUs.

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