Обратимые вычисления

Обратимые вычисления (англ. reversible computing) — модель вычислений, в которой процесс вычисления является в некоторой степени обратимым. Например, в вычислительной модели, использующей наборы состояний и переходов между ними, необходимым условием обратимости вычислений является возможность построения однозначного (инъективного) отображения каждого состояния в следующее за ним. На XX век и начало XXI века обратимые вычисления обычно относят к нетрадиционным моделям вычислений.

Обратимость

Существует два основных типа обратимости вычислений: физически обратимые и логически обратимые.[1]

Процесс физически обратим, если по его завершению система не увеличила свою физическую энтропию, то есть процесс является изоэнтропийным. Физически обратимые схемы: charge-recovery logic (сохраняющая заряд логика), адиабатические схемы, адиабатические вычисления. На практике нестационарный физический процесс не может быть полностью физически обратимым (изоэнтропийным), однако для хорошо изолированных систем возможно приближение к полной обратимости.

Вероятно, наибольшим стимулом изучения технологий для реализации обратимых вычислений является то, что они представляются единственным способом улучшить энергоэффективность вычислений за фундаментальные пределы, предсказанные принципом Неймана — Ландауэра[2][3], согласно которому выделяется по крайней мере kT ln(2) теплоты (около 3×10−21 Дж при T=300K) на каждую необратимую операцию над битом (при стирании бита информации). На начало XXI века компьютеры рассеивали примерно в миллион раз больше тепла, на начало 2010-х разница снизилась до нескольких тысяч[4].

Отношение к термодинамике

Как было показано Рольфом Ландауэром из IBM в 1961 году[3], для того, чтобы процесс вычислений был физически обратимым, требуется, чтобы он также был логически обратимым (logically reversible). В принципе Ландауэра им впервые было сформулировано правило, согласно которому стирание N бит неизвестной информации всегда связано с увеличением термодинамической энтропии на величину по крайней мере равную Nk ln(2). Дискретный детерминированный процесс вычислений называется логически обратимым в случае, если функция переходов, отображающая старое состояние системы в новое является инъективной (каждому новому состоянию однозначно соответствует одно старое состояние), то есть, по информации о конечном логическом состоянии схемы возможно определить входное логическое состояние схемы.

Для недетерминированных (вероятностных или случайных) процессов физическая обратимость может достигаться при менее строгих ограничениях, а именно, при условии неуменьшения совокупности всех возможных начальных состояний (в среднем) в процессе вычисления.

Физическая обратимость

Один из первых вариантов[5] реализации обратимых вычислений был предложен в работах Чарльза Беннетта,[6][7] (IBM Research, 1973). В настоящее время множеством ученых предложены десятки концепций обратимых вычислений, включая обратимые логические вентили, электронные схемы, архитектуры процессоров, языки программирования, алгоритмы[8][9].

Логическая обратимость

Для реализаций обратимых вычислительных схем и оценок их сложности и ограничений используется формализация через обратимые вентили — аналоги логических вентилей. Например, вентиль инвертора NOT (НЕ) является обратимым, так как сохраняет информацию. В то же время логический вентиль исключительное ИЛИ (XOR) является необратимым — значения его входов не могут быть восстановлены из единственного выходного значения. Обратимым аналогом XOR может стать вентиль управляемого отрицания (CNOT — controlled NOT).

См. также

Примечания
  1. The Reversible and Quantum Computing Group (Revcomp)
  2. J. von Neumann, Theory of Self-Reproducing Automata, Univ. of Illinois Press, 1966.
  3. Рольф Ландауэр «Необратимость и выделение тепла в процессе вычислений» // «Квантовый компьютер и квантовые вычисления. Том 2», 1999, ISBN 5-7029-0338-2, стр. 9-32;
    Rolf Landauer: «Irreversibility and heat generation in the computing process» // IBM Journal of Research and Development, vol. 5, pp. 183—191, 1961. (англ.)
  4. Bérut, Antoine, et al. «Experimental verification of Landauer/'s principle linking information and thermodynamics.» Nature 483.7388 (2012): 187—189: «From a technological perspective, energy dissipation per logic operation in present-day silicon-based digital circuits is about a factor of 1,000 greater than the ultimate Landauer limit, but is predicted to quickly attain it within the next couple of decades»
    Samuel K. Moore, Landauer Limit Demonstrated. Scientists show that a 50-year-old principle limiting future CMOS computing is real: Erasing information gives off heat // IEEE Spectrum, 7 Mar 2012
  5. Who invented reversible computing? // Reversible Computing FAQ (англ.)
  6. C. H. Bennett, "Logical reversibility of computation, " IBM Journal of Research and Development, vol. 17, no. 6, pp. 525—532, 1973.
  7. C. H. Bennett, "The Thermodynamics of Computation — A Review, " International Journal of Theoretical Physics, vol. 21, no. 12, pp. 905—940, 1982.
  8. Alexis De Vos. Reversible Computing: Fundamentals, Quantum Computing, and Applications. — Wiley, 2010. — 261 с. — ISBN 978-3-527-40992-1.
  9. Kalyan S. Perumalla. Introduction to Reversible Computing. — CRC Press, 2013. — 325 с. — ISBN 9781439873403.

Литература
  • P.M.B. Vitanyi, Time, space, and energy in reversible computing, Proceedings of the 2nd ACM conference on Computing frontiers, 2005, 435—444.
  • Introduction to Reversible Computing by Kalyan S. Perumalla

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.