Maintaining parallelism in reverse-mode automatic differentiation on functional parallel array languages
Summary
n this paper we set out to make a simple reverse-mode automatic differentiation (AD) algorithm, that uses tracing for the forward pass, and preserves data parallelism in the reverse pass. To do this, we first try to formalize the notion of tracing somewhat. We find that while some flexibility in the definition of is needed for it to work well, we can also boil it down to picking a subset of data types to keep in the trace. We also define a couple of logical assertions that further help us in showing whether a trace does really contain the information that we need. Having defined tracing, in theory, but also over a Haskell DSL, we continue to automatic differentiation. Here we expand the tracing function into a forward-pass function by adding reference counting and intermediate values. Using this forward-pass trace as a map, we then show how we can do the reverse-pass. We also show that we can keep data-parallelism intact for the map and fold (reduce) operations. Finally, we also highlight how task parallelism can be used in the reverse-pass to possibly unlock even more efficiency.
Collections
Related items
Showing items related by title, author, creator and subject.
-
La recherche contrastive, les grammaires descriptives et les corpus parallèles
Meiberg, Anne (2021)Met deze masterscriptie worden twee onderzoeksmethodes – onderzoek op basis van referentiegrammatica’s en onderzoek op basis van parallelle corpora – vergeleken om te zien met welke van de twee het beste de verschillen te ... -
Harpe, Partitioning Models to Minimize the Parallel Print Time in Fused Filament Fabrication
Lamboo, Casper (2021)3D printers are used for various applications such as education, manufacturing and prototyping. Prototyping is a process where it is very useful to have a physical representation of the object that is being designed. A ... -
The tensor product of bulk synchronous parallel algorithms
Koopman, Thomas (2022)A Bulk Synchronous Parallel (BSP) algorithm is a type of parallel algorithm where communication and computation is separated. We present a way to generalise BSP algorithms for linear functions to a BSP algorithm for the ...