GiggleLiu
GiggleLiu on Hacker News
> What if the reversibility of a program was implemented at the function level?
Are you finding NiLang? - an embedded domain specific language in Julia for creating reversible functions. Meanwhile, it has one of the best performance in automatic differentiation (AD).
I find reversible programming particularly useful in the reverse mode AD, where reversing the tape is required in order to use intermediate information to compute gradients. The Bennett's time space trade-off is particularly useful. Traditional AD also have something similar called treeverse to trace back states, however, it involves nasty implicit stack operations and can not utilize reversibility. Reversible computing is way more elegant.
It is not clever to build a completely reversible computer. No one wants to undo the computing to erase the disk after training a neural network for a month. Reversible computing is not always more energy efficient. The "proof" follows from the Bennett's time space tradeoff:
https://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2013W/Lev...As the coarse graining process goes, the ratio between computing time and garbadge space size increases exponentially. Erasing space is more energy efficient when E_compute/E_erase > N_uncompute/N_erase, where E and N are energy and number of instructions.
BUT, it is very likely to have a reversible computing device like GPU that can do part of works.
The key point is: most reversible computing devices CAN erase information, although with energy cost. We just need to switch between uncomputing and erasing at the right place. e.g NiLang is an eDSL that lives in function level, while most other reversible programming languages are standalone.
Nice project, please also check this notebook of Billiard ball model cellular automata (BBMCA) in NiLang:
https://giggleliu.github.io/NiLang.jl/dev/notebooks/margolus... . BBMCA is a reversible cellular automata model that very possible to find a physical correspondence. It is a strong candidate for future reversible computing in my mind.
According to [Michael Frank's video](
https://youtu.be/IQZ_bQbxSXk?t=547), there is an architectural overhead of ~500x that people can not get over (IIUC, this overhead only applies for gate based computing models). A reasonable gap between state-of-the-art gate based computing models and Landauer's limit should be 10^2-10^3. On the other side, reversible computing in general has 2-16 times computational overhead at the software level from my using experience. To save energy, reversible computing has to be at least ~10x more energy efficient at the instruction level.
1. Scalar level
Various benchmarks (including those in the paper) show NiLang is much better than Zygote to differentiate scalar functions. And Zygote is much faster than TF and PyTorch.
2. Tensor level
Zygote, TF and PyTorch are much better than NiLang, because NiLang's matrix multiplication is not fully optimized, it is much slower than BLAS. (One can wrap BLAS into NiLang, but that does not measure NiLang's programming language level AD performance anymore)
Very good question. Floating point `+=` and `-=` are not exactly reversible. This is the only approximation that we have made in NiLang. To compile NiLang to a reversible device (rigorously reversible), we need to overhaul current number systems, i.e. using fixed point numbers and logarithmic numbers instead. Fixed point numbers are exactly reversible under `+=` and `-=`, logarithmic numbers are exactly reversible under `*=` and `/=`. Here is an example of implementing Bessel function with two number systems:
https://giggleliu.github.io/NiLang.jl/dev/examples/besselj/
NiLang requires every instruction being reversible, e.g. `SWAP` and `y += f(args...)`. The back-propagation is implemented on a limited instruction set. It is different with Neural ODE because neural ODE does not back propagate the program step by step. Some time reversible integrator can utilize the reversibility (with NiLang) to save memory. e.g. the leap frog integrator for symplectic systems.
Posted by
GiggleLiu on Thursday April 09, 2020 @02:24PM
from the show-hn dept.