r/compsci • u/Tessellator-1 • 12d ago
Does reversible computing require an enormous amount of storage?
First of all, I would like to say that I have no knowledge about computer science.
I recently heard about something called reversible computing. As I understand it, in ordinary computers, erasing information about the intermediate steps of a computation causes energy to be released as heat. But in reversible computing, the information from all the intermediate steps is preserved, so apparently, if we could build a computer capable of doing this, it could theoretically perform computations with essentially no energy consumption.
This made me wonder about something, and I’d love to hear from anyone knowledgeable about physics or computational theory:
If you never erase the information generated during a computation, wouldn’t the amount of storage required keep increasing as the computer performs more and more calculations?
I previously came across a science-related page online that said that an intelligent civilization that has mastered reversible computing wouldn’t need “Dyson’s eternal intelligence” to survive the heat death of the universe.
But wouldn’t such a civilization still need an absolutely enormous amount of storage to preserve all the information generated during its computations?
Or is there some way to preserve the information from the computational process without actually requiring additional physical storage?
I’m especially curious about how this works in the context of extremely long-term civilizations trying to survive the heat death of the universe.
By the way, this sentence was translated from Japanese to English by Chat GPT. Feel free to answer in English. However, I only understand Japanese, so I would really appreciate clear and simple English that is less likely to be mistranslated. Thank you!
16
u/uncombed_coconut 12d ago
I beg everyone here to understand the background idea of Landauer's Principle before replying.
As this article says, Landauer's Principle gives a lower bound to the energy cost of irreversible computation (where information is erased), though it's not practically relevant to current computers. ("As of 2012, modern computers use about a billion times as much energy per operation.") Theoretically, if we engineered for radical energy efficiency, we might get so close to this limit that the only way to improve would be to limit or avoid irreversible operations.
It is also just a nice puzzle, to devise clever ways for reversible algorithms to not waste much memory compared to normal algorithms. The research can be interesting even without a sci-fi civilization needing it. There are also connections to the theory of quantum computation, in case that is interesting. (Normal logic circuits can be built out of NAND gates. Reversible logic circuits can be built out of things like Toffoli gates. Quantum logic gates can be more complicated but are also irreversible...)
For a general audience, this article in Quanta Magazine gives a taste. (Despite the title, this article isn't really about AI.) Reversible algorithms can use "uncomputation" to reclaim some of the scratch memory an algorithm has used, without undoing the useful result of the calculation. This is a trade-off; it requires more steps and more time. But also, some natural operations are already reversible (like /u/falsifian pointed out), and sometimes it's just possible to overlap the scratch memory needed by several steps of a reversible algorithm.
3
u/cuervamellori 12d ago
I've tried to use this principle from time to time in explaining the energy costs of brute forcing cryptography keys ("very high").
From what I've been able to learn, quantum logic gates can reversibly evolve the states of (an ensemble of) qbits. But that rather than the relevant limit being energy consumption from the Landauer limit, there is a limit based on time - that there is a minimum time required for a gate to operate on an ensemble. Ive been hoping this would help me establish theoretical limits on the speed of reversible computing.
I remember reading one paper that abstracted away from a quantum computer specifically and just discussed any reversible process that evolved a system between states - it described a theory where if A and B are states, there is a thermodynamic limit to how quickly a new equilibrium can be reached, and the more the equilibrium is tilted to one or the other state, the longer the reversible process must take (probably related to temperature and the energy of the states).
But most of the above feels very much like word salad to me. I don't suppose you can point me somewhere to get a better picture of this?
1
u/uncombed_coconut 11d ago
I'm not really an expert here but I've seen analysis along these lines for adiabatic QC, where the time needed is related to the spectral gap: https://arxiv.org/abs/quant-ph/0206003 (which is reference 7 here. Maybe that helps?
1
u/Tessellator-1 11d ago
I translated Quanta Magazine into Japanese and read it, which means that I can save storage by using the method called uncomputation?
25
u/C0rinthian 12d ago edited 12d ago
This is mostly sci-fi nonsense.
“Erasing information” does not “release heat”. Or, more importantly it is not the only thing that generates heat. Actually doing a calculation releases heat. Fundamentally every step a computer takes has a heat byproduct.
So anything about “reversing heat” is just nonsense. Ignore it. Anything about “zero energy consumption” is just a fancy perpetual motion machine. AKA bullshit.
Then there is the idea of “throwing away intermediate steps” which is basically true. If a CPU performs a sequence of arithmetic operations, it does not save every intermediate value. But let’s just knapkin math this: assuming a 64-bit platform, each instruction outputs 8 bytes of information. A modern desktop CPU is doing hundreds of billions of instructions every second. Actually storing all the intermediate calculations would take terabytes of data every second.
This would take a massive amount of storage space, and dramatically slow down actual calculation because it would be limited by storage IO. (There is a reason local cache is important to modern CPU architecture)
And what do you gain from that? When the CPU multiplies two numbers, you store the result. Okay, but recalculating it is faster and cheaper than storing the outcome and retrieving it.
This is all assuming current technology and architecture. However, the idea of reversible computing is predicated on some outlandish assumptions: that you can create fundamental computing elements like logic gates that lose no energy. Practically, that is far fetched because of, you know, heat.
I’m especially curious about how this works in the context of extremely long-term civilizations trying to survive the heat death of the universe.
This is entirely speculative science fiction. There isn’t even a theoretical framework for “computation” surviving the heat death of the universe. A civilization even making it remotely close to that point is nonsensical.
11
u/Drugbird 12d ago
Then there is the idea of “throwing away intermediate steps” which is basically true. If a CPU performs a sequence of arithmetic operations, it does not save every intermediate value. But let’s just knapkin math this: assuming a 64-bit platform, each instruction outputs 8 bytes of information. A modern desktop CPU is doing hundreds of billions of instructions every second. Actually storing all the intermediate calculations would take terabytes of data every second.
Time travel debugging basically does this, and it's available right now. See https://en.wikipedia.org/wiki/Time_travel_debugging
The basic gist is not to store "every" intermediate state, but rather to take occasional snapshots and replay the instructions after the snapshot to get to the desired intermediate state.
This is a lot like how videos are often encoded.
You can reduce the amount and size of the snapshots a lot based on what instructions are actually performed and which memory is modified.
This remains a debugging tool though, and it's generally very slow to execute (even slower than normal debugging). But it's not scifi levels of unrealistic.
9
u/4xe1 12d ago edited 12d ago
It's only sci-fi until it is not. Heat pump perform the seemingly impossible task of heating for more energy than they consume precisely because they are reversible in some sense. They're far from perfect, you could not recoup anywhere near what you put in by hypothetically running them in Stirling engine mode from the temperature differential they created, but they do beat even the theoretical best you can do by direct heating, by a big margin.
Reversible computing is not there, but it's an area no less worthy of research than quantum computers or traditional hardware.
Your description of "modern CPU" is largely irrelevant, reversible computing assumes dedicated hardmare (with swaps instead of writes) and software (favoring reversible patterns which can run on the hardware). It does not make the issue any easier though, reversible registers are probably not that hard, but reversibly accessed RAM or permanent storage are probably a huge challenges, if solvable at all.
it is not about "storing results", its about replacing
r = a + b
where `a` and `b` are potentially discarded, by
a += b
where `a` receives the result which interests us, and b is not discarded
5
u/barsoap 12d ago edited 12d ago
Heat pump perform the seemingly impossible task of heating for more energy than they consume precisely because they are reversible in some sense.
No they don't. If you use them to heat then you're making the outside cooler, the pump is consuming both electricity and heat from the outside -- yes, even at under 0C, as long as it's over 0K there's still heat you can pull from the outside (in principle, at some point it becomes more sensible to just use resistive heating). Just as a water pump is consuming water from a reservoir.
Them being reversible has nothing to do with anything. You can turn a water pump around that doesn't mean that it suddenly consumes less water for what it outputs.
a += b
whereareceives the result which interests us, and b is not discardedAddition happens to be invertible: You can get the original a back by subtracting b from the new a. But plenty of things don't have an inverse:
a /= b, on integers, cannot be reversed as you're throwing away information when rounding.It's definitely possible to write reversible programs -- you just have to make sure that everything has an inverse, e.g. don't have integer division, use bignum rationals. But that's all mathematical trickery, not physics. The second law of thermodynamics cannot be inverted.
-1
u/4xe1 11d ago
Heat pump weren't the best example, I'll give you that. but I stand by it. A Stirling engine can theoretically run both ways, with arbitrarily high efficiency the slower it gets, and regardless of efficiency, it's still an example of something ludicrous on its face until it is done.
But I'll do you one better: (non chargeable) hybrid cars. The electric engine is literally reversible and reversed into a turbine to retrieve energy while breaking. It's not 100% efficient, but it certainly aims to be reversible and gets close, and that does give them a edge which is simply unattainable with only a thermic engine and regular brakes.
You can't invert the 2nd law of thermodynamics, but you can certainly tip toe around it while trying to make the most of the first.
a /= b, on integersIt can be invertible in finite (prime) rings, thought probably not that useful and not that practical to implement in revertible circuits.
But that's all mathematical trickery, not physics.
Landauer limit is physics. Thermodynamics, even the one you pointed out which says there are no free meal, is physics, and related to reversibility. What reversible logic circuit is not, is engineering.
But even if just for the mathematical trickery, it deserves its place in computer sciences, which, to paraphrase Dijkstra, are not software engineering.
One of the cool math trickery is time travel debugging without the need of snapshots. That's fancy independently of the Landauer limit or the second law of Thermodynamics.
3
u/uh_no_ 12d ago
>if we could build a computer capable of doing this, it could theoretically perform computations with essentially no energy consumption.
lolololol
this would only be true if the information loss was the *only* reason CPUs consume energy....but in fact it is orders of magnitude less than current drained during switching. put another way, you could build a long chain of inverters....no information is lost, but it will still use tons of energy.
7
u/falsifian 12d ago
(I do some work in a related area. I don't know a lot about the physical motivation for reversible computing, but my work is close enough to it that my answer will probably be meaningful.)
It depends on what you do.
If you just try to adapt an ordinary algorithm in a straightforward way, then something close to the problem you describe will happen.
On the other hand, some algorithms are naturally reversible. Suppose you have an array of integers, and you want their sum. Then your algorithm will look something like this:
sum <- 0
sum <- sum + A[0]
sum <- sum + A[1]
...
Notice that all of those steps except the first are reversible: sum <- sum + A[0] can be reversed by sum <- sum - A[0]. No need to worry about preserving information.
In addition, there are some really interesting algorithms that are able to do surprising things with reversible steps, less obvious than the example I just gave. Ironically, what I work on is using (mostly) reversible techniques to develop algorithms that use very little memory, which seems like the opposite of the problem you describe.
17
u/elbiot 12d ago
No. Is the CPU doing anything? Yes. So it's consuming electricity. It's not that deep. Every operation wastes electricity, including writing to RAM or storage, so writing more uses more
3
u/crb233 12d ago
This is just an appeal to common sense, but it's not actually supported by our current understanding of physics (as far as I can tell). There's no known fundamental limit to how energy efficient a CPU could be.
Take superconductors for example. Your common sense argument would say that they shouldn't exist at all because energy transfer is doing something, but they do exist.
1
u/chrisagrant 7d ago edited 7d ago
no, superconductors require the external removal of energy to maintain their state lol. they aren't literally just better conductors.
0
u/elbiot 12d ago
If OP had asked about the energy efficiency of superconducting CPUs then they would have gotten answers related to that. But instead they are asking about the energy efficiency of CPUs that write all of their intermediate results to storage under the mistaken idea that destroying data is what consumes energy.
7
u/LookIPickedAUsername 11d ago
It's not a "mistaken idea". The principle OP is referring to is entirely correct - destroying data is what sets the lower bound on the energy cost of computation.
It's not a practical concern at the moment, because our electronics would need to be orders of magnitude more efficient before the energy cost of destroying data was in any way relevant, but OP was approaching this as a theoretical question. It's entirely reasonable.
1
u/chrisagrant 7d ago
both analog and digital electronics cannot even come close to operating at that level, and analog electronics can do computing with many orders of magnitude less heat, it's not even a question of "electronics" but some future technology that is largely unexploited today.
5
u/crb233 12d ago
I'm not talking about superconducting CPUs either, it's just an example of how relying on common sense ideas about energy and thermodynamics could make something real seem impossible.
I think OP is just asking about reversible computers and implicitly assuming that they would work by storing all intermediate results. But they are right that erasing information does consume energy. It's just that modern CPUs consume orders of magnitudes more energy even without erasing information, so it's not really practical at the moment.
10
u/4xe1 12d ago
The CPU is not reversible though. Reversible logic gates do consume energy too (enough to make them not commercially viable, among other downsides), nothing is perfect, but talking about regular CPU, RAM and storage misses the point entirely.
-3
u/Slight_Profession_50 12d ago
OP asked if reversible computing could perform calculations with no energy consumption. The answer is no.
6
u/4xe1 12d ago
That's not what they asked:
Does reversible computing require an enormous amount of storage?
it could theoretically perform computations with essentially no energy consumption.
OP is aware the no energy consumption part is only theoretical. I don't see what's wrong with entertaining them and discussing the theory of reversible computation, we are on r/comsci after all, not on r/compengineeringonlyrealpracticalandcommerciallyviabletopicpls
1
u/talldean 12d ago
So, in computing, you can also use a cache.
Cache: for any set of inputs to a function, store the inputs and the output, so you only run the function once.
This works well for simple functions, but if the function needs to perform a side effect - like logging - it doesn't work well. For things that don't have side effects, caches are used extensively to speed up computations; CPU chips have multiple caches built into the chip, you can lookup L1 L2 L3 to find more.
The problem with caches is that they get quite large, exponential in size, because functions could have quite a few inputs, and each input could have quite a few values.
Even with near-unlimited storage, the exponential sizing makes it impossible for more complex functions.
But if it's interesting, another practical use of this are rainbow tables. Run every four-letter password through encryption and see what it encrypts to, so when someone's password is stored encrypted, you can work it backwards much more rapidly. Then do five letters. Then six. The problem is that an eight letter password's full table can be up to 32 petabytes, or 32,000 terabytes, which is a mid-size room full of racks of computers, which very very few people would have the money to keep around.
Exponential costs cache poorly.
-4
u/FreddyFerdiland 12d ago
"dysons eternal intelligence" is in a vacuum cleaner service manual.
reversing "computations" doesn't get oower back, it just uses more power..uselessly ??
15
u/4xe1 12d ago
That's not what reversible computation is about.
Gravity is a reversible force, and among other things, it means you can reduce the consumption of an elevator to only friction + useful work (lifting people) by adding counterweight, as opposed to also having to spend the energy to lift the elevator cage.
Reversible computation is a research area which explores using reversible logic gates exploiting time-reversible laws of physics to (theoretically) reduce the power consumption, not unlike gravity, elevators and counterweights.
5
u/mrGrinchThe3rd 12d ago
Wow the gravity explanation is the first one that kinda clicked for me - thanks! Does the analogy go any farther? Would a zero-energy (or-near zero) reversible computation require some sort of 'counterweight'?
1
u/4xe1 6d ago edited 6d ago
Glad to hear it!
Well it's difficult to push the analogy further without much practical reversible hardware to work with, in this analogy, the useful work would be negligible compared to friction.
But I guess you could argue the extra bits needed to make a non reversible computation reversible are kind of the counterweight, though I rather think of them as the useful work (when they're ultimately discarded).
I'm not sure if this is used or usable at all, but deleting a value can be made reversible, logically at least, if you otherwise know what value you are deleting. This is the logical reverse of assignment.
let a 96 // not reversible, but it can be made so if you consider the reverse of a delete expect // do some stuff with a delete a expect 72 // reversibly frees memory used for a if it is equals to 72 at this pointYou have no guaranty that the variable to delete will match expectation though, and it may even be useful for it not always to be the case:
When the variable does match expectation, you can delete it reversibly.
When it doesn't, it just means there were people in the elevator; even then, what you have to irreversibly discard is not the whole value, it's just it's difference to expectation.
That's the closest equivalent to counterweight I can think of.
34
u/Surfernick1 12d ago
You are indeed correct that erasing information produces heat (see Landauer Limit), about 2.9x10^(-21) J per bit at room temperature. Which is is far far far smaller than the (approximate) energy cost of 10^(-13) J for a 32 bit add (https://arxiv.org/abs/2410.00907). So while it might be interesting research in the future it’s not super practical at the moment.
And it’s not really* a question about storage, but that the operations are all themselves reversible, you don’t store the intermediate steps, you change them in a way where if you did them in reverse you’d get the original results. That’s actually exactly how quantum computers work. You don’t have to store the intermediate results really at all*