Reverse Automatic Differentiation in Futhark

In this thesis, we describe our work with reverse automatic differentiation (AD) in the dataparallel programming language Futhark. The main motivation is to extend and optimise reverse AD in Futhark’s compiler to permit more expressive programs to by differentiated automatically and efficiently. Futhark’s AD consists of a set of rewrite rules that are used to transform a program to its differentiated counterpart. We present reverse mode AD rewrite rules for the operations reduce-byindex and scan. Reduce-by-index, also known as multi-reduce, has a generic cases and multiple special cases, of which the latter are loosely described by Schenck et al. 2022. We formulate and present a rewrite rule for the generic case and present specific rewrite rules for the special cases as Futhark pseudo-code. Likewise, we examine the reverse AD rewrite rules for scan presented by Schenck et al. 2022, one of which we have simplified with a performance benefit. The existing AD implementation is modified to work when the scan operates on tuples. We have extended the generic case with specialised rewrite rules for scan operators whose Jacobian matches specific patterns. We have implemented the presented rewrite rules of both reduce-by-index and scan in Futhark’s compiler. The performance of differentiated programs is evaluated experimentally and compared to its primal program performance and the program differentiated with forward AD instead. In many case, this demonstrates reasonable reverse AD overheads and competitive performance to Futhark’s established forward AD implementation.