Reverse-Mode AD of Multi-Reduce and Scan in Futhark

Lotte Maria Bruun; Ulrik Stuhr Larsen; Nikolaj Hey Hinnerskov; Cosmin Eugen Oancea

doi:10.1145/3652561.3652575

Reverse-Mode AD of Multi-Reduce and Scan in Futhark

Lotte Maria Bruun, Ulrik Stuhr Larsen, Nikolaj Hey Hinnerskov, Cosmin Eugen Oancea

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

3 Downloads (Pure)

Abstract

We present and evaluate the Futhark implementation of reverse-mode automatic differentiation (AD) for the basic blocks of parallel programming: reduce, prefix sum (scan), and reduce-by-index (multi-reduce). We present derivations of general-case algorithms, and then discuss several specializations that result in efficient differentiation of most cases of practical interest. We report an experiment that evaluates the GPU performance of the differentiated code and highlights the impact of the proposed specializations as well as the strengths and weaknesses of differentiating at high level bulk-parallel operators vs "differentiating the memory", i.e., low-level implementations that access/update individual array elements.

Originalsprog	Engelsk
Titel	Proceedings of the 2023 35th Symposium on Implementation and Application of Functional Languages, IFL 2023
Forlag	Association for Computing Machinery
Publikationsdato	2023
Sider	1-14
Artikelnummer	14
ISBN (Elektronisk)	9798400716317
DOI	https://doi.org/10.1145/3652561.3652575
Status	Udgivet - 2023
Begivenhed	35th Symposium on Implementation and Application of Functional Languages, IFL 2023 - Braga, Portugal Varighed: 29 aug. 2023 → 31 aug. 2023

Konference

Konference	35th Symposium on Implementation and Application of Functional Languages, IFL 2023
Land/Område	Portugal
By	Braga
Periode	29/08/2023 → 31/08/2023
Sponsor	Well-Typed

Bibliografisk note

Funding Information:
We would like to thank the reviewers for the very useful feedback. We would like to acknowledge Troels Henriksen and Robert Schenck for their invaluable contributions to implementing AD in Futhark. We credit Troels with the idea of differentiating the work-efficient implementation of scan in the case of un-vectorized operators on arrays. This work has been supported by the UCPH Data+ grant: High-Performance Land Change Assessment and by the the Independent Research Fund Denmark (DFF) under grant Monitoring Changes in Big Satellite Data via Massively Parallel AI.

Publisher Copyright:
© 2023 ACM.

Adgang til dokumentet

10.1145/3652561.3652575

FulltextAccepteret manuskript, 899 KBLicens: Ikke-specificeret

Citationsformater

Reverse-Mode AD of Multi-Reduce and Scan in Futhark. / Bruun, Lotte Maria; Larsen, Ulrik Stuhr; Hinnerskov, Nikolaj Hey ; Oancea, Cosmin Eugen.

Proceedings of the 2023 35th Symposium on Implementation and Application of Functional Languages, IFL 2023. Association for Computing Machinery, 2023. s. 1-14 14.

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Bruun, LM, Larsen, US, Hinnerskov, NH & Oancea, CE 2023, Reverse-Mode AD of Multi-Reduce and Scan in Futhark. i Proceedings of the 2023 35th Symposium on Implementation and Application of Functional Languages, IFL 2023., 14, Association for Computing Machinery, s. 1-14, 35th Symposium on Implementation and Application of Functional Languages, IFL 2023, Braga, Portugal, 29/08/2023. https://doi.org/10.1145/3652561.3652575

@inproceedings{b47f1cfa9e694669b48e416d34d45b3b,

title = "Reverse-Mode AD of Multi-Reduce and Scan in Futhark",

abstract = "We present and evaluate the Futhark implementation of reverse-mode automatic differentiation (AD) for the basic blocks of parallel programming: reduce, prefix sum (scan), and reduce-by-index (multi-reduce). We present derivations of general-case algorithms, and then discuss several specializations that result in efficient differentiation of most cases of practical interest. We report an experiment that evaluates the GPU performance of the differentiated code and highlights the impact of the proposed specializations as well as the strengths and weaknesses of differentiating at high level bulk-parallel operators vs {"}differentiating the memory{"}, i.e., low-level implementations that access/update individual array elements.",

author = "Bruun, {Lotte Maria} and Larsen, {Ulrik Stuhr} and Hinnerskov, {Nikolaj Hey} and Oancea, {Cosmin Eugen}",

note = "Publisher Copyright: {\textcopyright} 2023 ACM.; 35th Symposium on Implementation and Application of Functional Languages, IFL 2023 ; Conference date: 29-08-2023 Through 31-08-2023",

year = "2023",

doi = "10.1145/3652561.3652575",

language = "English",

pages = "1--14",

booktitle = "Proceedings of the 2023 35th Symposium on Implementation and Application of Functional Languages, IFL 2023",

publisher = "Association for Computing Machinery",

address = "United States",

}

TY - GEN

T1 - Reverse-Mode AD of Multi-Reduce and Scan in Futhark

AU - Bruun, Lotte Maria

AU - Larsen, Ulrik Stuhr

AU - Hinnerskov, Nikolaj Hey

AU - Oancea, Cosmin Eugen

PY - 2023

Y1 - 2023

N2 - We present and evaluate the Futhark implementation of reverse-mode automatic differentiation (AD) for the basic blocks of parallel programming: reduce, prefix sum (scan), and reduce-by-index (multi-reduce). We present derivations of general-case algorithms, and then discuss several specializations that result in efficient differentiation of most cases of practical interest. We report an experiment that evaluates the GPU performance of the differentiated code and highlights the impact of the proposed specializations as well as the strengths and weaknesses of differentiating at high level bulk-parallel operators vs "differentiating the memory", i.e., low-level implementations that access/update individual array elements.

AB - We present and evaluate the Futhark implementation of reverse-mode automatic differentiation (AD) for the basic blocks of parallel programming: reduce, prefix sum (scan), and reduce-by-index (multi-reduce). We present derivations of general-case algorithms, and then discuss several specializations that result in efficient differentiation of most cases of practical interest. We report an experiment that evaluates the GPU performance of the differentiated code and highlights the impact of the proposed specializations as well as the strengths and weaknesses of differentiating at high level bulk-parallel operators vs "differentiating the memory", i.e., low-level implementations that access/update individual array elements.

U2 - 10.1145/3652561.3652575

DO - 10.1145/3652561.3652575

M3 - Article in proceedings

AN - SCOPUS:85204302259

SP - 1

EP - 14

BT - Proceedings of the 2023 35th Symposium on Implementation and Application of Functional Languages, IFL 2023

PB - Association for Computing Machinery

T2 - 35th Symposium on Implementation and Application of Functional Languages, IFL 2023

Y2 - 29 August 2023 through 31 August 2023

ER -