Обратимые вычисления (KQjgmnbdy fdcnvlyunx)

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

Обратимость

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

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

Вероятно, наибольшим стимулом изучения технологий для реализации обратимых вычислений является то, что они представляются единственным способом улучшить энергоэффективность вычислений за фундаментальные пределы, предсказанные принципом Неймана — Ландауэра^[2]^[3], согласно которому выделяется по крайней мере kT ln(2) теплоты (около 3×10⁻²¹ Дж при 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).

См. также

Обратимость
Вентиль Тоффоли
Вентиль Фредкина
Квантовый компьютер (квантовая часть вычислений должна быть обратима вплоть до момента измерения)
Бильярдный компьютер
Обратимый клеточный автомат

Примечания

↑ The Reversible and Quantum Computing Group (Revcomp) (неопр.). Дата обращения: 4 января 2015. Архивировано 22 января 2021 года.
↑ J. von Neumann, Theory of Self-Reproducing Automata, Univ. of Illinois Press, 1966.
↑ ¹ ² Рольф Ландауэр «Необратимость и выделение тепла в процессе вычислений» // «Квантовый компьютер и квантовые вычисления. Том 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 Архивная копия от 23 октября 2016 на Wayback Machine, 1961. (англ.)
↑ Bérut, Antoine, et al. «Experimental verification of Landauer/'s principle linking information and thermodynamics. Архивная копия от 28 февраля 2015 на Wayback Machine» 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 Архивная копия от 22 ноября 2013 на Wayback Machine // IEEE Spectrum, 7 Mar 2012
↑ Who invented reversible computing? Архивная копия от 6 сентября 2014 на Wayback Machine // Reversible Computing FAQ (англ.)
↑ C. H. Bennett, "Logical reversibility of computation, " IBM Journal of Research and Development, vol. 17, no. 6, pp. 525—532, 1973.
↑ C. H. Bennett, "The Thermodynamics of Computation — A Review, " International Journal of Theoretical Physics, vol. 21, no. 12, pp. 905—940, 1982.
↑ Alexis De Vos. Reversible Computing: Fundamentals, Quantum Computing, and Applications. — Wiley, 2010. — 261 с. — ISBN 978-3-527-40992-1.
↑ 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

Ссылки

Introductory article on reversible computing
First International Workshop on reversible computing
Recent publications of Michael P. Frank
Internet Archive backup of the «Reversible computing community Wiki» that was administered by Dr. Frank
Recent Workshops on Reversible Computation
Open-source toolkit for reversible circuit design

[1] The Reversible and Quantum Computing Group (Revcomp) (неопр.). Дата обращения: 4 января 2015. Архивировано 22 января 2021 года.

[neumann-2] J. von Neumann, Theory of Self-Reproducing Automata, Univ. of Illinois Press, 1966.

[landauer-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 Архивная копия от 23 октября 2016 на Wayback Machine, 1961. (англ.)

[4] Bérut, Antoine, et al. «Experimental verification of Landauer/'s principle linking information and thermodynamics. Архивная копия от 28 февраля 2015 на Wayback Machine» 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 Архивная копия от 22 ноября 2013 на Wayback Machine // IEEE Spectrum, 7 Mar 2012

[5] Who invented reversible computing? Архивная копия от 6 сентября 2014 на Wayback Machine // 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]