7 ms·

Building a Completely Reversible Computer

90 points by lainon 10y ago

brudgers 10y ago
Direct link to paper at arXiv, https://arxiv.org/pdf/1702.08715.pdf https://arxiv.org/pdf/1702.08715.pdf
- tzs 10y ago
  Link to the abstract: https://arxiv.org/abs/1702.08715 https://arxiv.org/abs/1702.08715 Generally, it is better to link to the abstract than to the PDF. If the paper gets revised the abstract page page's PDF link will point to the latest version of the paper (with links available to prior revisions). The direct PDF link will remain stuck with the old version.
  - brudgers 10y ago
    Because I the find abstracts of readable, clear, and interesting papers are often indistinguishable from unreadable and dull papers, I prefer the paper itself to its abstract...at least in terms of Hacker News...I am long since reading scholarly papers for academic purposes. If someone wants to read the abstract, it's right there at the beginning of the paper anyway.
    - seanmcdirmid 10y ago
      Abstracts are short enough that they can be inlined into a hackernews comment directly: > A critical analysis of the feasibility of reversible computing is performed. The key question is: Is it possible to build a completely reversible computer? A closer look into the internal aspects of the reversible computing as well as the external constraints such as the second law of thermodynamics has demonstrated that several difficulties would have to be solved before reversible computer is being built. It is shown that a conventional reversible computer would require energy for setting up the reversible inputs from irreversible signals, for the reading out of the reversible outputs, for the transport of the information between logic elements and finally for the control signals that will require more energy dissipating into the environment. A loose bound on the minimum amount of energy required to be dissipated during the physical implementation of a reversible computer is obtained and a generalization of the principles for reversible computing is provided. It can save readers a click in deciding if they want to go for the whole paper or not. Think of the abstract as an upper bound on whether the paper is interesting or not. A paper could possibly be less interesting than its abstract, it is much less likely that it is more interesting than its abstract unless the author really messed up.
      - deleted 10y ago
        [deleted]
      - brudgers 10y ago
        Personally, I usually click on links based on the title more often than based on the comments. But I know other people have different habits. With a direct link to the PDF, the abstract is at the top of the PDF for anyone who wants to read it. For me personally, if I have the paper, I skip the abstract and read the introduction because it is more interesting and I don't feel a duty to bore myself reading the abstract. Here, I thought the title was interesting enough to click on the link and the paper interesting enough to provide a link to the less noisy original.
    - sctb 10y ago
      There's a small tradeoff in that not all readers might want to commit up-front to downloading a PDF. In the case of arXiv the abstract will be also updated with later versions of the paper if they appear.
      - brudgers 10y ago
        With Firefox the resource located at the arXiv URL of the PDF is smaller than the the resource located at the arXiv URL for the abstract. So goes the modern web. Both are an order of magnitude smaller than the originally submitted link. For me, the conventionality of UI of the PDF resource makes it easier to navigate than the UI of the resource for its metadata. Admittedly, I don't have a use case that is dominated by revisions to preprint journal articles...I just want to check papers out.
  - sctb 10y ago
    Thanks, we've updated the link from https://www.researchgate.net/publication/314115814_Building_a_Completely_Reversible_Computer https://www.researchgate.net/publication/314115814_Building_....
stevemk14ebr 10y ago
what is meant by reversible?
- naasking 10y ago
  https://en.wikipedia.org/wiki/Reversible_computing https://en.wikipedia.org/wiki/Reversible_computing
- SilasX 10y ago
  Logically (and therefore thermodynamically) reversible. By Landauer's principle, the only reason a computer must emit heat (and therefore use energy) is to perform irreversible operations. Therefore, if you want a computer that (potentially) uses the minimum energy, it needs to be reversible in this sense. An irreversible operation is anything that maps many (possible) states to the same state. Setting a bit to zero is irreversible (because it destroys the information about what bit was there previously). An AND gate is irreversible (because both TF and FT map to F). A NOT gate is reversible (because you can infer the input from the output.) There are universal reversible gates (Toffoli and Fredkin gates are examples, but there are many others), so you can (theoretically) build a (usable) computer whose logical operations are completely reversible.
  - sadgit 10y ago
    Does this imply that physical entropy and informational entropy are the same? Does it imply the computer would not give off heat? Or that a significant amount of the heat generated by a computer is due to information loss?
    - SilasX 10y ago
      >Does this imply that physical entropy and informational entropy are the same? It does, and there is a very strong (but not universally accepted) case that they are the same thing: https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_... Great lay article about it: http://lesswrong.com/lw/o5/the_second_law_of_thermodynamics_and_engines_of/ http://lesswrong.com/lw/o5/the_second_law_of_thermodynamics_... (Side note: I've long thought you can derive Carnot efficiency based on information-theoretic arguments about the information contained in knowing only the temperature difference between a heat source and a sink.) >Does it imply the computer would not give off heat? Or that a significant amount of the heat generated by a computer is due to information loss? Basically, yes. You can't avoid the heat emission from setting a 0 to a 1 on that computer's storage medium, but you would avoid the loss from any of the intermediate computations that typically make CPUs so hot.
dkarapetyan 10y ago
So reversible computing requires less energy not more right? Last I heard it is damn hard to forget information.
- VLM 10y ago
  Much less, in theory. At an imaginary hand waving level imagine the complete state of a cpu as passing charged capacitors around and occasionally charging new ones or discharging some. This is not all that far off of how they work... If you want to count to 7 reversibly there's an easy way involving hitting a 7 bit shift register, 7 times. In theory there's no reason to drain any capacitors per op or per the entire system, that same unit of charge just meanders down the line. Like a CCD sensor or old fashioned bubble memory kinda. The way chips are designed today that doesn't work, but insert a lot of kinda sorta in theory it could be done. On the other hand if you want to count to 7 using three full binary adders you're going to run into scenarios where two bits enter an adder (say, 001+001) and one bit leaves (result of 010), so at least one capacitors worth of charge got turned to heat. And that charging and discharging is basically wasting battery power for no good reason. And its not a lot of power for one capacitor, but you toggle a flip flop a couple billion times a second and then not-much adds up over time to a pretty hot CPU.
  - abecedarius 10y ago
    That last issue can be handled by encoding each logical bit as a pair of physical signals (like low/high for 0, high/low for 1). I don't think there's any reason you can't implement your reversible counter in binary.
- murbard2 10y ago
  In theory yes, the catch is that you're not allowed to forget information. For instance, you cannot use an "AND" gate, because a result of 0 would be ambiguous, but you can use the Toffoli gate [1] which takes three inputs and produces three outputs, mapping (a,b,c) to (a,b,c^(a&b)). But what happens to the outputs you don't need? They do need to go somehere. A reversible circuit ends up having a lot of unused outputs which need to be erased if the circuit is to be reused. In essence, we have traded a heatsink for a bitsink, but they are essentially the same thing. I don't see reversible computing as categorically different from regular computing. It's regular computing, with careful and detailed heat management. [1] https://en.wikipedia.org/wiki/Toffoli_gate https://en.wikipedia.org/wiki/Toffoli_gate
mrfusion 10y ago
Are there limitations for a reversible computer? Could this run Firefox someday?
- marcosdumay 10y ago
  It is only capable of reversible operations. A completely reversible computer could not interact with you. This paper goes long about how you can irreversibly initialize such a computer, run it, and then irreversibly read its results, and how much power you can save doing that. In practice the computers people could build were always slow and inefficient, nothing comparable to the computers we are used to have (not even to the usual microcontrollers).
  - johncolanduoni 10y ago
    It's also worth noting that even low-power chip designers would laugh at worrying about nkT losses from throwing bits away. Our technology is very far away from the thermodynamic limit for irreversible computers.
deleted 10y ago
[deleted]
openasocket 10y ago
What are the limitations to a completely reversible computer? I'm guessing it's still Turing complete, but do you pay a cost in terms of asymptotic complexity? I'm guessing you can make a program reversible trivially by doing something like making everything immutable and only ever appending new data, but of course that's extremely inefficient in terms of memory. Of course, I might be missing the core concept here.
- SilasX 10y ago
  AIUI, it's just a linear penalty because, at worst, you have to run each computation backwards to "uncompute it". That's under the (necessary) assumption that you don't even try to avoid erasure operations that need for their own sake rather than as an intermediate step.
  - aparent 10y ago
    It is a bit more complicated then that. The only penalty to time is a constant factor if you are willing to use space proportional to the computation time. I did a bit of work on how to do time-space trade-offs in reversible circuits in my masters thesis http://hdl.handle.net/10012/10949 http://hdl.handle.net/10012/10949.
ArchReaper 10y ago
What kind of applications would this actually be useful for? I don't think I really understand the benefit(s) here.
- Zaak 10y ago
  The benefit of a reversible computer is that there is no minimum amount of energy it must dissipate as heat in order to perform its computations. Every time a bit of information is erased, a certain amount of energy must be dissipated as heat. A reversible computer doesn't (have to) erase information. Reversible computing is energy-aware computing taken to its logical extreme.
  - ArchReaper 10y ago
    I get that. The concept of saving energy is what I do understand. What I don't understand is what kind of applications this could actually be used for. Given the (by-design) limitations of such a system, how would it be actually usable? What real-world scenarios would want this and be able to utilize it?
    - comicjk 10y ago
      Physics simulations. I work in drug design, and my field would be enormously benefited by this. Quantum mechanics calculations are naturally reversible.
      - johncolanduoni 10y ago
        The interior of the computation is reversible, but the measurement performed at the end most definitely is not. If it were, quantum computers would be able to solve NP-complete problems trivially, and complexity theorists would get pissed that physicists were holding out on them for decades.
        Entalpi 10y ago
        Can you expand on this?
ballenf 10y ago
A couple questions: 1. How does "reversible" here apply to encryption algorithms? In a sense the encryption key is forgotten, but with enough computing power it can be derived from the output (at least for certain encryption methods). So, in a sense no information is lost. 2. If two separate computers perform the same reversible operation, but one in reverse, are the two computers (if considered as one system) consuming no energy? Or must the operations be performed on the same computer sequentially? If the system of two computers is valid, then does that mean that somehow certain operations / calculations produce energy and others consume it? I realize both these questions are somewhat nonsensical, so I clearly am missing something fundamental about this theory.
- Zaak 10y ago
  2. Reversible operations have no minimum amount of energy that must be dissipated as heat, unlike irreversible operations which must dissipate every time bits are erased. So each computer individually could be consuming no energy, so both together would consume the sum (zero) of the two.
- undersuit 10y ago
  On 2. You can't run reversible logic on our currently non-reversible logic and expect to see less power usage. If you had two reversible computers you could reverse the output of the other while consuming minimal energy just as a single reversible computer could reverse it's own output. The operations must be run forward at least once, or technically you don't have the outputs to input to the reverse.
- johncolanduoni 10y ago
  Reversible (in the paper's sense) is more about the paths information takes than whether it's recoverable in principle. Lossless compression is reversible, but a reversible computer performing it would still need to have storage equal to the size of the entire original data. It's also important to note that the fact that you are doing calculations isn't the direct cause of energy consumption. Landhauer's principle is a consequence of the second law of thermodynamics, which mandates certain heat losses in certain situations but doesn't tell you anything about how they happen. The question of what actually causes the second law of thermodynamics to hold at the level of fundamental interactions is called Loschmidt's paradox, and there's not really a consensus as to whether we have an answer.
cmrx64 10y ago
See also a type system and programming language for reversible computations: http://gradworks.umi.com/35/87/3587675.html http://gradworks.umi.com/35/87/3587675.html
ajb 10y ago
OT: when I click on this, researchgate claims "People who read this publication also read 'Is minimal hepatic encephalopathy completely reversible following liver transplantation?' I don't believe them.
- yorwba 10y ago
  Maybe someone was searching for "completely reversible" and got intrigued? But I guess a recommender system is the more likely explanation.
  - mahmud 10y ago
    Not a recommender system or anything that intelligent. This is basically a keyword search of the paper titles. Even something as simple as term-frequence analysis would place the two papers far apart.
adrianratnapala 10y ago
Here https://arxiv.org/abs/1702.08715 https://arxiv.org/abs/1702.08715 is a link to the same article that might be a little easier to use.
karmicthreat 10y ago
So does this mean you can move the entropy cost around? For stack or 3D computing moving the heat cost to directly heatsinked surfaces would be useful.

90 points by lainon 10y ago

brudgers 10y ago

Direct link to paper at arXiv, https://arxiv.org/pdf/1702.08715.pdf https://arxiv.org/pdf/1702.08715.pdf

tzs 10y ago
Link to the abstract: https://arxiv.org/abs/1702.08715 https://arxiv.org/abs/1702.08715 Generally, it is better to link to the abstract than to the PDF. If the paper gets revised the abstract page page's PDF link will point to the latest version of the paper (with links available to prior revisions). The direct PDF link will remain stuck with the old version.
- brudgers 10y ago
  Because I the find abstracts of readable, clear, and interesting papers are often indistinguishable from unreadable and dull papers, I prefer the paper itself to its abstract...at least in terms of Hacker News...I am long since reading scholarly papers for academic purposes. If someone wants to read the abstract, it's right there at the beginning of the paper anyway.
  - seanmcdirmid 10y ago
    Abstracts are short enough that they can be inlined into a hackernews comment directly: > A critical analysis of the feasibility of reversible computing is performed. The key question is: Is it possible to build a completely reversible computer? A closer look into the internal aspects of the reversible computing as well as the external constraints such as the second law of thermodynamics has demonstrated that several difficulties would have to be solved before reversible computer is being built. It is shown that a conventional reversible computer would require energy for setting up the reversible inputs from irreversible signals, for the reading out of the reversible outputs, for the transport of the information between logic elements and finally for the control signals that will require more energy dissipating into the environment. A loose bound on the minimum amount of energy required to be dissipated during the physical implementation of a reversible computer is obtained and a generalization of the principles for reversible computing is provided. It can save readers a click in deciding if they want to go for the whole paper or not. Think of the abstract as an upper bound on whether the paper is interesting or not. A paper could possibly be less interesting than its abstract, it is much less likely that it is more interesting than its abstract unless the author really messed up.
    - deleted 10y ago
      [deleted]
    - brudgers 10y ago
      Personally, I usually click on links based on the title more often than based on the comments. But I know other people have different habits. With a direct link to the PDF, the abstract is at the top of the PDF for anyone who wants to read it. For me personally, if I have the paper, I skip the abstract and read the introduction because it is more interesting and I don't feel a duty to bore myself reading the abstract. Here, I thought the title was interesting enough to click on the link and the paper interesting enough to provide a link to the less noisy original.
  - sctb 10y ago
    There's a small tradeoff in that not all readers might want to commit up-front to downloading a PDF. In the case of arXiv the abstract will be also updated with later versions of the paper if they appear.
    - brudgers 10y ago
      With Firefox the resource located at the arXiv URL of the PDF is smaller than the the resource located at the arXiv URL for the abstract. So goes the modern web. Both are an order of magnitude smaller than the originally submitted link. For me, the conventionality of UI of the PDF resource makes it easier to navigate than the UI of the resource for its metadata. Admittedly, I don't have a use case that is dominated by revisions to preprint journal articles...I just want to check papers out.
- sctb 10y ago
  Thanks, we've updated the link from https://www.researchgate.net/publication/314115814_Building_a_Completely_Reversible_Computer https://www.researchgate.net/publication/314115814_Building_....

stevemk14ebr 10y ago

what is meant by reversible?

naasking 10y ago
https://en.wikipedia.org/wiki/Reversible_computing https://en.wikipedia.org/wiki/Reversible_computing
SilasX 10y ago
Logically (and therefore thermodynamically) reversible. By Landauer's principle, the only reason a computer must emit heat (and therefore use energy) is to perform irreversible operations. Therefore, if you want a computer that (potentially) uses the minimum energy, it needs to be reversible in this sense. An irreversible operation is anything that maps many (possible) states to the same state. Setting a bit to zero is irreversible (because it destroys the information about what bit was there previously). An AND gate is irreversible (because both TF and FT map to F). A NOT gate is reversible (because you can infer the input from the output.) There are universal reversible gates (Toffoli and Fredkin gates are examples, but there are many others), so you can (theoretically) build a (usable) computer whose logical operations are completely reversible.
- sadgit 10y ago
  Does this imply that physical entropy and informational entropy are the same? Does it imply the computer would not give off heat? Or that a significant amount of the heat generated by a computer is due to information loss?
  - SilasX 10y ago
    >Does this imply that physical entropy and informational entropy are the same? It does, and there is a very strong (but not universally accepted) case that they are the same thing: https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_... Great lay article about it: http://lesswrong.com/lw/o5/the_second_law_of_thermodynamics_and_engines_of/ http://lesswrong.com/lw/o5/the_second_law_of_thermodynamics_... (Side note: I've long thought you can derive Carnot efficiency based on information-theoretic arguments about the information contained in knowing only the temperature difference between a heat source and a sink.) >Does it imply the computer would not give off heat? Or that a significant amount of the heat generated by a computer is due to information loss? Basically, yes. You can't avoid the heat emission from setting a 0 to a 1 on that computer's storage medium, but you would avoid the loss from any of the intermediate computations that typically make CPUs so hot.

dkarapetyan 10y ago

So reversible computing requires less energy not more right? Last I heard it is damn hard to forget information.

VLM 10y ago
Much less, in theory. At an imaginary hand waving level imagine the complete state of a cpu as passing charged capacitors around and occasionally charging new ones or discharging some. This is not all that far off of how they work... If you want to count to 7 reversibly there's an easy way involving hitting a 7 bit shift register, 7 times. In theory there's no reason to drain any capacitors per op or per the entire system, that same unit of charge just meanders down the line. Like a CCD sensor or old fashioned bubble memory kinda. The way chips are designed today that doesn't work, but insert a lot of kinda sorta in theory it could be done. On the other hand if you want to count to 7 using three full binary adders you're going to run into scenarios where two bits enter an adder (say, 001+001) and one bit leaves (result of 010), so at least one capacitors worth of charge got turned to heat. And that charging and discharging is basically wasting battery power for no good reason. And its not a lot of power for one capacitor, but you toggle a flip flop a couple billion times a second and then not-much adds up over time to a pretty hot CPU.
- abecedarius 10y ago
  That last issue can be handled by encoding each logical bit as a pair of physical signals (like low/high for 0, high/low for 1). I don't think there's any reason you can't implement your reversible counter in binary.
murbard2 10y ago
In theory yes, the catch is that you're not allowed to forget information. For instance, you cannot use an "AND" gate, because a result of 0 would be ambiguous, but you can use the Toffoli gate [1] which takes three inputs and produces three outputs, mapping (a,b,c) to (a,b,c^(a&b)). But what happens to the outputs you don't need? They do need to go somehere. A reversible circuit ends up having a lot of unused outputs which need to be erased if the circuit is to be reused. In essence, we have traded a heatsink for a bitsink, but they are essentially the same thing. I don't see reversible computing as categorically different from regular computing. It's regular computing, with careful and detailed heat management. [1] https://en.wikipedia.org/wiki/Toffoli_gate https://en.wikipedia.org/wiki/Toffoli_gate

mrfusion 10y ago

Are there limitations for a reversible computer? Could this run Firefox someday?

marcosdumay 10y ago
It is only capable of reversible operations. A completely reversible computer could not interact with you. This paper goes long about how you can irreversibly initialize such a computer, run it, and then irreversibly read its results, and how much power you can save doing that. In practice the computers people could build were always slow and inefficient, nothing comparable to the computers we are used to have (not even to the usual microcontrollers).
- johncolanduoni 10y ago
  It's also worth noting that even low-power chip designers would laugh at worrying about nkT losses from throwing bits away. Our technology is very far away from the thermodynamic limit for irreversible computers.

deleted 10y ago

[deleted]

openasocket 10y ago

What are the limitations to a completely reversible computer? I'm guessing it's still Turing complete, but do you pay a cost in terms of asymptotic complexity? I'm guessing you can make a program reversible trivially by doing something like making everything immutable and only ever appending new data, but of course that's extremely inefficient in terms of memory. Of course, I might be missing the core concept here.

SilasX 10y ago
AIUI, it's just a linear penalty because, at worst, you have to run each computation backwards to "uncompute it". That's under the (necessary) assumption that you don't even try to avoid erasure operations that need for their own sake rather than as an intermediate step.
- aparent 10y ago
  It is a bit more complicated then that. The only penalty to time is a constant factor if you are willing to use space proportional to the computation time. I did a bit of work on how to do time-space trade-offs in reversible circuits in my masters thesis http://hdl.handle.net/10012/10949 http://hdl.handle.net/10012/10949.

ArchReaper 10y ago

What kind of applications would this actually be useful for? I don't think I really understand the benefit(s) here.

Zaak 10y ago
The benefit of a reversible computer is that there is no minimum amount of energy it must dissipate as heat in order to perform its computations. Every time a bit of information is erased, a certain amount of energy must be dissipated as heat. A reversible computer doesn't (have to) erase information. Reversible computing is energy-aware computing taken to its logical extreme.
- ArchReaper 10y ago
  I get that. The concept of saving energy is what I do understand. What I don't understand is what kind of applications this could actually be used for. Given the (by-design) limitations of such a system, how would it be actually usable? What real-world scenarios would want this and be able to utilize it?
  - comicjk 10y ago
    Physics simulations. I work in drug design, and my field would be enormously benefited by this. Quantum mechanics calculations are naturally reversible.
    - johncolanduoni 10y ago
      The interior of the computation is reversible, but the measurement performed at the end most definitely is not. If it were, quantum computers would be able to solve NP-complete problems trivially, and complexity theorists would get pissed that physicists were holding out on them for decades.
      - Entalpi 10y ago
        Can you expand on this?

ballenf 10y ago

A couple questions: 1. How does "reversible" here apply to encryption algorithms? In a sense the encryption key is forgotten, but with enough computing power it can be derived from the output (at least for certain encryption methods). So, in a sense no information is lost. 2. If two separate computers perform the same reversible operation, but one in reverse, are the two computers (if considered as one system) consuming no energy? Or must the operations be performed on the same computer sequentially? If the system of two computers is valid, then does that mean that somehow certain operations / calculations produce energy and others consume it? I realize both these questions are somewhat nonsensical, so I clearly am missing something fundamental about this theory.

Zaak 10y ago
2. Reversible operations have no minimum amount of energy that must be dissipated as heat, unlike irreversible operations which must dissipate every time bits are erased. So each computer individually could be consuming no energy, so both together would consume the sum (zero) of the two.
undersuit 10y ago
On 2. You can't run reversible logic on our currently non-reversible logic and expect to see less power usage. If you had two reversible computers you could reverse the output of the other while consuming minimal energy just as a single reversible computer could reverse it's own output. The operations must be run forward at least once, or technically you don't have the outputs to input to the reverse.
johncolanduoni 10y ago
Reversible (in the paper's sense) is more about the paths information takes than whether it's recoverable in principle. Lossless compression is reversible, but a reversible computer performing it would still need to have storage equal to the size of the entire original data. It's also important to note that the fact that you are doing calculations isn't the direct cause of energy consumption. Landhauer's principle is a consequence of the second law of thermodynamics, which mandates certain heat losses in certain situations but doesn't tell you anything about how they happen. The question of what actually causes the second law of thermodynamics to hold at the level of fundamental interactions is called Loschmidt's paradox, and there's not really a consensus as to whether we have an answer.

cmrx64 10y ago

See also a type system and programming language for reversible computations: http://gradworks.umi.com/35/87/3587675.html http://gradworks.umi.com/35/87/3587675.html

ajb 10y ago

OT: when I click on this, researchgate claims "People who read this publication also read 'Is minimal hepatic encephalopathy completely reversible following liver transplantation?' I don't believe them.

yorwba 10y ago
Maybe someone was searching for "completely reversible" and got intrigued? But I guess a recommender system is the more likely explanation.
- mahmud 10y ago
  Not a recommender system or anything that intelligent. This is basically a keyword search of the paper titles. Even something as simple as term-frequence analysis would place the two papers far apart.

adrianratnapala 10y ago

Here https://arxiv.org/abs/1702.08715 https://arxiv.org/abs/1702.08715 is a link to the same article that might be a little easier to use.

karmicthreat 10y ago

So does this mean you can move the entropy cost around? For stack or 3D computing moving the heat cost to directly heatsinked surfaces would be useful.