Reversible computing: Difference between revisions

Revision as of 19:00, 8 September 2022

Revision as of 20:30, 16 October 2022

Line 10:

A process is said to be ''physically reversible'' if it results in no increase in physical [[entropy]]; it is [[isentropic]]. There is a style of circuit design ideally exhibiting this property that is referred to as '''charge recovery logic'''<!--boldface per WP:R#PLA-->, [[adiabatic circuit]]s, or '''adiabatic computing'''<!--boldface per WP:R#PLA--> (see [[Adiabatic process]]). Although ''in practice'' no nonstationary physical process can be ''exactly'' physically reversible or isentropic, there is no known limit to the closeness with which we can approach perfect reversibility, in systems that are sufficiently well isolated from interactions with unknown external environments, when the laws of physics describing the system's evolution are precisely known.

A motivation for the study of technologies aimed at implementing reversible computing is that they offer what is predicted to be the only potential way to improve the [[computational energy efficiency]] of computers beyond the fundamental [[von Neumann-Landauer limit|von Neumann–Landauer limit]]<ref name="landauer">{{Citation |author=Rolf Landauer |url=http://worrydream.com/refs/Landauer%20-%20Irreversibility%20and%20Heat%20Generation%20in%20the%20Computing%20Process.pdf |title=Irreversibility and heat generation in the computing process |journal=IBM Journal of Research and Development |volume=5 |issue=3 |pages=183–191 |year=1961 |accessdate=2015-02-18 |doi=10.1147/rd.53.0183 |quote=The entropy of a closed system, e.g., a computer with its own batteries, cannot decrease; hence this entropy must appear else where as a heating effect, supplying 0.6931 kT per restored bit to the surroundings.}}</ref><ref name="neumann">{{cite book|author=J. von Neumann|author-link=John von Neumann|publisher=University of Illinois Press|title=Theory of self-reproducing automata|year=1966|url=https://archive.org/details/theoryofselfrepr00vonn_0|access-date=2022-05-21}} Third lecture: Statistical Theories about Information</ref> of {{Math|''[[kT (energy)|kT]]'' ln(2)}} energy dissipated per irreversible [[bit operation]]. Although the Landauer limit was millions of times below the energy consumption of computers in the 2000s and thousands of times less in the 2010s,<ref>{{cite journal |last1=Bérut |first1=Antoine |last2=Arakelyan |first2=Artak |last3=Petrosyan |first3=Artyom |last4=Ciliberto |first4=Sergio |last5=Dillenschneider |first5=Raoul |last6=Lutz |first6=Eric |title=Experimental verification of Landauer's principle linking information and thermodynamics |journal=Nature |date=March 2012 |volume=483 |issue=7388 |pages=187–189 |doi=10.1038/nature10872 |pmid=22398556 |bibcode=2012Natur.483..187B |arxiv=1503.06537 |s2cid=9415026 }}</ref> proponents of reversible computing argue that this can be attributed largely to architectural overheads which effectively magnify the impact of Landauer's limit in practical circuit designs, so that it may prove difficult for practical technology to progress very far beyond current levels of energy efficiency if reversible computing principles are not used.<ref>Michael P. Frank, "Foundations of Generalized Reversible Computing," to be published at the 9th Conference on Reversible Computation, Jul. 6-7, 2017, Kolkata, India. Preprint available at https://cfwebprod.sandia.gov/cfdocs/CompResearch/docs/grc-rc17-preprint2.pdf.</ref>

==Relation to thermodynamics==

Line 39:

Similarly, in the [[Turing machine]] model of computation, a reversible Turing machine is one whose transition function is invertible, so that each machine state has at most one predecessor.

[[:fr:Yves Lecerf|Yves Lecerf]] proposed a reversible Turing machine in a 1963 paper,<ref>Lecerf (Y.) : [http://vadeker.net/corpus/reversible/lecerf.pdf Logique Mathématique : Machines de Turing réversibles.] Comptes rendus des séances de l'académie des sciences, 257:2597--2600, 1963.</ref> but apparently unaware of Landauer's principle, did not pursue the subject further, devoting most of the rest of his career to ethnolinguistics. In 1973 [[Charles H. Bennett (physicist)|Charles H. Bennett]], at IBM Research, showed that a universal Turing machine could be made both logically and thermodynamically reversible,<ref>C. H. Bennett, "[http://www.dna.caltech.edu/courses/cs191/paperscs191/bennett1973.pdf Logical reversibility of computation]", IBM Journal of Research and Development, vol. 17, no. 6, pp. 525-532, 1973</ref> and therefore able in principle to perform an arbitrarily large number of computation steps per unit of physical energy dissipated, if operated sufficiently slowly. Thermodynamically reversible computers could perform useful computations at useful speed, while dissipating considerably less than ''[[kT (energy)|kT]]'' of energy per logical step. In 1982 [[Edward Fredkin]] and [[Tommaso Toffoli]] proposed the [[Billiard ball computer]], a mechanism using classical hard spheres to do reversible computations at finite speed with zero dissipation, but requiring perfect initial alignment of the balls' trajectories, and Bennett's review<ref>{{cite journal |last1=Bennett |first1=Charles H. |title=The thermodynamics of computation—a review |journal=International Journal of Theoretical Physics |date=December 1982 |volume=21 |issue=12 |pages=905–940 |doi=10.1007/BF02084158 |bibcode=1982IJTP...21..905B |s2cid=17471991 }}</ref> compared these "Brownian" and "ballistic" paradigms for reversible computation. Aside from the motivation of energy-efficient computation, reversible logic gates offered practical improvements of [[bit manipulation|bit-manipulation]] transforms in cryptography and computer graphics. Since the 1980s, reversible circuits have attracted interest as components of [[quantum algorithm]]s, and more recently in photonic and nano-computing technologies where some switching devices offer no [[signal gain]].

Surveys of reversible circuits, their construction and optimization, as well as recent research challenges, are available.<ref>Rolf Drechsler, Robert Wille. From Truth Tables to Programming Languages: Progress in the Design of Reversible Circuits. International Symposium on Multiple-Valued Logic, 2011. http://www.informatik.uni-bremen.de/agra/doc/konf/11_ismvl_reversible_circuit_design_tutorial.pdf</ref><ref>{{cite journal |last1=Saeedi |first1=Mehdi |last2=Markov |first2=Igor L. |title=Synthesis and optimization of reversible circuits—a survey |journal=ACM Computing Surveys |date=1 February 2013 |volume=45 |issue=2 |pages=1–34 |doi=10.1145/2431211.2431220 |arxiv=1110.2574 |s2cid=6302811 }}</ref><ref>Rolf Drechsler and Robert Wille. Reversible Circuits: Recent Accomplishments and Future Challenges for an Emerging Technology. International Symposium on VLSI Design and Test, 2012. http://www.informatik.uni-bremen.de/agra/doc/konf/2012_vdat_reversible_circuits_accompl_chall.pdf</ref><ref>{{cite journal |last1=Cohen |first1=Eyal |last2=Dolev |first2=Shlomi |last3=Rosenblit |first3=Michael |title=All-optical design for inherently energy-conserving reversible gates and circuits |journal=Nature Communications |date=26 April 2016 |volume=7 |issue=1 |pages=11424 |doi=10.1038/ncomms11424 |pmid=27113510 |pmc=4853429 |bibcode=2016NatCo...711424C }}</ref><ref>{{Cite journal|lastlast1 =Ang|firstfirst1 = Y. S.|last2 = Yang|first2 = S. A.|last3 = Zhang|first3 = C.|last4 = Ma|first4 = Z. S.|last5 = Ang|first5 = L. K.|date = 2017|title = Valleytronics in merging Dirac cones: All-electric-controlled valley filter, valve, and universal reversible logic gate|journal = Physical Review B|volume = 96|issue = 24|pages = 245410|doi = 10.1103/PhysRevB.96.245410|arxiv = 1711.05906|bibcode = 2017PhRvB..96x5410A| s2cid=51933139 }}</ref>

==See also==

Line 68:

==Further reading==

* {{cite journal |last1=Denning |first1=Peter |last2=Lewis |first2=Ted |title=Computers That Can Run Backwards |journal=American Scientist |date=2017 |volume=105 |issue=5 |pages=270 |doi=10.1511/2017.105.5.270 |s2cid=125446656 }}

* {{cite journal |last1=Lange |first1=Klaus-Jörn |last2=McKenzie |first2=Pierre |last3=Tapp |first3=Alain |title=Reversible Space Equals Deterministic Space |journal=Journal of Computer and System Sciences |date=April 2000 |volume=60 |issue=2 |pages=354–367 |doi=10.1006/jcss.1999.1672 |doi-access=free }}

* Perumalla K. S. (2014), ''Introduction to Reversible Computing'', [[CRC Press]].

* {{cite book |doi=10.1145/1062261.1062335 |chapter=Time, space, and energy in reversible computing |title=Proceedings of the 2nd conference on Computing frontiers - CF '05 |year=2005 |last1=Vitányi |first1=Paul |pages=435 |isbn=1595930191 |s2cid=5252384 }}

==External links==