Term rewriting on GPUs

DOI10.1007/978-3-030-89247-0_12MaRDI QIDQ2145278zbMATH OpenOpenAlexFDO

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

Publication date 17 June 2022

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

zbMATH Keywords

parallel computingterm rewritingGPUprogramming

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(2)

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

Describes a project that uses

Uses Software

• textX
• GPU-PRISM
• CUDA
• mCRL2

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)