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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

Samenvatting

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.

Originele taal-2	Engels
Titel	Fundamentals of Software Engineering - 9th International Conference, FSEN 2021, Revised Selected Papers
Redacteuren	Hossein Hojjat, Mieke Massink
Uitgeverij	Springer
Pagina's	175-189
Aantal pagina's	15
ISBN van geprinte versie	9783030892463
DOI's	https://doi.org/10.1007/978-3-030-89247-0_12
Status	Gepubliceerd - 2021
Evenement	9th International Conference on Fundamentals of Software Engineering, FSEN 2021 - Virtual, Online Duur: 19 mei 2021 → 21 mei 2021

Publicatie series

Naam	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12818 LNCS
ISSN van geprinte versie	0302-9743
ISSN van elektronische versie	1611-3349

Congres

Congres	9th International Conference on Fundamentals of Software Engineering, FSEN 2021
Stad	Virtual, Online
Periode	19/05/21 → 21/05/21

Bibliografische nota

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

Toegang tot document

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

Andere bestanden en links

Link naar publicatie in Scopus

Citeer dit

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

van Eerd, Johri ; Groote, Jan Friso ; Hijma, Pieter ; Martens, Jan ; Wijs, Anton. / Term Rewriting on GPUs. Fundamentals of Software Engineering - 9th International Conference, FSEN 2021, Revised Selected Papers. redacteur / Hossein Hojjat ; Mieke Massink. Springer, 2021. blz. 175-189 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8dcac397bf2f4b1d80210a14dd258678,

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

pages = "175--189",

editor = "Hossein Hojjat and Mieke Massink",

booktitle = "Fundamentals of Software Engineering - 9th International Conference, FSEN 2021, Revised Selected Papers",

address = "Germany",

}

van Eerd, J, Groote, JF , Hijma, P , Martens, J & Wijs, A 2021, Term Rewriting on GPUs. in H Hojjat & M Massink (redactie), Fundamentals of Software Engineering - 9th International Conference, FSEN 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, blz. 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 ; Martens, Jan ; Wijs, Anton.

Fundamentals of Software Engineering - 9th International Conference, FSEN 2021, Revised Selected Papers. redactie / Hossein Hojjat; Mieke Massink. Springer, 2021. blz. 175-189 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12818 LNCS).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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

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 - 9th International Conference, FSEN 2021, Revised Selected Papers

A2 - Hojjat, Hossein

A2 - Massink, Mieke

PB - Springer

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, redacteurs, Fundamentals of Software Engineering - 9th International Conference, FSEN 2021, Revised Selected Papers. Springer. 2021. blz. 175-189. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-89247-0_12

Term Rewriting on GPUs

Samenvatting

Publicatie series

Congres

Bibliografische nota

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit