Term Rewriting on GPUs

Johri van Eerd; Jan Friso Groote; Pieter Hijma; Jan Martens; Anton Wijs

doi:10.1007/978-3-030-89247-0_12

Term Rewriting on GPUs

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

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	Fundamentals of Software Engineering
Subtitle of host publication	9th International Conference, FSEN 2021, Virtual Event, May 19–21, 2021, Revised Selected Papers
Editors	Hossein Hojjat, Mieke Massink
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	175-189
Number of pages	15
ISBN (Electronic)	9783030892470
ISBN (Print)	9783030892463
DOIs	https://doi.org/10.1007/978-3-030-89247-0_12
Publication status	Published - 2021
Event	9th International Conference on Fundamentals of Software Engineering, FSEN 2021 - Virtual, Online Duration: 19 May 2021 → 21 May 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12818 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Fundamentals of Software Engineering, FSEN 2021
City	Virtual, Online
Period	19/05/21 → 21/05/21

Bibliographical note

Funding Information:
Acknowledgment. This work is carried out in the context of the NWO AVVA project 612.001751. We gratefully acknowledge the support of NVIDIA Corporation with the donation of the GeForce Titan RTX used for this research.

Funding Information:
This work is carried out in the context of the NWO AVVA project 612.001751. We gratefully acknowledge the support of NVIDIA Corporation with the donation of the GeForce Titan RTX used for this research.

Publisher Copyright:
© 2021, IFIP International Federation for Information Processing.

Keywords

GPU
Parallel computing
Programming
Term rewriting

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/978-3-030-89247-0_12

Persistent URL (handle)

Persistent link

Cite this

van Eerd, J., Groote, J. F., Hijma, P., Martens, J., & Wijs, A. (2021). Term Rewriting on GPUs. In H. Hojjat, & M. Massink (Eds.), Fundamentals of Software Engineering: 9th International Conference, FSEN 2021, Virtual Event, May 19–21, 2021, Revised Selected Papers (pp. 175-189). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12818 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-89247-0_12

van Eerd, Johri ; Groote, Jan Friso ; Hijma, Pieter et al. / Term Rewriting on GPUs. Fundamentals of Software Engineering: 9th International Conference, FSEN 2021, Virtual Event, May 19–21, 2021, Revised Selected Papers. editor / Hossein Hojjat ; Mieke Massink. Springer Science and Business Media Deutschland GmbH, 2021. pp. 175-189 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6f434cbcbe7e4444b5b6abb793ea0db9,

title = "Term Rewriting on GPUs",

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.",

keywords = "GPU, Parallel computing, Programming, Term rewriting",

author = "{van Eerd}, Johri and Groote, {Jan Friso} and Pieter Hijma and Jan Martens and Anton Wijs",

note = "Funding Information: Acknowledgment. This work is carried out in the context of the NWO AVVA project 612.001751. We gratefully acknowledge the support of NVIDIA Corporation with the donation of the GeForce Titan RTX used for this research. Funding Information: This work is carried out in the context of the NWO AVVA project 612.001751. We gratefully acknowledge the support of NVIDIA Corporation with the donation of the GeForce Titan RTX used for this research. Publisher Copyright: {\textcopyright} 2021, IFIP International Federation for Information Processing.; 9th International Conference on Fundamentals of Software Engineering, FSEN 2021 ; Conference date: 19-05-2021 Through 21-05-2021",

year = "2021",

doi = "10.1007/978-3-030-89247-0_12",

language = "English",

isbn = "9783030892463",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "175--189",

editor = "Hossein Hojjat and Mieke Massink",

booktitle = "Fundamentals of Software Engineering",

address = "Germany",

}

van Eerd, J, Groote, JF, Hijma, P, Martens, J & Wijs, A 2021, Term Rewriting on GPUs. in H Hojjat & M Massink (eds), Fundamentals of Software Engineering: 9th International Conference, FSEN 2021, Virtual Event, May 19–21, 2021, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12818 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 175-189, 9th International Conference on Fundamentals of Software Engineering, FSEN 2021, Virtual, Online, 19/05/21. https://doi.org/10.1007/978-3-030-89247-0_12

Term Rewriting on GPUs. / van Eerd, Johri; Groote, Jan Friso; Hijma, Pieter et al.
Fundamentals of Software Engineering: 9th International Conference, FSEN 2021, Virtual Event, May 19–21, 2021, Revised Selected Papers. ed. / Hossein Hojjat; Mieke Massink. Springer Science and Business Media Deutschland GmbH, 2021. p. 175-189 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12818 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Term Rewriting on GPUs

AU - van Eerd, Johri

AU - Groote, Jan Friso

AU - Hijma, Pieter

AU - Martens, Jan

AU - Wijs, Anton

N1 - Funding Information: Acknowledgment. This work is carried out in the context of the NWO AVVA project 612.001751. We gratefully acknowledge the support of NVIDIA Corporation with the donation of the GeForce Titan RTX used for this research. Funding Information: This work is carried out in the context of the NWO AVVA project 612.001751. We gratefully acknowledge the support of NVIDIA Corporation with the donation of the GeForce Titan RTX used for this research. Publisher Copyright: © 2021, IFIP International Federation for Information Processing.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - GPU

KW - Parallel computing

KW - Programming

KW - Term rewriting

UR - http://www.scopus.com/inward/record.url?scp=85118180383&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85118180383&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-89247-0_12

DO - 10.1007/978-3-030-89247-0_12

M3 - Conference contribution

AN - SCOPUS:85118180383

SN - 9783030892463

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 175

EP - 189

BT - Fundamentals of Software Engineering

A2 - Hojjat, Hossein

A2 - Massink, Mieke

PB - Springer Science and Business Media Deutschland GmbH

T2 - 9th International Conference on Fundamentals of Software Engineering, FSEN 2021

Y2 - 19 May 2021 through 21 May 2021

ER -

van Eerd J, Groote JF, Hijma P, Martens J, Wijs A. Term Rewriting on GPUs. In Hojjat H, Massink M, editors, Fundamentals of Software Engineering: 9th International Conference, FSEN 2021, Virtual Event, May 19–21, 2021, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2021. p. 175-189. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2021 Oct 17. doi: 10.1007/978-3-030-89247-0_12

Term Rewriting on GPUs

Abstract

Publication series

Conference

Bibliographical note

Keywords

UN SDGs

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this