Term rewriting on GPUs

DOI10.1007/978-3-030-89247-0_12zbMATH Open1496.68168arXiv2009.07174OpenAlexW3210166429MaRDI QIDQ2145278FDOQ2145278

Authors: Johri van Eerd, Jan Friso Groote, Pieter Hijma, Jan Martens, Anton Wijs 

Publication date: 17 June 2022

Abstract: 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. Since we expect that our implementation can be further optimized, and because in any case GPUs will become much more powerful in the future, this suggests that GPUs are an interesting platform for 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.

Full work available at URL: https://arxiv.org/abs/2009.07174

Recommendations

• scientific article; zbMATH DE number 177461
• Modularity of termination in term graph rewriting
• scientific article; zbMATH DE number 4043232
• Towards a GPU-based implementation of interaction nets
• Essentials of term graph rewriting

zbMATH Keywords

parallel computingterm rewritingGPUprogramming

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Parallel algorithms in computer science (68W10)

Cites Work

• Parallel algorithms for transitive reduction for weighted graphs
• Optimising purely functional GPU programs

Cited In (2)

• Analysing parallel complexity of term rewriting
• On complexity bounds and confluence of parallel term rewriting

Uses Software

• mCRL2
• CUDA
• GPU-PRISM
• textX

This page was built for publication: Term rewriting on GPUs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2145278)