Differentiate Everything with a Reversible Domain-Specific Language
Authors: JinGuo Liu
Taine Zhao
Venue:  (2021)
Keywords: Reversible computing
automatic differentiation
Julia

Abstract: Reverse-mode automatic differentiation (AD) suffers from the issue of having too much space overhead to trace back intermediate computational states for backpropagation.
The traditional method to trace back states is called checkpointing that stores intermediate states into a global stack and restore state through either stack pop or re-computing.
The overhead of stack manipulations and re-computing makes the general purposed (or not tensor-based) AD engines unable to meet many industrial needs.
Instead of checkpointing, we propose to use reverse computing to trace back states by designing and implementing a reversible programming eDSL, where a program can be executed bi-directionally without implicit stack operations. The absence of implicit stack operations makes the program compatible with existing compiler features, including utilizing existing optimization passes and compiling the code as GPU kernels.
We implement AD for sparse matrix operations and some machine learning applications to show that our framework has state-of-the-art performance.

Under review as a conference paper at ICLR 2021
DIFFERENTIATE EVERYTHING WITH A REVERSIBLE EMBEDED DOMAIN-SPECIFIC LANGUAGE
Anonymous authors Paper under double-blind review
ABSTRACT
Reverse-mode automatic differentiation (AD) suffers from the issue of having too much space overhead to trace back intermediate computational states for pack-propagation. The traditional method to trace back states is called checkpointing that stores intermediate states into global stack and restore state through either stack pop or re-computing. The overhead of stack manipulations and re-computing makes the general purposed (not tensor-based) AD engines unable to meet many industrial needs. Instead of checkpointing, we propose to reverse computing to trace back states by designing and implementing a reversible programming eDSL, where program can executed bi-directionally without implicit stack operations. The absence of implicit stack operations makes the program compatible with existing compiler features, including utilizing existing optimization passes and compiling the code GPU kernels. We implement AD for sparse matrix operations and some machine learning applications show that our framework has the state-of-the-ar performance.
INTRODUCTION
Most of the popular automatic differentiation (AD) tools in the market, such as TensorFlow (Abadi et al., 2015), Pytorch (Paszke et al., 2017), and Flux (Innes et al., 2018) implements reverse mode AD at the tensor level to meet the need in machine learning. Later, People in the scientific computing domain also realized the power of these AD tools, they use these tools to solve scientific problems such as seismic inversion (Zhu et al., 2020), variational quantum circuits simulation (Bergholm al., 2018; Luo et al., 2019) and variational tensor network simulation (Liao et al., 2019; Roberts et al., 2019). To meet the diverse need these applications, one sometimes has to define backward rules manually, for example
1. To differentiate sparse matrix operations used in Hamiltonian engineering (Hao Xie & Wang), people defined backward rules for sparse matrix multiplication and dominant eigensolvers (Golub & Van Loan, 2012),
2. In tensor network algorithms study the phase transition problem (Liao al., 2019; Seeger et al., 2017; Wan & Zhang, 2019; Hubig, 2019), people defined backward rules for singular value decomposition (SVD) function and QR decomposition (Golub & Van Loan, 2012).
Instead of defining backward rules manually, one can also use a general purposed AD (GP-AD) framework like Tapenade (Hascoet & Pascual, 2013), OpenAD (Utke al., 2008) and Zygote (Innes, 2018; Innes et al., 2019). Researchers have used these tools in practical applications such as bundle adjustment (Shen & Dai, 2018) and earth system simulation (Forget et al., 2015), where differentiating scalar operations is important. However, the power of these tools are often limited by their relatively poor performance. In many practical applications, a program might do billions of computations. In each computational step, the AD engine might cache some data for backpropagation. (Griewank Walther, 2008) Frequent caching of data slows down the program significantly, while the memory usage will become bottleneck well. Caching implicitly also make these frameworks incompatible with kernel functions. To avoid such issues, we need a new GP-AD framework that does not cache automatically for users.
In this paper, we propose to implement the reverse mode AD on a reversible (domain-specinf) programming language (Perumalla, 2013; Frank, 2017). where intermediate states can be traced

---

Under review as a conference paper at ICLR 2021
backward without accessing an implicit stack. Reversible programming allows people utilize the reversibility to reverse a program. In machine learning, reversibility is proven to substantially decrease the memory usage in unitary recurrent neural networks (MacKay et al., 2018), normalizing flow (Dinh et al., 2014), hyper-parameter learning (Maclaurin et al., 2015) and residual neural networks (Gomez al., 2017; Behrmann al., 2018). Reversible programming will make these happen naturally. The power of reversible programming is not limited to handling these reversible applications, any program can be written in a reversible style. Converting an irreversible program to the reversible form would cost overheads in time and space. Reversible programming provides a flexible time-space trade-off scheme that different with checkpointing (Griewank, 1992; Griewank & Walther, 2008; Chen et al., 2016). reverse computing (Bennett, 1989; Levine Sherman, 1990), to let user handle these overheads explicitly.
There have been many prototypes of reversible languages like Janus (Lutz, 1986). R (not the popular one) (Frank, 1997), Erlang (Lanese et al., 2018) and object-oriented ROOPL (Haulund, 2017). In the past, the primary motivation to study reversible programming is to support reversible computing devices (Frank & Knight Jr, 1999) such as adiabatic complementary cettll-xiide-semioodduuee
(CMOS) (Koller & Athas, 1992), molecular mechanical computing system (Merkle et al., 2018) and superconducting system (Likharev, 1977; Semenov et al., 2003; Takeuchi al., 2014; 2017), and these reversible computing devices are orders more energy-efficient. Landauer proves that only when a device does not erase information (i.e. reversible), its energy efficiency can go beyond the thermal dynamic limit. (Landauer, 1961; Reeb & Wolf, 2014) However, these reversible programming languages can not be used directly in real scientific computing, since most of them do not have basic elements like floating point numbers, arrays, and complex numbers. This motivates us to build a new embedded camain-specifie language (eDSL) Julia (Bezanson et al., 2012; 2017)
new playground of GP-AD.
In this paper, we first compare the time-space trade-off off in the optimal checkpointing and the optimal reverse computing in Sec. 2. Then we introduce the language design of Nil.ang See. 3. Sec. 4, we explain the implementation of automatic differentiation in Nil.ang In Sec. 5, we benchmark the performance of NiLang's AD with other AD software and explain why it is fast.
2 REVERSE COMPUTING AS AN ALTERNATIVE TO CHECKPOINTING
One can use either checkpointing or reverse computing to trace back intermediate states of a T- step computational process 5i fi()). = fa(s))..... fr(s-1) with run-time memory S. In the checkpointing scheme, the program first takes snapshots of states at certain time steps S (Sa. .). S < < ... < 7' by running forward pass. When retrieving state sk, if & E S, just return this state, otherwise, return max Syzk E S and re-compute & from sy. In the reverse
computing scheme, one first writes the program in reversible style. Without prior knowledge, regular program can be transpiled to the reversible style is by doing the transformation in Listing. 1.
Listing I: Transpiling regular code the reversible code without prior knowledge.
Listing 2: The reverse of Listing.
fy fr(sy
(((8)
+= fa(a))
f - fi( f f((%)
+= fr(ST 2)
Then one can visit states in the reversed order by running the reversed program in Listing. 2, which erases the computed results from the tail. One may argue that easing through uncomputing is not necessary here. This is not true for a general reversible program, because the intermediate states might be mutable and used in other parts of the program. It is easy to see, both checkpointing and reverse computing can trace back states without time overhead, but both suffer from space overhead that linear to time (Table 1). The checkpointing scheme snapshots the output in every step, and the reverse computing scheme allocates extra storage for storing outputs in every step. On the other side, only checkpointing can achieve a zero space overhead by recomputing everything from the beginning so, with time complexity O(12). The minimum space complexity in reverse
2

---

Under review as a conference paper at ICLR 2021
computing is O(S log(T/S)) (Bennett, 1989; Levine & Sherman, 1990; Perumalla, 2013), with time complexity O(T15585)
most time efficient (Time/Space)
most space efficient (Time/Space)
Method
Checkpointing
O 5)
OTT))/OS)) OCTCE)""))0 log(
Reverse computing
O1T)/OT S)
Table 1: T and S are the time and space of the original irreversible program. In the "Reverse computing" case, the reversibility of the original program is not utilized.
The difference in space overheads can be explained by the difference of the optimal checkpointing and optimal reverse computing algorithms. The optimal checkpointing algorithm that widely used in AD is the treeverse algorithm in Fig. (a)) This algorithm partitions the computational process binomially into sectors. At the beginning of each sector, the program snapshots the state and push it into a global stack, hence the memory for checkpointing is dS. The states in the last sector are retrieved by the above space-efficient O(T²) algorithm. After that, the last snapshot can be freed and the program has one more quota in memory. With the freed memory, the second last sector can be further partition into two sectors. Likewise, the /th sectors is partitioned into sub-sectors, where / is the sector index counting from the tail. Recursively apply this treeverse algorithm r times until the sector size is 1. The approximated overhead in time and space are
T = IT,S. dS.
(1)
where 7' 17(1, d) holds. By carefully choosing either or d, the overhead in time and space can be both logarithmic.
On the other side, the optimal time-space trade-off scheme in reverse computing is the Bennett's algorithm illustrated in Fig. 1 (b). It evenly evenly partition the program into k sectors. The program marches forward (P process) for & steps obtain the final state Sk+1 then backward (Q process) from the k - 1th step to crase the states in between Si<idt This process is also called the compute-copy" uncompute process. Recursively apply the each P/Q process contains only one unit computation. the time and space complexities are
process for each sector until
T, T.=T(
TIA
S,,
k- --1 T log S
In
Here, the overhead in time is polynomial, which is worse than the treeverse algorithm. The treeverse like partition does not apply here because the first sweep create initial checkpoints without introducing any space overheads is not possible in reversible computing, The pseudo-code of Bennett's 's time-space trade-off algorithm is shown in Listing. 3.
Listing 3: The Bennett's time-space trade-off scheme. The first argument { is the collection states, is the number of partitions, i and len are the starting point and length of the working sector. A function call changes variables inplace. 5." is the symbol of uncomputing, which means undoing a function call. Statement S;+1 + 0 allocates zero state and add it to the state collection. Its inverse Si+1 0 discards zero cleared state from the collection. Its Nil.ang implementation in
Appendix A.
(ln.... k, len)
if len au Swi [arii %))
else
# process that calls the forward program k steps bennett (Is,... k, i+len=k*(j-D) (j-1), lensk) for je1.2.....k # process that calls the backward program k-1 steps -bennett((s,...), k, islenske(j-1), lensk) for jek-1,k-2,....
The reverse computing does not show advantage from the above complexity analysis. But we argue the this analysis is from the worst case, which are very different to the practical using cases. First,
3

---

Under review as a conference paper at ICLR 2021
(a)
(b)
P1
P1
P1
((t-1,2)n(t-1.1)
Q1
Q1
P2
P2
P2
n(t,3)
n(t, 1),,
Q2
Q2
Figure 1: (a) Treeverse algorithm for optimal checkpointing, (Griewank, 1992) 17(TT, 6) = T+
(r+5] rla! is the binomial function. (b) Bennett's time space trade-off scheme for reverse com- puting. (Bennett, 1973; Levine & Sherman, 1990) P and Q are computing and uncomputing respectively. The pseudo-code is defined in Listing. 3.
reverse computing can make use of the reversibility to save memory. In Appendix B.2, we show how to implement unitary matrix multiplication without introducing overheads space and time. Second, reverse computing does not allocate automatically for users, user can optimize the memory access patterns for their own devices like GPU. Third, reverse computing is compatible with effective codes, so that it fits better with modern languages. In Appendix B.I, show how to manipulate inplace functions on arrays with NiLang. Fourth, reverse computing can utilize the existing compiler to optimize the code because it does not introduce global stack operations that harm the purity of functions. Fifth, reverse computing encourages users to think reversibly. In Appendix B.3, we show reversible thinking can lead the user constant memory, constant time implementation of chained multiplication algorithms.
3 LANGUAGE DESIGN
NiL.nng is an embedded domain-specific language (eDSL.) NiLang built on top of the host language Julia (Bezanson al., 2012: 2017). Julia popular language for scientific programming and machine learning. We choose Julia mainly for speed. Julia is a language with high abstraction, however, its clever design of type inference and just in time compiling make it has a like speed. Meanwhile, it has rich features for meta programogg....ng. Its package for pattern matching MLStyle allows us to define an eDSL less than 2000 lines. Comparing with a regular reversible programming language, NiLang features array operations, rich number systems including floating-poin point numbers, complex numbers, fixed-point numbers, and logarithmic numbers. It also implements the campute-copy-umcomput (Bennett, 1973) macro increase code reusability. Besides the above reversible hardware compatible features, it also has some reversible hardware incompatible features meet the practical needs. For example, it views the floating operations as reversible. It also allows users to extend instruction sets and sometimes inserting external statements. These features are not compatible with future reversible hardware. NiLang's compiling process, grammar and operational semantics are described in Appendix G. The source code also available online, we will put a link here after the anonymous open review session. By the time of writing, the version of NiLang is v0.7.3.
and
3.1 REVERSIBLE FUNCTIONS INSTRUCTIONS
Mathematically, any irreversible mapping y = fargs.... can be trivially transformed to its reversible form y += f(args...) or y Y= f(arss...) (L is the bit-wise XOR), where is pre-emptied variable. But in numeric computing with finite precision, this is not always true. The reversibility of arithmetic instruction is closely related to the number system. For integer and fixed
4

---

Under review as a conference paper at ICLR 2021
point number system, y f(args...) and fargs.... rigorously reversible. For logarithmic number system and tropical number system (Speyer & Sturmfels, 2009). y *= f(args...) and /= farrgs...) floating point numbers, none of the above operations are rigorously reversible. However, for convenience, ignore the round-off errors in floating-point and operations and treat them equal footing with fixed-point numbers in the following discussion. In Appendix F, we will show doing this is safe in most cases provided careful implementation. Other reversible operations includes SWAP. ROT, NEG et. al., and this instruction set is extensible. One can define a reversible multiplier in NiLang as Listing.
reversible (not introducing the zero element). While for
Listing 4: A reversible multiplier
julias using XiLang
julias di function multiplier(y!:::ee a: Re:Real, b: Re:le
yl
end julias mitiplier(2,, 3, 5)
(17, 3, 5)
julias (>mitiplier))11,, 3, 5)
Macro @i generates two functions that are reversible to each other, mul tiplier and -mpleip each defines a mapping R - R. The ! after a symbol part of the name, as a conversion to indicate the mutated variables.
3.2 REVERSIBLE MEMORY MANAGEMENT
A distinct feature of reversible memory management is that the content of a variable must be known when it deallocated. We denote the allocation of pre-emptied memory as x < and its inverse, deallocating a zero emptied variable, but can be pushed to stack pop out later in the uncomputing stage. If a variable allocated and deallocated in the local scope, we call it ancilla. Listing. 5 defines the complex valued accumulative log function.
x - 0. An unknown variable can not be deallocate,
Listing 5: Reversible complex valued log
Listing 6: Compute-cooy--uccompue ver- sion of Listing. 5
function += log(Ix) + iArg(x).
81 Ginline function (log) (r) Cot
8inline function (:+=) (log) (y!: :omplex(T
3. x:: C:opleexx(T)) wbere (e)o(T) (b)(x)
J. Complex(()) where Groutine begin zero(T)
n abs(x)
y!.re += log(n)
end
yl.in += angle(x)
yl.re log(n)
im angle
-- ab)
~Groutine
zero(T)
end
and
Here, the macro @inline tells the compiler that this function can be inlined. One can input "-" KEYJ" respectively editor or REPL. NiLang does not have immutable structs, so that the real part y! re and imaginary y!.im im of a complex number can changed directly. is easy to verify that the bottom two lines in the function body are the inverse of the top two lines. i.e., the bottom two lines uncomputes the top two lines. The motivation of uncomputing is to zero clear the contents in ancilla n so that it can be deallocated correctly. Compute-con wop---cccpyyppptiee is useful design pattern in reversible programming so that we created a pair of macros @routine and ~@routine for it. One can rewrite the above function in Listing. 6.
and "-" by typing "|eettarrowTTAB KEY]" and "[rightarrow
Julia
5

---

Under review as a conference paper at ICLR 2021
(a)
(b)
stmit1
pro equals to post
stnits
pre
post
stmis2
error
BITOr
Figure 2: The flow chart for reversible (a) if statement and (b) while statement. "pre" and "post" represents precondition and postcondition respectively. The assersion errors are thrown to the host language instead of handling them in NiLang.
3.3 REVERSIBLE CONTROL FLOWS
One can define reversible if, for and while statements in a reversible program. Fig. 2 (a) shows the flow chart of executing the reversible if statement. There are two condition expressions in this chart, precondition and a postcondition. The precondition decides which branch to enter the forward execution, while the postcondition decides which branch to enter in the backward execution. The pseudo-code for the forward and backward passes are shown in Listing. 7 and Listing. 8.
Listing 7: Translating reversible if state-
Listing 8: Translating reversible if state- ment (backward)
ment (forward)
branchkeeper precondition
branchkeeper postcandition if postcondition
if precondition
branch
-(branch
else
else
branch
~(branch
and
end
assert branchkeeper
postcondition
assert branchkeeger == precondition
Fig. 2 (b) shows the flow chart of the reversible while statement. also has two condition expressions. Before executing the condition expressions, the program presumes the postcondition false. After each iteration, the program asserts the postcondition to be true. To reverse this statement, one exchange the precondition and postcondition, and reverse the body statements. The pseudo-code for the forward and backward passes are shown in Listing. 9 and Listing. 10.
Listing Translating a reversible while statement (forward)
Listing 10: Translating a reversible while statement (backward)
postconditian
assert precondition while postcondition
ubile precondition loog body
-(loop body)
assert postcondition
assert precendition
end
end
The reversible for statement is similar to the irreversible one except that after execution, the program will assert the iterator to be unchanged. To reverse this statement, exchange start and stop and inverse the sign of step. Listing. 11 computes the Fibonacci number recursively and reversibly.

---

Under review as a conference paper at ICLR 2021
Listing 11: Computing Fibonacci number recursively and reversibly.
81 function refib n)
@invcheckoff (L >= 1, -)
+ 0
counter += n
while (counter' counter!=a) rafib counter-1)
counter
end
counter - n. %
counter
end and
Here, out! is an integer initialized to for storing outputs. The precondition and postcondition are wrapped into a tuple. the if statement, the postcondition is the same as the precondition, hence we omit the postcondition by inserting a "~" in the second field for "copying the precondition in this field as the postcondition". In the while statement, the postcondition is true only for the initial loop. Once code is proven correct, one turn off the reversibility check by adding @invcheckoff before a statement. This will remove the reversibility check and make the code faster and compatible with GPU kernels (kernel functions can not handle exceptions).
4 REVERSIBLE AUTOMATIC DIFFERENTIATION
4.1 BACK PROPAGATION
.T' 0y i; 0%
original program O
gradient program for
compute
reverse
reverse
reverse program R
gradient program for R
We decompose the problem of reverse mode AD into sub-problems, reversing the code and Alsingle input]
computing Ammutiple outpurs] Reversing the code trivial in reversible programming. Computing the gradient here is similar to forward mode automatic differentiation that computes @imultipl oupputs] Aisingle inpui]
Inspired by the Julia package ForwardDiff (Revels et al., 2016), we use the operator overloading technique differentiate the program efficiently. In the backward pass, wrap each output variable with composite type GVar that containing an extra gradient field, and feed it into the reversed generic program. Instructions instructions that update the gradient field GVar at the meantime of uncomputing. By reversing this gradient program, define the adjoint ("adjoint" here means the program for back poockpropggating gradients) of a primitive instruction reversible function on either the function itself its reverse since the adjoint of function's 's reverse is equivalent to the reverse of the function's 's adjoint.
multiple dispatched to corresponding gradient
obtain the gradient program for the reversed program too. One can
f:(t.g)) G8.g 0x
(3)
05
f' (.. गर
(4)
It can be easily verified by applying the above two mappings consecutively. which turns out to be an identity mapping considering 89 ar 1.
07

---

Under review as a conference paper at ICLR 2021
The implementation details described in Appendix C. In most languages, operator overloading accompanied with significant overheads of function calls and object allocation and deallocation. But in language with type inference and just in time compiling like Julia, the boundary between two approaches are vague. The compiler inlines small functions, packs an array of constant sized immutable objects into continuous memory, and truncates unnecessary branches automatically.
4.2 HESSIANS
Combining forward mode AD and reverse mode AD is simple yet efficient way to obtain Hessians. By wrapping the elementary type with Dual defined package ForwardDiff and throwing into the gradient program defined in NiLang, one obtains one row/column of the Hessian matrix. We will use this approach to compute Hessians in the graph embedding benchmark Sec. D.2.
4.3 CUDA KERNELS
CUDA programming is playing significant role in high perffrreffrmecc computing. In Julia, one write GPU compatible functions in native Julia language with KermelAbstractions. (Besard et al., 2017) Since NiLang does not push variables into stack automatically for users, it is safe write differentiable GPU kernels with NiLang. We will differentiate CUDA kernels with no more than extra 10 lines in the bundle adjustment benchmark in Sec. 5.
5 BENCHMARKS
We benchmark our framework with the state-of-the-art GP-AD frameworks, including source code transformation based Tapenade and Zygote and operator overloading based ForwardDiff and ReverseDiff. Since most tensor based AD software like famous TensorFlow and Py PyTorch are not designed for the using cases used in our benchmarks, we do not include those package to avoid an unfair comparison. In the following benchmarks, the CPU device is Intel(R) Xeon(R) Gold 6230 CPU @ 2.10HHz and the GPU device is NVIDIA Titan V. For NiLang benchmarks, we have turned the reversibility check off to achieve better performance.
We reproduced the benchmarks for Gaussian mixture model (GMM) and bundle adjustment in Srajer et al. (2018) by re-writing the programs in a reversible style. We show the results in Fig. 3. The Tapenade data is obtained by executing the docker file provided by the original benchmark, which provides baseline for comparison.
Gaussian Mixture Model
Bundle Adjustment
10?
101
Julla-O
seconds
NiLang-O
10
10-1
Tapenade-O
ForwardDiffJ
NilangJ
Tapenade-J
10-2
10-3
NiLangJJ (GPU)
103
105
105
105
107
parameters
parameters
Figure 3: Absolute runtimes in seconds for computing the objective (-O) and Jacobians (-J). (a) GMM with 10k data points, the loss function has a single output, hence computing Jacobian the same computing gradient. ForwardDiff data is missing due to not finishing in limited time. The NiLang GPU data is missing because we do not write kernel here. (b) Bundle adjustment.
NiLang's objective function is ~2x slower than normal code due to the uncomputing overhead. In this case, NiLang does not show advantage to Tapenade obtaining gradients, the ratio between computing the gradients and the objective function are close. This is because the bottleneck of this
8

---

Under review as a conference paper at ICLR 2021
(64, 200
106
(64,
105
(64, 10
peak memory
(64, S)
(10, 50
104
12, 200
(10, 5
10
regular
102 (2,
reversible
10
10
10
10
# of parameters
Figure 4: Peak memory of running the original and the reversible GMM program. The labels are (d, k) pairs.
model is the matrix vector multiplication, traditional AD can already handle this function well. The extra memory used to reverse the program is negligible comparing to the original program as shown in Fig. 4. The backward pass is not shown here, it is just two times the reversible program in order to store gradients. The data is obtained by counting the main memory allocations in the program manually. The analytical expression of memory usage in unit of floating point number is
= (2 (2 2d
(5)
s, (3 + di d)k + 2log,k +
(6)
where d and are the size and number of covariance matrices. P did=1l k k + dk is the size of parameter space. The memory of the dataset (dxN) is not included because it will scale as N. Due to the hardness of estimating peak memory usage, the Tapenade data is missing here. The ForwardDiff memory usage is approximately the original size times the batch size, where the batch size is 12 by default.
In the bundle adjustment benchmark, NiLang performs the best on CPU. We also compiled our adjoint program to GPU with no more than 10 lines code with KermelAbstractions, which provides another ~200x speed up. Parallelizing the adjoint code requires the forward code not reading the same variable simultaneously in different threads, and this requirement is satisfied here. The peak memory of the original program and the reversible program both equal to the size of parameter space because all "allocation', 's happen on registers in this application.
One can find more benchmarks in Appendix D, including differentiating sparse matrix dot product and obtaining Hessians in the graph embedding application.
6 DISCUSSION
In this work, we demonstrate a new approach to back propagates a program called reverse computing AD by designing reversible eDSL Nil.ngg. Nil is a powerful tool differentiate code from the source code level so that can be directly useful to machine learning researches. can generate efficient backward rules, which is exemplified in Appendix E. It can also be used differentiate reversible neural networks like normalizing flows (Kobyzev et al., 2019) to save memory, e.g. back- propagating NICE network (Dinh et al., 2014) with only constant space overheads. NiLang is most useful in solving large scale scientific problems memory efficiently. In Liu et al. (2020), people solve the ground state problem of 28 28 square lattice spin-glass by re-writing the quantum simulator with NiLang. There are some challenges in reverse computing AD too.
The native BLAS and convolution operations in NiLang are not optimized for the memory layout, and are too slow comparing with state of the art machine learning libraries. We

---

Under review as a conference paper at ICLR 2021
need better implementation of these functions in the reversible programming context so that it can be more useful in training traditional deep neural networks.
Although we show some examples of training neural networks on GPU, the shared-reading of variable is not allowed.
NiLang's 's IR does not have variable analysis. The uncomputing pass is not always necessary for the irreversible host language to deallocate memory. In many cases, the host language's variable analysis can figure this out, but it guarantted.
Another interesting issue is how to make use of reversible computing devices save energy in machine learning. Reversible computing is not always more energy efficient than irreversible computing. the time-space trade-off scheme in Sec. 2, we show the time to uncompute unit of memory is exponential to as Qa (2k 1y", and the computing energy also increases exponentially. On the other side, the amount of energy erase unit of memory is a constant. When (2k 1y" 1/5, erasing the memory irreversibly is more energy-efficient, where & is the energy ratio between reversible operation (an instruction or a gate) and its irreversible counterpart.
ACKNOWLEIGMENT
The authors grateful the people who help improve this work and fundings that sponsored the research. To meet the anonymous criteria, we will add the acknowledgments after the open review session.
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg. Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL https: rensorflow www.sor.woooorr////ooooo Software available from tensorflow.org.
Jens Behrmann, David Duvenaud, and Jöm-Henrik Jacobsen. Invertible residual networks. CoRR, abs/1811.000 100995 2018. URL http:/// httppp////arrio.o/abb/////// www.////////..//////////
Charles H. Bennett. Logical reversibility of computation. 1973. URL https://ieeexplore.
ieee. gree.org/aee aiiceoorg/bbstrccee /ttp///stracc/bocmee////999
Charles H. Bennett. Time/space trade-offs for reversible computation. SIAM Journal on Computing, 0t1.://///01111100101000055
18(4):766-776, 1989. doi: 10.1137/021805, URL
Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, M. Sohaib Alam, Shahnawaz Ahmed, Juan Miguel Arrazola, Carsten Blank, Alain Delgado, Soran Jahangiri, Keri McKiernan, Johannes Jakob Meyer, Zeyue Niu, Antal Száva, and Nathan Killoran. Pennylane: Automatic differentiation of hybrid quantum-classical computations, 2018. URL https://arxiv. org/ abs/1811. 04968.
Tim Besard, Christophe Foket, and Bjorn De Sutter. Effective extenssble programming: Unleashing julia on gpus. CoRR, abs/1712.031 2017. URL http::/aazzivoor//
03112.
Jeff Bezanson, Stefan Karpinski, Viral B. Shah, and Alan Edelman. Julia: A fast dynamic language technical computing, 2012. URL
5145.
Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B. Shah. Julia: A fresh approach to numerical computing. SIAM Review, 59(1) Jan 2017. ISSN 1095-7200. doi: 10.1137/ 141000671. URI. http://d/ doi. arg/10.
10

---

Under review as a conference paper at ICLR 2021
Tianqi Chen, Bing Xu, Chiyuan Zhang, and Carlos Guestrin. Training deep nets with sublinear memory cost. CoRR, abs/1604.061744, 2016. URL
06174.
Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: Non-linear independent components estimation, 2014. URL httpt: wwtexii.orrgabb////// 8516.
GAEL Foret, J-M Campin, Patrick Heimbach, Christopher N Hill, Rui M Ponte, and Carl Wunsch. Eeco version An integrated framework for non-linear inverse modeling and global ocean state estimation. 2015. URL htt.hhttt////peee .mmtt www.mmitt.......mmmmmmmmmm
1/99660.
Michael P Frank. The programming language and compiler. Technical report, MIT Reversible Computing Project Memo, 1997.
Michael P. Frank. Throwing computing into reverse. IEEE Spectrum, 54(9):32-37, Sep 2017. ISSN 0018-9235. doi: 10.100//mpp:22177881223333 URL http://dxx.do doi oaril.rrg/110 1T9/10..109/MSPEC. 2017.8012237
Michael Patrick Frank and Thomas F Knight Jr. Reversibility for efficient computing. Phl) thesis, 1999. URL http://citesserx. iitpserrx.ist.ssu.... httpssrr......sss..c///iieoor//s 428. -90.2222rrp-reepttpp---...
1.1..
Gene H Golub and Charles F Van Loan. Malrix computations, volume 3. JHU press, 2012.
Aidan N Gomez, Mengye Ren, Raquel Urtasun, and Roger B Grosse. The reversible residual network: Backpropagation without storing activations.
In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp- 2214-2224. Curran Associates, Inc., 2017. URL http: http://papers... miis..ipp.............. cttppp...cppe//////ppp/pppp 1-16-the-revee retterrrveessbbleeeee reserssbe----r-rriillll--l neewwrkk--etooo---oo beskk--bacppopgattoon thout- strring-accttattiinss activations. pdf.
Andreas Griewank. Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation. Optimization Methods and software, 1(1):35-54, 1992. URL https:
//www. tawdfollloo ine. com/doi/abll a1s/10....101/////////..// 1980/10556789208855000
Andreas Griewank and Andrea Walther. Evaluating derivatives: principles and techniques of algorithmic differentiation. SIAM, 2008
Jin-Guo Liu Hao Xic and Lei Wang. Automatic differentiation of dominant eigensolver and its applications in quantum physics. URL httpttts///aaae http://aaxiv..or//////////////// 04121.
Laurent Hascoet and Valérie Pascual. The tapenade automatic differentiation tool: Principles, model, and specification. ACM Transactions on Matherattial Softwre (TOMS), 39(3):20, 2013. URL
https://dl. acm. www.loggggg..eeeeeeee www.ttit.tticccm.oomooo.... cfw..nd-21dmdddddd5555 otg
Tue Haulund. Design and implementation of reversible object-oriented programming language,
2017. URL htthh::t///// //tps::////xvvv/ org//bb/1117/ httpss//arrxvv.orr/a//////// 07745485577.8
Claudius Hubig. Use and implementation of autodifferretiiation in tensor network methods with
complex scalars, 2019. URL
wrg//bs////// 13422.
Michael Innes. Don't unroll adjoint: Differentiating ssa-form programs, 2018. URL https://
arxiv. serrv.org/abs//811e 07951.
Michael Innes, Elliot Saba, Keno Fischer, Dhairya Gandhi, Marco Concetto Rudilosso, Neethu Mariya Joy, Tejan Karmali, Avik Pal, and Viral Shah. Fashionable modelling with flux, 2018. URL https:://axi:: wwwpxiivoogg/abaee htsp/bbs/181111 01457.
Mike Innes, Alan Fdelman, Keno Fischer, Christopher Rackauckas, Elliot Saba, Viral B. Shah, and Will Tebbutt. differentiable programming system to bridge machine learning and scientific computing. CORR, abs/1907.07587, 2019. URL
haw.a////99...777 07587.
Li Jing, Yichen Shen, Tena Dubcek, John Peurifoy, Scott Skirlo, Yann LeCun, Max Tegmark, and Marin Soljacić. Tunable efficient unitary neural networks (cunn) and their application to rnns, 2016. URL. https: www.:/rgg//bb/....... 65231

---

Under review as a conference paper at ICLR 2021
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. URL https: //arxiv. www.voorg/aaoe aaaaabss1122 1112. 6980.
Ivan Kobyzev, Simon Prince, and Marcus A. Brubaker. Normalizing flows: An introduction and review current methods, 2019.
J. G. Koller and W. C. Athas. Adiabatic switching, low energy computing, and the physics of storing and erasing information. Workshop on Physics and Computation, pp. 267-270, Oct 1992. doi: URL https:/ /ttess///eeeeeporeeeeeeee ieee org www.:oogg///oooooeeee document/611555
Rolf Landauer. Irreversibility and heat generation the computing process. IBM journal of research and development, 5(3):183-191, 1961. URL https://ieeexplorr ieee. org/ /ocument/////////////// 5392446.
Ivan Lanese, Naoki Nishida, Adrián Palacios, and Germán Vidal. A theory of reversibility for erlang. Journal of Logical and Algebraic Methods Programming. 100:71-97, Nov 2018. ISSN 2352-2208. doi: 11..1166..lmmp22188000000 j.jlamp. 2018. 06. 004.
URL http://dx.don wwt.:doo....g.11111
Robert Y Levine and Alan T Sherman. A note bennett's time-space tradeoff for reversible computation. SIAM Journal on Computing, 19(4)667-6777, 1990. URL https//::/seus siam. org/doi/abs/19 10.
Hai-Jun Liao, Jin-Guo Liu, Lei Wang, and Tao Xiang. Differentiable programming tensor networks. Physical Review X, 9(3), Sep 2019. ISSN 2160-3308. doi: 10.1 10.100//yyysrexx...03100 URL
http://dxx doi. org/10 11000..111/111111 1103/PhysRevks ..t.ovx...0011.. 031041
K. Likharev. Dynamics of some single flux quantum devices: I. parametric quantron. IEEE Transactions on Magnetics, 13(1):242-244, January 1977. ISSN 1941-0069. doi: 10.1
TMAG. 1MAGG.977.10553551. URL httpt:://eeeeeplorrttt iere. www.ooocgggg////tooe.oo/
Jin-Guo Liu, Lei Wang, and Pan Zhang. Tropical tensor network for ground states of spin glasses, 2020. URL http:::/t/:/aatt
orgo arg/abs/2008. 66888
Xiu-Zhe Luo, Jin-Guo Liu, Pan Zhang, and Lei Wang. Yao.jl: Extensible, efficient framework for quantum algorithm design, 2019. URL https://arxxi https//////xvv.o.o/a/bbe httg/bbs/1912. 1097777777..
Christopher Lutz. Janus: a time-reversible language. Letter to Landauer. 1986.
Matthew MacKay, Paul Vicol, Jimmy Ba, and Roger B Grosse Reversible recurrent neural networks. In S. Bengio, Wallach, Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 9029-9040. Curran Associates, Inc., 2018. URL http://papers hwtppppprs.iiss....peppp.pp cc/paper/ pdf..
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter opti- mization through reversible learning. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 Proceedings of Machine Learning Research, pp. 2113-211111 11222, Lille, France, 07-09 Jul 2015. PMLR. URL http://proceedings. mlr. www.ppreesv..... ht////maaaaannnnn/ /tt.a//.....eee///m//amaaaaaaaa html.
Ralph C. Merkle, Robert A. Freitas, Tad Hogg, Thomas E. Moore, Matthew S. Moses, and James Ryley. Mechanical computing systems using only links and rotary joints. Journal of Mechanisms and Robotics, 10(6), Sep 2018. ISSN 1942-4310. doi: 14441///4 URL http: / //xx. doi. iaii.rg//1 2tg/10.111 1.1.1111/.444129.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS Autodiff Workshop, 2017. URL http:://penreriew...ee/// wwwpiareveiiiineeffrueeee B]JsrmfCZ.
Kalyan S Perumalla. Introduction to reversible computing. Chapman and Hall/CRC, 2013.
12

---

Under review as a conference paper at ICLR 2021
David Reeb and Michael M Wolf. An improved landauer principle with finite-size corrections. New Journal of Physics, 16(10):00001, 2014. URL https://iopscience www.eeip........................ wwweeeippppo..o.eeeeeeee wwwp:org//arie aaggarrtile/ 10. 1008 (136776630/1665 1111/////1/11/11001/1//////
Jarrett Revels, Miles Lubin, and Theodore Papamarkou. Forward-man mode automatic differentiation in julia, 2016. URL htt.http/:aaree http///axiii.oora/////////// .08892.
Chase Roberts, Ashley Milsted, Martin Ganahl, Adam Zaleman, Bruce Fontaine, Yijian Zou, Jack Hidary, Guifre Vidal, and Stefan Leichenauer. Tensornetwork: A library for physics and machine learning, 2019. URL https: htttps://axxiv..et org. wttp.//9.rgaaa/110..0111
Matthias Seeger, Asmus Hetzel, Zhenwen Dai, Eric Meissner, and Neil D. Lawrence. Auto- differentiating linear algebra, 2017. URL https://arxxv.org/abbb 07710
V. K. Semenov, G. Danilov, and D. V. Averin. Negative-indductance squid the basic element of reversible josephson-junction circuits. IEEE Transactions on Applied Superconductivity, 13 (2):938-945) 9438, June 2003. ISSN 2378-7074. doi: 10.1109/TASC.2003...M / //ieeexplore ieeeeerrreeeeeeeeee..ooo.oo org/ http//mmmme///11766
URL https:
Yan Shen and Yuxing Dai. Fast automatic differentiation for large scale bundle adjustment. IEEE Access, 1111146-1153, 2018. URLhttps::/ieeexplorr ieee. htt..//bstaat///ocmmeeeeeo 8307241/.
David Speyer and Bernd Sturmfels. Tropical mathematics. Mathematics Magazine, 82(3):163- 173. 2009. URL https://wwi tandfonline. 11953615.
http://o//pp//11.10////0/// http::://ww.taadoooiirr
Filip Srajer, Zuzana Kukelova, and Andrew Fitzgibbon. A benchmark of selected algorithmic differentiation tools on some problems computer vision and machine learning. Optimization Methods and Software, (1(4-6):889-900) 2018. URL https:::///peeerreiie www.neeforrrm?.
SMCWZL2TGDN.
Jun Takahashi and Anders W. Sandvik. Valence-bond solids, vestigial order, and emergent so(5) symmetry in two-dimensional quantum magnet, 2020. wtt.https://arxiv.oott //tr///v....r//a//0000.. 10045.
N Takeuchi, Y Yamanashi, and N Yoshikawa. Reversible logic gate using adiabatic superconducting
devices. Scientific reports, 4:6354, 2014. URL https:/ hopps://www http:/ttwwwwtttt////t/tt////.. com.articcmm//tt srep06354.
Naoki Takeuchi, Yuki Yamanashi, and Nobuyuki Yoshikawa. Reversibility and energy dissipation in adiabatic superconductor logic. Scientific reports, 7(1):1-12, 2017. URL httpp://wwis nature. nature.com/artic www.ureeccmmaatrleseessseeee
017-00089-9.
Clay S Turner. fast binary logarithm algorithm [dsp tips tricks]. IEEE Signal Processing Mag- azine, 1745):1441140, 2010. URL http:///www.lllsstrreeeere www.uuuee.......eeeeeeeeeeeeeeee cww/dsp/ comm/dsp/iinayylggriit pdf.
Jean Utke, Uwe Naumann, Mike Fagan, Nathan Tallent, Michelle Strout, Patrick Heimbach, Chris Hill, and Carl Wunsch. Openad/f: A modular open-source tool for automatic differentiation of fortran codes. ACM Trans. Math. Softw., 34(4), July 2008. ISSN 0098-3500. doi: 10.1145/ 1377596.1377598. URL https:/:://oo www.orgg//// 10. /155//117796... 1377598.
Zhou-Quan Wan and Shi-Xin Zhang. Automatic diffcrentiation for complex valued svd, 2019, URL https://arxiv.ot wrg. htagg/abs/19000 02659.
Weiqiang Zhu, Kailai Xu, Eric Darve, and Gregory C. Beroza. A general approach to seismic inversion with automatic differentiation, 2020. URL https/////avv...aaa//ssss/s 06027.
13

---

Under review as a conference paper at ICLR 2021
A
NILANG IMPLEMENTATION OF BENNETT'S TIAE- OFF ALGORITHM
Listing 12: NiLaag implementation of the Bennett's time-space trade-off scheme.
using KiLang, Test
PROG, COUNTER = Ref(O) (2
PEAK_MEN Ref(O)
n*(k-1)+2
01 function :emnett((::bssttaeeeecoo. state::Dictt(Int,]] k::Int, base, len) where T
if (len
state[basee1] - zero(T)
f[base] (sttte]sstatt state[base])
Osafe
+=
(length(state) PEAK_MEM[] (PEAK_NEM[] length(state)))
else
n lensk
# the P pracess
for j=l:k
bennett state, k, base=n"(j-1),
# the Q process
for j=k-1:-1:1
(ennettt state, Maseen"(j-D), end
lenek
end
state 1ict(1=>1.4)
f(X) = 2.0
instructions (11)()usE
the program Binstr bemmet((instraction) state, k, 1, N)
Stest state[N-1] 2.8*N & length(state) == 2
ōtest PEAK_ MEX(] n (k))) +
Otest PROG PROG_ COUNTER[] (2*k-1)*n
The input f is vector of functions and state is dictionary. We also added some irreversible external statements (those marked with @safe) to help analyse to program.
B CASES WHERE REVERSE COMPUTING SHOWS ADVANTAGE
B.I HANDLING EFFECTIVE CODES
Reverse computing can handling effective codes with mutable structures and arrays. For example, the affine transformation can be implemented without any overhead.
14

---

Under review as a conference paper at ICLR 2021
81 function Listing 13: Inplace affine transformation.
W::hbstracthatrik()), b:::bstraccteccor(())
AbbstractVector(TT) where
Osafe @assert size(M) (length(y!), length(x)) & length(b) length(y!)
@invcheckoff for j=1:size(K, 2)
i-
Binhounds y!] += [[i]
end
Oinvcheckoff for i=1:size(M, 1)
Oinhounds y! b[i]
end
end
Here, the expression following the @safe macro is an external irreversible statement.
B.2 UTILIZING REVERSIBILITY
Reverse computing can utilize reversibility trace back states without extra memory cost. For example, we can define the unitary matrix multiplication that can be used in type of memory- efficient recurrent neural network. (Jing al., 2016)
Listing 14: Two level decomposition of unitary matrix.
01 function 1 umm! (x! :bbstractrrrr,, 6 size(x!. 1)
size(x!, 2)
@safe @assert length(#) == H²(-1)/2
for j=1:8
for 1=N-1:-1:f
IXC
[i, xl[i+1,1], A[K))
and
end
(e)
end
B.3
ENCOURAGES REVERSIBLE THINKING
Last but not least, reversible programming encourages users code in memory friendly style. Since allocations in reversible programming are explicit, programmers have the flexibility to control how to allocate memory and which number system use. For example, compute the power of positive fixed-point number and an integer, one can easily write irreversible code as in Listing. 15
Listing 16: A reversible power function.
ai function mypover(out, x:: :In) where T
Listing 15: A regular power function.
Groutine begin
1y one ((Logarithiicc(T))
function (x:over(x::T, n: I::Int) where T
Ix one (ULoggaiithmie(())
y one(T) for Sel:n y += x end return end
1x convert (x) for i=l:n ly +
end
out + convert(ly)
~Broutine
end
end
15

---

Under review as a conference paper at ICLR 2021
Since the fixed-point number is not reversible under *=, naive checkpointing would require stack operations inside a loop. With reversible thinking, we can convert the exeed-point number to logarithmic numbers utilize the reversibility of *= shown in Listing. 16. Here, the algorithm to convert a regular fixed-point number to a logarithmic number can be efficient. (Turner, 2010)
C IMPLEMENTATION OF AD IN NILANG
To backpropagate the program, we first reverse the code through source code transformation and then insert the gradient code through operator overloading. If we inline all the functions in Listing. 6, the function body would be like Listing. 17. The automatically generated inverse program (i.e. (y,x) (y log(x). x)) would be like Listing. 18.
Listing 17: The inlined function body of Listing.
Listing 18: The inverse of Listing. 17.
@routine begin
Oroutine begin
nsq + zero(T)
nsq zTro(T)
zero(T)
zero(1)
+= x[1] .re ^
nsq += x[i] .re
nsq += x[i]
nsq sqrt(ssq)
(nsq)
end
yi[i].re log(n)
[riierr log(n)
y! [im -= atan(x(i) im, x(i].re)
yt [i] += atan(x(3].in,, x(i].re)
-Groutine
-Broutine
To compute the adjoint of the computational process in Listing, 17, one simply insert the gradient code into its inverse in Listing. 18. The resulting inlined code is show in Listing. 19.
Listing 19: Insert the gradient code into Listing. 18, the original computational processes are highlighted in yellow background.
xnrt(nsq.x) -8zeros ra rb
@routine begin
nsq zero(GVar(TTT))
(GVa
(nsq.
end
gsqa zero(T)
gaqa += x[i] re.
yl re.x log(n.x)
rri].re.g gsqa nsq-g
n.g (ii).rr..
nsq. 5
gsqa - x[i] re.
gsqa zero(T)
nsq.x += x(i] re.x +2
jac_x jac_y
xy2 + abbs(x(1).rre..
abs2(x[i] (n..).)
g5gb zero(T)
jac_y += x[i] xy2
gsqb += x(i] iim.x
jac_x (-x[i]. in.x) xy2
x[i].in .n.g gsqb usq.9
x[i].in.g y! [i].int in.. jac_y
gsgb - x[i] .im.x
x[i] re.g. yl [i].in. in. jac_x
gsqb zero(T)
jac_x (-x[i) in..x) xy2
a += xii]-in.x in.x *2
jac y -= xxi]]_e.x / XY2
xy2 abs2[x[3] in.
ézeros rb 2))Q()) += ra
xy2 - abs2(x(3] re.
-zeros xy2 jac_x jac_y
nsq.g n.g rb - 2 ra
rroutine
Here, @zeros TYPE varl var2... is the macro to allocate multiple variables of the same type. Its inverse operations starts with ~0zeros deallocates zero emptied variables. In practice, "inserting gradients" is not achieved by source code transformation, but by operator overloading. We change the element type to composite type GVar with two fields, value x and gradient g. With multiple dispatching primitive instructions this type, values and gradients be updated simultaneously. Although the code looks much longer, the computing time (with reversibility check closed) is not.
16

---

Under review as a conference paper at ICLR 2021
Listing 20; Time and allocation to differentiate complex valued log.
julias using KiLang, NiLang.AD, BenchmarkTools
julias éinline function end
1x)(abs(x)) in=angle(x)
juliaz obtine ir ir_lag(x) setup- (x-1.8e1.2in) native code
30.097 allocations: bytes)
julias
obtine (Binstr y log(x)) setup=(r-1.011.2ing y=0.8-0.0im) reversible code
17.542 allocations: bytes)
juliaz obtine (Binstr log(x))) setup=(xedVarr1..011... 0.0r0.8im); 1..Var(0.1+0..2
(.0:0.0im)). adjoint code
allocations: bytes)
The performance unreasonably good because the generated Julia code is further compiled to LLVM that it can enjoy existing optimization passes. For example, the optimization passes can find out that for an inreversible device, uncomputing local variables n and nsq to zeros does not affect return values, that it will ignore the uncomputing process automatically. Unlike checkpointing based approaches that focus a lot in the optimization of data caching on global stack, Nilang does not have any optimization pass in itself. Instead, it throws itself to existing optimization passes in Julia. Without accessing the global stack, NiL.nngss code is quite friendly to optimization passes. In this case, also the boundary between source code transformation and operator overloading can be vague in a Julia, in that the generated code can be very different from how it looks.
The joint functions for primitive instructions (:+=) (sqrt) and (:-=) (sqrt) used above can be defined as in Listing. 21.
Listing 21: Adjoints for primitives (sqrt) and (: (:==) (sqrt).
8i Ginline function (sg=) (out!::GVar, xT)GVa((T) where Broutine @invcheckoćf begin
+ (x.x)
b +=
end out - X.g out!.g --Broutine
D
MORE BENCHMARKS
D.I SPARSE MATRICES
We compare the call, uncall and backward propagation time used for sparse matrix dot product and matrix multiplication in Table 2. Their reversible implementations are shown in Listing. 22 and Listing. 23. The computing time for backward propagation is approximately 1.5-3 times the Julia's native forward pass, which is close the theoretical optimal performance.
17

---

Under review as a conference paper at ICLR 2021
Listing 22: Reversible sparse matrix multiplication.
using SparseArrays
;r: A::Sarseeaarricss(()) Spr.spppppatttttccccCCC http://rrrrrttt......pirrrrrrrrn
(T)
+- (A,e 1)
size 2)
@invcheckoff branch_keeper (erol 2*m)
#safe size(H) =- (n,n) || throw(Uinensi ontii must have the same
dimensions"))
@invcheckoff Sinbounds for 1:n
ial A.colptr[i]
ibl B.colptr(j]
ia2 - A.coIpte[j+1]
ib2 B.colptr[j+1]
ia - ial
ib1
Oinbounds for 1=1::n2--al--b2--I11-
ra A.rowval [ia]
[ibb
(ra == rb, ~)
A.nzval [ia]' B.nzval
end
true,
Brranch_keeperfee y= la == ia2-1 II (ib 1= 1b2-1 & ra rb)
rа A.rowval [ia]
B.rowval [ib]
(branch -)
IKC(ib)
else
INC(1a)
end end
Sinbounds for i=1:ia2-ial-ib2-i1
# move - true, a move >> false
keeper))) Y= ia2-1 (ib ib2-1 A.rowva [ib]) 1f (branch keeper[i], -) INC(ib)
else IXC(ia)
and end
Oinvcheckoff branch keeper - zeros (Baol, 2*m)
end
Listing 23: Reversible sparse matrix dot-product.
0i function i_mal (C:rrrrdedirriide A: S:AbstrractSppasetttrii, B: B:sStridedVectorrT)) a:: Number, :unbbr)rr) where
#safe size(A, 2) size(B, 1)
throw (Wwneniiionnniiinaaeeeeeeee ())tchh)
Osate size(A, = size(C, 1)
throw (Dimensionnil snatchh
@safe size 2) size(C, 2) nzv - nonzeros(A)
throw (Dimensioniii smatch()
rowvals(A)
if 1= 1=
esafe error("only 8 is supported, got = $(8).") end
Here, we close the reversibility check inside the loop to increase perfornance @invcheckoff for 1:size @inbounds for col 1:size(A, 2)
exi
exj += B[col,k] +
for =
Clev[j]. + nev end
B[col,k] +
end
end
18

---

Under review as a conference paper at ICLR 2021
dot
mul! (complex valued)
Julia-O
3.493e-04
8.005e-05
NiLang-O
4.675e-04
9.332c-05
NiLang-B
5.821e-04
2.214c-04
Table 2: Absolute runtimes in seconds for computing the objectives (O) and the backward pass (B) of sparse matrix operations. The matrix size is 1000 x 1000, and the element density is 0.05. The total time for computing gradients be estimated by summing "O" and "B".
5
10
8
Figure 5: The Petersen graph has 10 vertices and 15 edges. We want to find a minimum embedding dimension for it.
D.2 GRAPH EMBEDDING PROBLEM
Graph embedding can be used to find proper representation for an order parameter (Takahashi & Sandvik, 2020) in condensed matter physics. People want to find a minimum Euclidean space dimension & that a Petersen graph can embed into, that the distances between pairs of connected vertices are 4, and the distance between pairs of disconnected vertices are l2, where 12 4. The Petersen graph is shown in Fig. 5. Let us denote the set of connected and disconnected vertex pairs L, and 12, respectively. This problem be variationally solved with the following loss.
L Var(dist(L;)) Var(dist(L2))
+ expírelu(dis((L,) dist(L2) + 0.1)))
The first line is a summation of distance variances in two sets of vertex pairs, where Var(X) is the variance of samples in X. The second line is used to guarantee l2 > (1, where X means taking the average of samples in X. Its reversible implementation could be found in our benchmark repository.
We repeat the training for dimension & from to 10. In each training, we fix two of the vertices and optimize the positions of the rest. Otherwise, the program will find the trivial solution with overlapped vertices. For < the loss is always much higher than while for k 2 5, we can a loss close to machine precision with high probability. From the & = 5 solution, it is easy to see 1/4 = v2. An Adam optimizer with learning rate 0.01 (Kingma & Ba) requires ~2000 steps training. The trust region Newton's method converges much faster, which requires ~20 computations of Hessians to reach convergence. Although training time is comparable, the converged precision of the later is much better.
Since
combine ForwardDiff and NiLang to obtain Hessians, it is interesting how much performance we can get in differentiating the graph embedding program.
In Table 3, show the the performance of different implementations by varying the dimension k. The number of parameters is 10k. As the baseline, (a) shows the time for computing the function call. We have reversible and irreversible implementations, where the reversible program is slower
19

---

Under review as a conference paper at ICLR 2021
k
2
4
6
10
Julia-O
4.477c-06
4.729c-06
4.959c-06
5.196c-06
5,567c-06
NiLang-O
7.173e-06
7.783e-06
8.558e-06
9.212e-06
1,002e-05
NiLang-U
7.453e-06
7.839e-06
8.464c-06
9.298e-06
1.054e-05
NiLang-G
1.509e-05
1.690e-05
1.872e-05
2.076c-05
2.266e-05
ReverseDiff-G
2.823e-05
4.582e-05
6,045e-05
7.651e-05
9.666e-05
ForwardDiff-G
1.518e-05
4.053e-05
6.732e-05
1.184c-04
1.701c-04
Zygote-G
5.315c-04
5.570c-04
5.81 le-04
6.096c-04
6,396c-04
(NiLang+F)-H 4.528c-04
1.025e-03
1.740c-03
2.577c-03
3.558c-03
ForwardDiff-
2.378c-04
2.380c-03
6.903e-03
1.967c-02
3.978c-02
(ReverseDiff-F--H
1.966e-03
6.058e-03
1.225e-02
2.035e-02
3,140e-02
Table 3: Absolute times in seconds for computing the objectives (O), uncall objective (U), gradients (G) and Hessians (H) of the graph embedding program. k is the embedding dimension, the number of parameters is 10k.
than the irreversible native Julia program by factor of ~ due the uncomputing overhead. The reversible program shows the advantage of obtaining gradients when the dimension k 2 3. The larger the number of inputs, the more advantage shows due to the overhead proportional input size in forward mode AD. The same reason applies to computing Hessians, where the combo of NiLang and Foff gives the best performance for k 3.
PORTING NILANG TO ZYGOTE
Zygote is popular machine learning package in Julia. We port NiLang's automatically gener- ated backward rules to Zygote to accelcrate some performance-critte functions. The following ex- ample shows how speed up the backward propagation of norm by ~5 times.
20

---

Under review as a conference paper at ICLR 2021
Listing 24: Porting NiLang to Zygote.
julias using Zygote, NiLang, NiLang.AD. BenchnarkTools, LinearAlgebra
julias randn (1000);
julia> Obenchmark norm' (X)
BenchnarkToals, Trial:
Trial:
nenory estimate: 339.02 Ki8
allocs estimate:
8883
minimu time:
228.967 μus (0.00% GC)
medi tine:
237.579 (0.00% GC)
mean time:
277.682 jus (12.06% GC)
maximun time:
5.552 (94.00% GC)
samples: evals/sample:
julia> function nor out2::T, k::abstractdrray(T) where for i=1: i=1:1ength(()
@inbounds out x[3]^2
end end
sqrt(out2)
julia> Zygote. Gadjoint function norm(x: :dbstractárray((T) where compute the forward with regular norn (might be faster) norm(x)
compute the backward with Milang's norn, element type is GVar out, (grad((-r norn) (out, (out (Var(x)) (31).)
end
julia> Obenchmark norm' (x)
BenchmarkTools Trial:
nenory
23.69
allocs estimate:
2
minimum time:
4.015 ju (0.80% 6C)
median tine: 5.171 as (0. 08. GC)
time:
6.872 (13.80% GC)
maximun time:
389.953 μr (93.90% GC)
samples: 18000
evals/ malls/sanple:
We first import the norm function from Julia standard library Linear Zygote's builtin AD engine will generate slow code and memory allocation of 339KB. Then write reversible norm function r r_norm with NiLang and port the backward function to Zygote by specifying the backward rule (the function marked with macro Zygote @adjoint). Except for the speed up in computing time, the memory allocation also decreases to 23KB, which is equal to the sum of the original x and the array used backpropagation.
(1000 x 8 1000 8 2)/1024 23
The later one has a doubled size because GVar has extra gradient field.
F A BENCHMARK OF ROUND-OFF ERROR IN LEAPFROG
Running reversible programming with the floating pointing number system can introduce round-off emrors and make the program not reversible. The quantify the effects, we use the leapfrog integrator to compute the orbitals of planets in our solar system benchmark. The leapfrog interations can be represented as
d = G (x(K} xi)
(8)
|| - X111
1/ = 1/11/2 + d;At
(9)
Ru1 I 1/=1
(10)
21

---

Under review as a conference paper at ICLR 2021
10a
Flot32 (reqular)
Floet32 (reversible)
103
(cummulativ)) Rlaa64 (regular)
round off error
Flost64 (reversible)
Float44 (cummulative)
10
10
10-12
102
10 leapfrog steps
10
Figure 6: Round-off errors in the final axes of planets as a function of the number of time steps. "(regular)" means irreversible program, "(reversible)" means reversible program (Listing. 25), and "(coumulative)" means reversible program with the acceleration computed with ccumulative errors (Listing. 26).
where G is the gravitational constant and mj is the mass of jth planet, X. 1t and à are location, velocity and acceleration respectively. The first value of velocity is V1/2 agAr/2. Since the dynamics of our solar system are symplectic and the leapfrog integrator is time-reversible, the reversible program does not have overheads and the evolution time can go arbitrarily long with constant memory. We compare the mean error in the final axes of the planets and show the results in Fig. 6. Errors are computed by comparing with the results computed with high precision floating-poin point numbers. One of the key steps that introduce round-off error is the computation of acceleration. If is implemented as Listing. 25, the round-off error does not bring additional effect in the reversible context, hence figure. This is because, when returning a dirty (not exactly zero cleared due to the floating-point round-off error) ancilla the ancilla pool, the small remaining value will be zero-cleared automatically in NiLang. The acceleration function can also be implemented as in Listing. 26, where the same variable rb is repeatedly used for compute and uncompute, the error will accumulate on this variable. In both Float64 (double precision floating point) and Float32 (single precision floating point) benchmarks, the results show a much lower precision. Hence, simulating reversible programming with floating-pons numbers does not necessarily make the results less reliable if one can avoid cumulative errors the implementation.
overlapping lines "(regular)" and "(reversible)" in the
Listing 25; Compute the acceleration. Com- pute and uncompute on ancilla rc
Listing 26: Compute the acceleration. Com- pute and uncompute on the input variable rb.
0i function :(+=) (acceleration) (y::3V)( vV)) rb::v3(1), :bell G)
function :(==) (acceeleratiomnnyyy..o. ra::v3(T), rb::v3(T), ub: :eal, G)
where T
where @routine @invcheckoff begin
Broutine @invcheckoff begin ezeros T ancl anc2 anc3 anc4 zero(V3(T])
@zeros T d ancl anc2 anc3 anc4 sodistance(ra, rb) ancl += sqrt(d)
d + sqdistance rb) (d)
anc2 ancl 3
anc3 += G $ nb anct += anc3 / anc2 rb
anc3
rC += rb ra
end
y!
anc4 re
~Groutine
-Broutine
not recovered rigorously!
end
end
22

---

Under review as a conference paper at ICLR 2021
G LANGUAGE DESCRIPTION
G.1 GRAMMAR
minimum definition NiLang's grammar is
s
a statement
multiple statements
constant
x,
symbols
i,
integers
e
julia expression
Tplx + v]
environemnt with x's value equal to environemnt with x undefined
Trlx + nothing]
Tp.e He
Julia expression under environment of is interpreted as value the evaluation of statement s under environment Or generates environment o'p the reverse evaluation of statement s under environment op generates environment T,
Tp. Up o'p
Tp.s Up or
Statements
8 -5 cdd)) x x
@routine s : ~@routiee if () s* else sa end
while (e,e) end
for morx=eieien end
begin s* end
Data views d :: d.x d[e] dre
c
Reversible functions
@i function (x* ) s* end
> is the pipe operator in Julia. Here, e a reversible function and d' represents a bijection of d. Function arguments are data views, where data view is modifiable memory. It can be variable, a field data view, an array element of a data view, or bijection data view.
G.2 OPERATIONAL SEMANTICS
The following operational semantics for the forward and backward evaluation shows how statement is evaluated and reversed.
Tp.e V.
Jp. U. F vl.x e U, o - nothing]
ANCILLA Tp(x H- nothingl, + xpxx+v
ANCILLA-I Op. U, o
σp. - op
TP,x ell
x - o op
SP. Up Uy opp. begin 82 s. end Up of
BLOCK
Tp. begin s S, end Up 0%
Tp, begin end U, or
Tp.SnUplor of of begin s1 end 07!0%
BLOCK-I
Tr,, begin ", end J 0%
oy. begin end 1
or,ei le o le m opee (n <= == (n2 0)
orix + mil.3 Up of for testetes Jend U, oj Te. for x ellsses end U, of
FOR
23

---

Under review as a conference paper at ICLR 2021
Tp,e1 De 81 dp de nn orees Ue ny (m <= (n) Up op
FOR-EXIT
Tp, x
Gp. es: egee begin 3 end end Up oj Tr, for eiezees end U,
FOR-1
Op,4 Ve true Jp,31 Up of op Uc true Jp. (e), else end Up U
IF-T
Tp.e: We false op.52 Up Tf pp.e2 Ue false (f 8j else s end Up opp
IF-F
Cp, if (1) begin si end else begin 5 end end Up ogp Tr, if (2),02) else end Up'or
IF-1
Cp.c Us true
dp,02 de false Tp.5 Up Tp Tp. 5) Uloo T'p while (e), 3end Up o
WHILE
WHILE-RECC Jp.22 Ue true
dp.01 Ue true Up Jp (p. Uloop dp.
(e, Uson o dp.61 false (p.le1.e2, Utoop Tp
EHILE-EXIT Op.42 Uc true
WHILE-1 Sp. while (e2.e1) ~begin Jnd end Up opp while (e).ez) send Up! 0
Tp. S..sUpprr op Tp, - Up Jr
UNCOMPUTE
Fr. 81 Up Jj pp. @routine sji 3; @@routine U, o
Tpp begin 3 end 0% op.S1
COMPUTE-COPY-UNCO..E
Tr. @routine sj begin end @roottine Up or @routine si 3; ~@routinell," o
COMPUTE-COPY-UNCOMPUUE
Tp. d; Uger Ø H H val. (x) (,)),) = xy(x ... xx) U. only + 14 .. + v/]l
op the Op.
CALL
(r.. xr.xx(d; ..dd)) Up or.
CALL-1 (x.(-x,)dd.... ... d,)) Up T'p
GET-VIEW
Jr.d Jp.ed Uge V
SET-VIEW-SYM
OP.VX Uer JPX v]
24

---

Under review as a conference paper at ICLR 2021
SET-VIEW-ARRAY z fresh drlz vl, se) U. v
Jp.V Una of
vv Uea Typ
SET-VIEW-FELD fresh o xh. Uo op,. Une op
V, Une op
WEEVIEW-BBECTOO 3fresh odk vl.2z (-e) Ver an..d Um opp dr.Vddre ter op
Here, chfield(x, y, 2) is Julia function that returns object similar to x, but with field y modified to value z, setindex!xx, y) is a Julia function that sets the yth element of an array x to the value of We do not define primitive instructions like dj Q= xy(d2 dz). O E +,,, V) because these instructions
are prime(O, xy (d, d2....d)) = (d, @ x.(dh....dal) d.....ddd))) using the above CALL rule, where prime(O, xy) is predefined Julia function. To reverse the call, the reverse julia function -prime(O, xy) should also be properly defined. On the other side, any non primpiimitive NiLang function defintion will generate two Julia functions xy and ~xy so that it can be used in a recursive definition or other reversible functions. When calling a function, NiLang does not allow the input data views mappings to the same memory, i.c. shared read and write is not allowed. If the same variable is used for shared writing, the result might incorrect. If the same variable is used for both reading and writing, the program will become irreversibl.. For example, one can not use - x to erase a variable, while coding y.y -= x. z is safe. Even a variables is used for shared reading, can be dangerous in automatic differentiating. The share read of variable induces shared write of its gradient in the adjoint program. For example, += x
evaluated
as
a
regular
julia
expression
x will not give the correct gradient, and y *2 will.
but its equivalent forms
0; x; y += x zi Z x;
G.3 COMPILATION
The compilation of reversible function to native Julia functions is consisted of three stages: preprocessing, reversing and translation as shown in Fig. 7.
Source Code
NiLang IR
Julia Language
begia
grouttne begta abais)
Preprocess
ababs)
Transaaee
Boss kyntkk (OPosmppeessseee. kt tree
Compile
and togin) yi angle(s)
stire begta
Togins
Mascigrback (onusig ura, 13 the
begin
-froutine
(1ii bay cn drwe 16s, 2000e1)
Reverse
LIVM
begia
abs(s)
Trandage
and
caro(t)
Jula Campie
ylotn
angli(es) (og(s)
(ecrtpbads (Ontentoo 1h,
F1-
legi. (UhtRadt2) tegi #0 Urow
#beCo)
CillangCore.demm dearcann asro11))
ord
Figure 7: Compiling the body of the complex valued log function defined in Listing. 5.
In the preprocessing stage, the compiler pre-processes human inputs to the reversible NiLang IR. The preprocessor removes eye candies and expands shorteuts to symmetrize the code. In the left most code box in Fig. 7, one uses @routine <stmt> statement to record statement, and ~@routine to insert the corresponding inverse statement for uncomputing. This macro is expanded in the preprocessing stage. In the reversing stage, based on this symmetrized reversible IR, the compiler generates reversed statements. In the translation stage, the compiler translates this reversible IR as well as its inverse to native Julia code. It adds @assi gnback before each function call, inserts codes for reversibility check, and handle control flows. The @assignback macro assigns the outputs of a function to its input data views. As final step. the compiler attaches return statement that returns all updated input arguments. Now, the function is ready to execute on the host language.
25


Reviews:
[{"review_id": "bp9eYLlCnWQ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper adapts reversible computing techniques to compute gradients. The techniques presented are not new though the Julia based DSL is new. The results presented are for differentiating through a GMM. It is not clear if the technique scale to a modern day neural network models and how they will integrate into current frameworks like JAX, PyTorch or TensorFlow.\n\nThe paper may be more relevant to a Programming Language focused venue or maybe even JuliaCon", "extra_scores": {}, "extra_text": {}}, {"review_id": "S9SDYgzXMgY", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "General comments:\n- This paper presents a new approach to automatic differentiation (AD), namely the use of reversible programming to achieve memory-efficient function inverse and adjoint. The authors have done a good job reviewing the background and laying out the motivation for the new apporach. The implementation is based on adding an embedded DSL to Julia called NiLang. Through reversible programming, NiLang gets rid of the need for checkpointing and hence is amenable to CUDA execution. NiLang is benchmarked against native Julia, ForwardDiff and Tapenade. The performance of NiLang is slightly worse than other approachs in the GMM benchmark. But in the bundle adjustment benchmark, NiLang outperforms ForwardDiff and Tapenade, especially with CUDA acceleration.\t\n \nDetailed comments:\n- Section 2.3\n  - I feel the explanation of the pre and post conditions can be made clearer. While most readers are familiar with the idea of pre condition in if and while control flows, some may not be familiar with what post condition is. The example in Listing 4 isn't presented in a way that's most clear and helpful to resolve this confusion either. Please explain post condition more clearly, perhaps be adding annotations to Listing 4.\n  - Also, in Figure 1(a), what does \"pre == post\" mean? On a related note, in Listing 4, if the post condition of the if statement is a placeholder \"~\", how does it work when it's treated as the pre condition during reversal? Explain that it's simply treated as an always-true condition.\n  - Please add a sentences to explain how NiLang handles the errors (as shown in red in Figure 1) that occur during the control flow and their reversals.\n- Section 3.1\n  - Please explain what adjoint is briefly before mentioning it first time, possibly by citing the Tapenade paper (Hascoet & Pascual 2013).\n- Section 4.1\n  - Since the authors emphasize the memory usage advantage of NiLang, why not run memory benchmarking, quantify the results and show them in tables or figures here?\n  - Table 1: Why are NiLang GPU results not included in this table?\n  - Tables 1 and 2: The timing numbers in these tables to not span many orders of manitude. So using regular decimal points (e.g., 0.009844, 0.0351) might be more visually clear and easier to parse than the engineering notation currently used. Also, consider making plots instead of tables for these numbers, because plots will be much more intuitive and facilitate comparisons between the different implementations. The plots can be in logarithmic scale.\n- This manuscript currently lacks a discussion section. Given AD is widely used in machine learning and neural networks (especially within the context of this conference), many readers will be interested in whether NiLang is suitable for training neural networks.\n\nMore detailed comments / writing suggestions:\n- p 2. \"Besides the above “nice” features, it also has some “bad” features to meet the practical needs\" The meaning of the second part of this sentence is unclear. Please rewrite it.\n- p 8, Section 4.1. Do not repeatedly define the ancronym \"BA\". It's already defined above in the same page. Also, since you don't really use the acronym anyway, there's no need to define it.", "extra_scores": {}, "extra_text": {}}, {"review_id": "P9t5qeUfiO", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I apologize for the late review since I did not realize I was assigned an emergency review for this paper.\n\n## Summary\n\nThe paper proposes a new DSL language embedded in Julia that can represent reversible programs. They provide mechanisms to automatically reverse a program given its forward definition in their DSL. Their language would allow reverse mode automatic differentiation to be implemented in lieu of the standard checkpointing schemes. \n\n## Strengths\n\n* A DSL to express reversible programs and implementation in a well-known language\n* Simple description\n\n## Weaknesses\n\n* Very limited evaluation on two benchmarks.\n* Presentation issues that distract from the main point of the paper.\n* Vague language description and limitations not mentioned.\n\n\n## General discussion and Questions for the authors\n\nI liked the high-level idea of this paper, however the presentation and writing need to be drastically improved in order to be accepted for publication. Also, the current results section is limited to two examples and I recommend adding more case studies to validate the usefulness of their DSL.\n\nAt a high-level the authors can do the following to improve their presentation.\n\n* Some of the language implementation details distract the readers from understanding the design aspects. For example. “One can input “←” and “→” by typing “\\leftarrow[TAB KEY]” and “\\rightarrow[TAB KEY]” respectively in a Julia editor or REPL”. The authors can omit the implementation details or move it to appendices and focus more on the design decisions they took and the reasoning for those decisions.\n* The authors can present their DSL language more formally. For example, they can give operational semantics for their forward program and reversed program using deductive rules.\n* What’s supported by the language and what’s not is not clearly mentioned. Specifically, the authors should mention limitations and scope of the language.\n\nEvaluation needs to be improved\n\n* It is not conclusive from the results presented that the DSL (or reverse mode in general) produces better code than a checkpointing strategy. It helps in case of bundle adjustment, however has an overhead in the GMM implementation.\n* Coverage - To showcase the expressivity of the DSL, the authors should implement a known NN architecture (e.g., even a small resnet) and show how training and inference speeds vary.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "JS9dfthHV2c", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper draws connections between reversible programming and reverse mode automatic differentiation and introduces a reversible DSL in Julia that can be used to calculate first and second order gradients.\n\nI reviewed a previous version of this paper for NeurIPS.\n\nI really like the idea of reversible programming and I think that a clear introduction of reversible programming and its use in automatic differentiation could be of interest to the machine learning community. However, I feel that this paper fails to clearly explain the use of reversible programming and its trade-offs compared to checkpointing and other existing approaches.\n\nAs a paper, the first section is great, but then the authors leave me with many questions: How do checkpointing and reversible programming differ in memory usage? Given that the multiplier from listing 1 has 3 outputs, doesn't that mean that a program consisting of n chained multiplications still requires storing n * 2 + 1 outputs, similarly to regular AD? And doesn't binomial checkpointing allow for logarithmic memory usage in exchange for a logarithmic increase in runtime (rather than polynomial)?\n\nRather than answering these questions, the paper jumps eagerly into Julia code snippets, metaprogramming, and CUDA kernels, which I don't feel actually serve to elucidate the message that reversible programming is of interest to the machine learning community.\n\nAlthough I feel that this version of the paper is an improvement over the version I reviewed for NeurIPS, I feel that it still fails to clearly introduce reversible programming and shed light on the subtle trade-offs between reversible programming, checkpointing, and regular AD. I encourage the authors to rewrite the paper with less of a focus on the implementation details of their framework, and a stronger focus on the memory and runtime trade-offs provided by all of these methods from a more high-level, theoretical perspective.\n\nPros\n\n* Very relevant and interesting topic\n* Well-written introduction\n* Good code\n\nCons\n\n* Fails to introduce the topic appropriately for an ML audience\n* Does not clearly compare to advanced checkpointing methods\n* Not well written; too many details about the software implementation that do not contribute to an understanding of the high-level technique", "extra_scores": {}, "extra_text": {}}, {"review_id": "-lBKDkNq67", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Changes after rebuttal\nThanks to the authors for their answers to the questions and their revisions to improve the manuscript. It is useful to have further descriptions of reversible computing for an audience that may be unfamiliar with the topic. I would encourage the authors to make further revisions to more concisely show the scientific value of the work while leaving some of the details to tutorials or other documents.  Other venues more focused on scientific computing, programming languages, or Julia may also be more suitable. If the language also attracts more users and applications built on top of it, then the case for publication will also be stronger (consider that the PyTorch paper was presented at NeurIPS 2019 even though the first release was in 2016).\n\n---\n# Summary\nThe paper presents an embedded domain-specific language in Julia which enables reversible computation and automatic differentiation. In order to compute gradients, we need access to all the intermediate results in a program; typically, it is necessary to store (checkpoint) these intermediate results separately or recompute them from the inputs. With reversible computing, these are unnecessary as we can compute backwards from the output to reach any intermediate result. The paper shows some empirical performance benchmarks on a bundle adjustment program.\n\n# Strengths\n- The proposed system shows strong performance compared to the presented alternatives, especially when using GPU kernels.\n- There are many examples presented which shows that the language is terse.\n- The system is practicality and usable for existing scientific computing applications.\n\n# Weaknesses\n- As a significant portion of the paper is dedicated to examples of the language in use, there is not much room to discuss other aspects of the system.\n- The novel aspects of the work are not made very clear in the paper. It is hard to compare the benefits and drawbacks of the work compared to the alternatives, other than in the runtime performance.\n- ICLR is about machine learning, but there is no evaluation of machine learning workloads. For example, I think the ICLR audience would be quite interested in how such a system might enable very deep neural networks. \n\n# Comments\n- For people not very familiar with reversible computing (like me), it is quite useful to have detailed examples and explanations about the fundamentals. However, it seemed to me that too much of the main body is spent on the fundamentals and the tutorial aspects, and more of it could be moved into an appendix. \n- It would be better to have more comparisons and discussions of which aspects of the system are novel. There is a discussion of some related work on page 2, but it is not very systematic.\n- As the paper states at the end of page 2, it is not possible to rigorously reverse operations on floating point numbers. However, there is no further discussion of the implications of this. It would be good to have some further reassurance that the errors are not important, or to have a discussion of what applications are acceptable and sufficiently tolerant of the errors.\n- Given the lack of checkpointing required for automatic differentiation, it would seem to me that the language can enable significantly lower memory usage than non-reversible languages. So I was surprised that there are no benchmarks discussing memory usage, or showing that the method can operate with larger datasets/parameters on a fixed memory budget.\n- Anonymous submissions should not include acknowledgements and should not include links to non-anonymous GitHub repositories.\n- Please use \\citet and \\citep with natbib so that citations are formatted properly in the text. Citations at the end of sentences, or otherwise not used as a noun in the sentence, should look like (Author, 2020) rather than Author (2020).\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: After reading the paper, reviews and authors’ feedback. The meta-reviewer agrees with the reviewers that the paper touches an interesting topic (reversible computing) but could be improved in the area of presentation and evaluation. Therefore this paper is rejected.

Thank you for submitting the paper to ICLR. 

Decision: Reject