Русская Википедия:Обратимые вычисления
Обратимые вычисления (Шаблон:Lang-en) — модель вычислений, в которой процесс вычисления является в некоторой степени обратимым. Например, в вычислительной модели, использующей наборы состояний и переходов между ними, необходимым условием обратимости вычислений является возможность построения однозначного (инъективного) отображения каждого состояния в следующее за ним. На 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] реализации обратимых вычислений был предложен в работах Шаблон:Нп3,[6][7] (IBM Research, 1973). В настоящее время множеством ученых предложены десятки концепций обратимых вычислений, включая обратимые логические вентили, электронные схемы, архитектуры процессоров, языки программирования, алгоритмы[8][9].
Логическая обратимость
Для реализаций обратимых вычислительных схем и оценок их сложности и ограничений используется формализация через обратимые вентили — аналоги логических вентилей. Например, вентиль инвертора NOT (НЕ) является обратимым, так как сохраняет информацию. В то же время логический вентиль исключительное ИЛИ (XOR) является необратимым — значения его входов не могут быть восстановлены из единственного выходного значения. Обратимым аналогом XOR может стать вентиль управляемого отрицания (CNOT — controlled NOT).
См. также
- Обратимость
- Вентиль Тоффоли
- Вентиль Фредкина
- Квантовый компьютер (квантовая часть вычислений должна быть обратима вплоть до момента измерения)
- Бильярдный компьютер
- Обратимый клеточный автомат
Примечания
Литература
- 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
- ↑ Шаблон:Cite web
- ↑ J. von Neumann, Theory of Self-Reproducing Automata, Univ. of Illinois Press, 1966.
- ↑ 3,0 3,1 Рольф Ландауэр «Необратимость и выделение тепла в процессе вычислений» // «Квантовый компьютер и квантовые вычисления. Том 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 Шаблон:Wayback, 1961.Шаблон:Ref-en - ↑ Bérut, Antoine, et al. «Experimental verification of Landauer/'s principle linking information and thermodynamics. Шаблон:Wayback» 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 Шаблон:Wayback // IEEE Spectrum, 7 Mar 2012 - ↑ Who invented reversible computing? Шаблон:Wayback // Reversible Computing FAQШаблон:Ref-en
- ↑ 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.
- ↑ Шаблон:Книга
- ↑ Шаблон:Книга
