Innermost many-sorted term rewriting on GPUs

• Published in: Science of computer programming 2023-01, Vol.225, p.102910, Article 102910
• Main Authors: van Eerd, Johri, Groote, Jan Friso, Hijma, Pieter, Martens, Jan, Osama, Muhammad, Wijs, Anton
• Format: Article
• Language: English
• Subjects: GPU; Parallel computing; Programming; Term rewriting
• ISSN: 0167-6423; 1872-7964
• DOI: 10.1016/j.scico.2022.102910

This article presents a way to implement many-sorted term rewriting on a GPU. This is done by letting the GPU repeatedly perform a massively parallel evaluation of all subterms. Innermost many-sorted term rewriting is experimentally compared with a relaxed form of innermost many-sorted term rewriting, and two different garbage collection mechanisms, to remove terms that are no longer needed, are discussed and experimentally compared. It is concluded that when the many-sorted term rewrite systems exhibit sufficient internal parallelism, GPU rewriting substantially outperforms the CPU. Both relaxed innermost many-sorted rewriting and garbage collection further improve this performance. Since the implementation can probably be even further optimised, and because in any case GPUs will become much more powerful in the future, this suggests that GPUs are an interesting platform for (many-sorted) 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. •Many-sorted term rewriting can be effectively performed in parallel on a GPU.•Garbage collection in GPU term rewriting benefits both memory use and performance.•Inner-most rewriting is thread-safe, and can be relaxed to improve performance.•Many-sorted term rewrite systems offer a convenient means to program GPUs.