Innermost many-sorted term rewriting on GPUs

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

3 Citaten (Scopus)
76 Downloads (Pure)

Samenvatting

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.

Originele taal-2Engels
Artikelnummer102910
Aantal pagina's19
TijdschriftScience of Computer Programming
Volume225
DOI's
StatusGepubliceerd - jan. 2023

Bibliografische nota

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

Financiering

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

Vingerafdruk

Duik in de onderzoeksthema's van 'Innermost many-sorted term rewriting on GPUs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit