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

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

1 Citation (Scopus)

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

Original language	English
Title of host publication	Proceedings of the 2023 35th Symposium on Implementation and Application of Functional Languages, IFL 2023
Publisher	Association for Computing Machinery
Publication date	2023
Pages	1-14
Article number	14
ISBN (Electronic)	9798400716317
DOIs	https://doi.org/10.1145/3652561.3652575
Publication status	Published - 2023
Event	35th Symposium on Implementation and Application of Functional Languages, IFL 2023 - Braga, Portugal Duration: 29 Aug 2023 → 31 Aug 2023

Conference

Conference	35th Symposium on Implementation and Application of Functional Languages, IFL 2023
Country/Territory	Portugal
City	Braga
Period	29/08/2023 → 31/08/2023

Bibliographical note

Publisher Copyright:
© 2023 ACM.

Access to Document

10.1145/3652561.3652575

FulltextAccepted author manuscript, 899 KBLicence: Unspecified

Library access?

Check availability at the Royal Danish Library

Cite this

Reverse-Mode AD of Multi-Reduce and Scan in Futhark. / Bruun, Lotte Maria; Larsen, Ulrik Stuhr; Hinnerskov, Nikolaj Hey et al.
Proceedings of the 2023 35th Symposium on Implementation and Application of Functional Languages, IFL 2023. Association for Computing Machinery, 2023. p. 1-14 14.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Bruun, LM, Larsen, US, Hinnerskov, NH & Oancea, CE 2023, Reverse-Mode AD of Multi-Reduce and Scan in Futhark. in Proceedings of the 2023 35th Symposium on Implementation and Application of Functional Languages, IFL 2023., 14, Association for Computing Machinery, pp. 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 -