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

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

Обратимость

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

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

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

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

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

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

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

Один из первых вариантов реализации обратимых вычислений был предложен в работах (англ.) ( , (IBM Research, 1973). В настоящее время множеством ученых предложены десятки концепций обратимых вычислений, включая обратимые логические вентили, электронные схемы, архитектуры процессоров, языки программирования, алгоритмы .

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

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

См. также

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

Примечания

. Дата обращения: 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, от 23 октября 2016 на Wayback Machine , 1961. (англ.)
Bérut, Antoine, et al. « от 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, от 22 ноября 2013 на Wayback Machine // IEEE Spectrum, 7 Mar 2012
от 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. . — Wiley, 2010. — 261 с. — ISBN 978-3-527-40992-1 .
Kalyan S. Perumalla. . — 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