[HN Gopher] Reversible Computing
___________________________________________________________________
Reversible Computing
Author : ve55
Score : 96 points
Date : 2021-02-28 16:55 UTC (6 hours ago)
(HTM) web link (en.wikipedia.org)
(TXT) w3m dump (en.wikipedia.org)
| gbrown_ wrote:
| For anyone interested in the topic I highly recommend checking
| out Dr. Michael P. Frank's work. This video is good one to start
| with https://www.youtube.com/watch?v=IQZ_bQbxSXk
| rpmuller wrote:
| Michael is great. Here's a link to Michael's Sandia National
| Labs website, which has links to some of his publications:
| https://cfwebprod.sandia.gov/cfdocs/CompResearch/templates/i...
| m463 wrote:
| Feynman was the first person I heard talk about this, pretty
| interesting topic.
| the__alchemist wrote:
| One of the biographical books attributed to him (The Pleasure
| of Finding Things Out?) ha a chapter dedicated to this and
| related concepts. I was astonished when reading it, especially
| since he discussed this decades ago, but we don't hear much
| about it today, at least in popular media.
| abdullahkhalids wrote:
| He also has The Feynman Lectures on Computing, which has a
| chapter on reversible computing.
| User23 wrote:
| Same. I was introduced to the concept in the book Feynman
| Lectures on Computation. It's an excellent read. He was a
| brilliant man and it's fun seeing someone coming at computation
| from the physical direction.
| gfody wrote:
| one of the benefits of expressing business logic in a high level
| declarative language like SQL is that the order isn't specified
| and can be reversed depending on the execution context. a
| perfectly sargable and streamable view definition for example can
| end up on either side of a join in some execution plan with data
| streaming in either direction, and the same code can power
| filtering as well as generating.
| einpoklum wrote:
| Where order isn't specified, that doesn't mean it can "be
| reversed". It's just not part of the relevant state. So, I
| would say that's orthogonal to the issue of reversibility of
| computing.
| gfody wrote:
| fair I guess but that's awfully pedantic. today we can write
| code that runs backwards and forwards but it's because a
| compiler is generating multiple versions based on context -
| if we achieve physical reversibility then maybe one version
| could do. "computing" has many layers - I don't think it's
| off topic to include the high level ones in the discussion
| fallingknife wrote:
| Since x + y = z can't be reversed without preserving input, this
| would have to use additional memory. What if you then have z + a
| = b? Can you now throw out x/y, or does it have to be reversible
| all the way back to the beginning?
| tromp wrote:
| You start with {x, y, z=0, a, b=0} and then reversibly compute
| z+=x; z+=y, b+=z; b+=a to end up with {x, y, z=x+y, a, b=x+y+a}
| from which you could reversibly compute the starting state
| again with b-=a, etc.
| fallingknife wrote:
| Right, but when can you throw out your initial values?
| Because if this is going to be usable you have to free up
| memory sometime.
| ravi-delia wrote:
| It goes something like this:
|
| 1) Perform some reversible operation
|
| 2) Copy answer to another location (At some cost in heat)
|
| 3) Perform reverse operation, which rolls back memory to
| starting point
|
| When you're done you have zeroed out memory, and the only
| costly operation was the copying of the answer.
| a1369209993 wrote:
| You can't. If you want to zero the memory holding the
| initial values, you have to exchange it with some other
| memory. This is how current ('non'-reversable) computers
| work: exchanging junk data with the large number of known-
| value bits constituting a low-temperature and/or fixed-
| voltage environment via diffusion (eg, attaching a bit
| storage location to GND to clear it by diffusing its change
| into the GND bus + waste heat).
| KingFelix wrote:
| Thanks for this
| adamnemecek wrote:
| Closure under inverse is like the most important idea in math,
| physics and probability. Linear logic, constructive math,
| probability, quantum mechanics all have in common that they rely
| on closure under adjoint and norm which in turn give you closure
| under inverse.
|
| I wrote something on the topic but it's very incomplete
| https://github.com/adamnemecek/adjoint
| gaogao wrote:
| Humorous, unconventional example of reversible computing using
| actual swarms of crabs - https://www.wired.com/2012/04/soldier-
| crabs/
| corysama wrote:
| Waaay back in uni I was taught that eventually computing will
| have to go reversible because of the mentioned "von Neumann-
| Landauer limit". So, your program will run each instruction
| forward, then again as the stack rewinds (instead of stack pops).
| But, this 2X penalty will enable a >2X clock rate increase due to
| lower thermals.
|
| Rewinding code also has the side effect of automatic garbage
| collection. The challenge becomes copying out end results before
| rewinding without re-introducing thermal waste.
|
| In the meantime chips are utilizing partial measures against it
| like sending excess bits to recycling pools. So, A|B results in 2
| bits in, 1 bit out as a useful result and 1 bit shuttled off for
| recycling.
|
| Backing this up, I recently learned that quantum computer
| programs must be reversible if they are to function.
| rhn_mk1 wrote:
| The way I understand it is that you don't necessarily actually
| have to rewind anything, just that destroying information is
| what causes the extra energy need and is therefore not allowed.
|
| The principle is already in use in areas like differential
| signalling, where a single bit is transmitted on 2 lines at the
| same time: 0 as (0,1), 1 as (1,0), so that the total charge in
| the circuit never changes. In simple signalling like SPI, there
| is only one line, and the system has a different charge
| depending on the transmitted value, so the charge has to be fed
| into and removed from the system all the time.
|
| As for quantum computing, reversibility is coming as a direct
| consequence of the inability to either destroy or copy quantum
| states (which ends up being two aspects of the same thing).
|
| https://en.wikipedia.org/wiki/No-cloning_theorem
| tlb wrote:
| You eventually have to rewind, if you ever want to run a
| second program on your reversible computer.
|
| Ideally you break things into small chunks of computation
| where you run it forward, copy the result (at some energy
| cost), then rewind it. Then you're only paying per bit of
| result.
| smallnamespace wrote:
| Just to offer a slightly different rewording that may be more
| intuitive:
|
| Under quantum mechanics, information may not be destroyed,
| only moved around (this is implied by the fancy physics/math
| term 'unitarity').
|
| When you 'destroy' a bit in your (sub-)system, you're
| actually transferring that bit into the surrounding
| environment, which shows up as heat.
|
| Reversible computing avoids that heat generation by keeping
| all relevant state within your subsystem.
|
| The terminology around 'destroying information' can be
| confusing because the particular system under discussion
| isn't always clear.
| ravi-delia wrote:
| Although there are justifications outside of quantum
| mechanics if you, for example, already believe in the laws
| of thermodynamics. If computation didn't create entropy,
| you could reverse entropy. Of course, now it goes the other
| way. Since the universe runs on quantum mechanics 'below'
| thermodynamics, entropy can't be reversed because doing so
| would imply computation without entropy.
| zozbot234 wrote:
| Charge-recovery logic has become a lot less interesting with
| modern fabrication nodes since dynamic power draw (the part
| that's due to actual charging and discharging within the
| circuit) is now a relatively minor part of power dissipation,
| whereas leakage power has become a lot more important. The
| main way of lowering leakage power is to simply power off
| unused areas of the chip, but that doesn't help if you
| actually have to perform logic. So the whole idea of
| reversible computing has become a bit of a red herring.
| fmihaila wrote:
| For those who want to look into this in more depth, Conservative
| Logic by Fredkin and Toffoli [1] is a foundational paper
| exploring in detail how the principle of reversible computing
| impacts the underlying logic used for computation down to the
| logic gates. It is very readable.
|
| [ _Edit_ : the video recommended by gbrown_ elsewhere in this
| thread (https://news.ycombinator.com/item?id=26295043) refers to
| this paper and also shows how it is possible to move beyond the
| constraints introduced in it.]
|
| [1] (PDF)
| https://www.cs.princeton.edu/courses/archive/fall06/cos576/p...
| erk__ wrote:
| A interesting subject under this is reversible programming
| languages, there is for example Janus [0], which given some input
| program can generate the inverse, it can also generate C++ code
| with both directions.
|
| [0]: https://en.m.wikipedia.org/wiki/Janus_(time-
| reversible_compu...
| jaggirs wrote:
| Interesting fact: In a quantum algorithm you can not really
| delete information, which is why quantum algorithms are always
| defined as reversible computations (unitary matrices).
|
| Also, here is a reversible programming language someone made
| (which has nothing to do with quantum):
|
| https://wiki.c2.com/?ReversibleProgrammingLanguage
| MichaelBurge wrote:
| Isn't every algorithm reversible if you save the inputs?
|
| If you have some algorithm A that turns an input bitstring N into
| an output bitstring M in K steps going through states S(0) ...
| S(K), then:
|
| 1. None of the states can repeat or you have an infinite loop.
|
| 2. For some step 0 < K0 < K, (A, N, K0) uniquely determines both
| S(K0-1) and S(K0+1): Run A on input N for K0+1 steps and record {
| S(K0-1), S(K0), S(K0+1) }.
|
| 3. So all computations are reversible given (A, N, K).
|
| Maybe physics wants something like "local reversibility"(a
| reverse-step must execute within fixed time), whereas CS works
| with "mathematical reversibility"(is it a computable one-to-one
| function?).
|
| The construction above doesn't execute within fixed time, but I
| don't think that's the correct fix: There are lots of dumb things
| I can do in constant-time.
|
| So why does Physics not allow me to write off all my electricity
| expenses, as long as I keep the data on backup tapes in a closet
| in case I get audited for reversibility?
| einpoklum wrote:
| > Isn't every algorithm reversible if you save the inputs?
|
| 1. No, it might be probabilistic or non-deterministic.
|
| 2. Depends on your definition of reversibility. Maybe it's the
| ability to reverse a single, highly-localized, operation, such
| as an ALU operation; in which it doesn't help that you can
| repeat the computation all the way from the input to the
| previous state.
| wizzwizz4 wrote:
| It actually _does_ let you do that. Trouble is, unless you can
| reverse your backup tapes to their original state, that won 't
| help you.
| longemen3000 wrote:
| In Julia there is a package for a reversible computing DSL, with
| excelent examples https://giggleliu.github.io/NiLang.jl/dev/
| miguelrochefort wrote:
| How does that relate to P versus NP problem?
| float4 wrote:
| P vs NP can be expressed using Turing machines. However,
| reversible languages like Janus can only execute injective
| functions whereas a Turing machine can also execute non-
| injective functions. This is why reversible Turing
| completeness, or r-Turing completeness, was invented[0] to
| further work on reversible languages.
|
| As P vs NP has to do with Turing machines, not just reversible
| Turing machines, it's not really that comparable as far as I
| know.
|
| There is some comparison that can be made between TMs and RTMs
| if you have multiple memory tapes, but I forgot what it was.
| Could be that that was also described in [0], but I don't know.
|
| [0] "What do reversible programs compute?" from Axelsen et al.
| wizzwizz4 wrote:
| It doesn't. (Probably.)
___________________________________________________________________
(page generated 2021-02-28 23:00 UTC)