Innermost many-sorted term rewriting on GPUs

Johri van Eerd, Jan Friso Groote, Pieter Hijma, Jan Martens, Muhammad Osama, Anton Wijs (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
23 Downloads (Pure)


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.

Original languageEnglish
Article number102910
Number of pages19
JournalScience of Computer Programming
Publication statusPublished - Jan 2023

Bibliographical note

Funding Information:
This work is carried out in the context of the NWO AVVA project 612.001751.


  • GPU
  • Parallel computing
  • Programming
  • Term rewriting


Dive into the research topics of 'Innermost many-sorted term rewriting on GPUs'. Together they form a unique fingerprint.

Cite this