Innermost many-sorted term rewriting on GPUs

• DOI: 10.1016/j.scico.2022.102910
• Publication Date: 2022-12-10T00:42:08Z
• Authors: Johri van Eerd; Jan Friso Groote; Pieter Hijma; Jan Martens; Muhammad Osama; Anton Wijs
• Keywords: Confluence

This article presents a way to implement many-sorted term rewriting on GPU. is done by letting the GPU repeatedly perform massively parallel evaluation of all subterms. Innermost experimentally compared with relaxed form innermost rewriting, and two different garbage collection mechanisms, remove terms that are no longer needed, discussed compared. It concluded when rewrite systems exhibit sufficient internal parallelism, substantially outperforms CPU. Both further improve this performance. Since implementation can probably be even optimised, because in any case GPUs will become much more powerful future, suggests an interesting platform for (many-sorted) rewriting. As viewed as universal programming language, also opens route towards especially irregular computations.