News for hackers. Stuff that matters.

GiggleLiu

Re:Reversible Computing on Thursday March 04, 2021 @12:45AM (#26339077)
> 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.

Re:Reversible Computing on Thursday March 04, 2021 @12:29AM (#26338994)
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.

Re:Reversible Computing on Thursday March 04, 2021 @12:00AM (#26338832)
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.
Re:Reversible Computing on Wednesday March 03, 2021 @10:34PM (#26338293)
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.
Re:Nilang.jl – A Reversible Julia DSL on Sunday October 11, 2020 @04:04PM (#24748642)
Graph embedding example is not missing, it in the appendix of the paper's master branch: https://github.com/GiggleLiu/nilangpaper/blob/master/invc.pd...

The source code is available here: https://github.com/JuliaReverse/NiGraphEmbedding.jl

Re:Nilang.jl – A Reversible Julia DSL on Sunday October 11, 2020 @04:03PM (#24748630)
This is the latest NiLang tutorial notebook: https://github.com/JuliaReverse/NiLangTutorial
Re:Nilang.jl – A Reversible Julia DSL on Sunday October 11, 2020 @03:33PM (#24748394)
Snapshots can be freed through reverse computing in NiLang. Reverse computing has subtle relationship with checkpointing, see author's blog: https://nextjournal.com/giggle/reverse-checkpointing .
Re:Nilang.jl – A Reversible Julia DSL on Sunday October 11, 2020 @03:28PM (#24748353)
Thanks for the link to the paper, also check the latest version here: https://github.com/GiggleLiu/nilangpaper/blob/master/invc.pd...
Re:Nilang.jl – A Reversible Julia DSL on Sunday October 11, 2020 @03:26PM (#24748331)
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)

Re:Nilang.jl – A Reversible Julia DSL on Sunday October 11, 2020 @03:20PM (#24748282)
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/
Re:Nilang.jl – A Reversible Julia DSL on Sunday October 11, 2020 @03:06PM (#24748196)
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.
The github page is https://github.com/GiggleLiu/NiLang.jl.

Search “Reversible Computing” and “Reversible programming” for more discussions about reversible programming in Hacker news.