Реверсивные вычисления

Обратимые вычисления — это любая модель вычислений , в которой вычислительный процесс в некоторой степени обратим во времени . В модели вычислений, которая использует детерминированные переходы от одного состояния абстрактной машины к другому, необходимым условием обратимости является то, что отношение отображения состояний к их преемникам должно быть взаимно однозначным . Реверсивные вычисления — это форма нетрадиционных вычислений .

Из-за унитарности квантовые квантовой механики в схемы обратимы до тех пор, пока они не « коллапсируют » квантовые состояния, которых они действуют. ^[1]

обратимость

Есть два основных, тесно связанных типа обратимости, которые представляют особый интерес для этой цели: физическая обратимость и логическая обратимость . ^[2]

Процесс называется физически обратимым , если он не приводит к увеличению физической энтропии ; он изэнтропичен . Существует стиль проектирования схем, идеально демонстрирующий это свойство, который называется логикой восстановления заряда , адиабатическими схемами или адиабатическими вычислениями (см. Адиабатический процесс ). Хотя на практике ни один нестационарный физический процесс не может быть точно физически обратимым или изэнтропическим, не существует известного предела близости, с которой мы можем приблизиться к идеальной обратимости в системах, достаточно хорошо изолированных от взаимодействий с неизвестной внешней средой, когда законы физики описывающие эволюцию системы, точно известны.

Мотивом для изучения технологий, направленных на реализацию обратимых вычислений, является то, что они предлагают то, что, по прогнозам, является единственным потенциальным способом повышения вычислительной энергоэффективности (т. е. количества полезных операций, выполняемых на единицу рассеиваемой энергии) компьютеров, помимо фундаментального принципа фон Неймана – Предел Ландауэра ^[3]^[4] энергии $kT ln(2),$ рассеиваемой за необратимую битовую операцию . Хотя предел Ландауэра был в миллионы раз ниже энергопотребления компьютеров в 2000-х и в тысячи раз меньше в 2010-х, ^[5] Сторонники обратимых вычислений утверждают, что это можно объяснить в основном архитектурными накладными расходами, которые эффективно усиливают влияние ограничения Ландауэра на практические проекты схем, так что практической технологии может оказаться затруднительным продвинуться далеко за пределы нынешнего уровня энергоэффективности, если принципы обратимых вычислений не используются. ^[6]

Связь с термодинамикой

Как впервые заявил Рольф Ландауэр, работая в IBM , ^[7] Чтобы вычислительный процесс был физически обратимым, он также должен быть обратимым логически . Принцип Ландауэра заключается в наблюдении, что забвение стирания n бит известной информации всегда должно повлечь за собой затраты в размере $nkT ln(2)$ в виде термодинамической энтропии . Дискретный детерминированный вычислительный процесс называется логически обратимым, если функция перехода, которая отображает старые вычислительные состояния в новые, является функцией «один к одному» ; т.е. выходные логические состояния однозначно определяют входные логические состояния вычислительной операции.

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

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

Принцип Ландауэра (и, по сути, второй закон термодинамики ) также можно понимать как прямое логическое следствие лежащей в основе обратимости физики , что отражено в общей гамильтоновой формулировке механики и в эволюции во времени . унитарном операторе квантовой механика точнее. ^[8]

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

Хотя достижение этой цели представляет собой серьезную проблему для проектирования, производства и определения характеристик новых сверхточных физических механизмов для вычислений , в настоящее время нет фундаментальных оснований полагать, что эта цель в конечном итоге не может быть достигнута, что позволит когда-нибудь создавать компьютеры, генерирующие Физическая энтропия гораздо меньше 1 бита (и рассеивается гораздо меньше энергии на нагревание, чем кТл ln 2) на каждую полезную логическую операцию, которую они выполняют внутри.

Сегодня в этой области имеется значительный объем научной литературы. множество концепций обратимых устройств, логических элементов , электронных схем , архитектур процессоров, языков программирования и прикладных алгоритмов было разработано и проанализировано Физиками , инженерами-электриками и компьютерщиками .

Эта область исследований ожидает детальной разработки высококачественной, экономичной, почти обратимой технологии логических устройств, которая включает в себя высокоэнергетические механизмы тактирования и синхронизации или позволяет избежать необходимости в них за счет асинхронного проектирования. Такого рода солидный инженерный прогресс будет необходим, прежде чем большой объем теоретических исследований в области обратимых вычислений сможет найти практическое применение, позволяя реальной компьютерной технологии обойти различные краткосрочные барьеры на пути к ее энергоэффективности, включая границу фон Неймана-Ландауэра. Этого можно обойти только с помощью логически обратимых вычислений, согласно второму закону термодинамики . ^[9]

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

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

Вентиль инвертора можно (НЕ) логически обратим, поскольку его отменить . Однако вентиль НЕ может быть физически обратимым, в зависимости от его реализации.

Исключающий вентиль или (XOR) необратим, поскольку его два входа не могут быть однозначно восстановлены из его единственного выхода, или, альтернативно, потому что стирание информации необратимо. Однако обратимую версию логического элемента исключающее ИЛИ — управляемый вентиль НЕ (CNOT) — можно определить, сохранив один из входов в качестве второго выхода. Трехвходовой вариант вентиля CNOT называется вентилем Тоффоли . Он сохраняет два своих входа a,b и заменяет третий c на $c\oplus (a\cdot b)$ . С $c=0$ , это дает функцию И, и с $a\cdot b=1$ это дает функцию НЕ. Поскольку И и НЕ вместе представляют собой функционально полный набор, вентиль Тоффоли универсален и может реализовать любую логическую функцию (если задано достаточное количество инициализированных вспомогательных битов ).

Аналогично, в модели вычислений машины Тьюринга обратимая машина Тьюринга — это машина, функция перехода которой обратима, так что каждое состояние машины имеет не более одного предшественника.

Ив Лесерф предложил обратимую машину Тьюринга в статье 1963 года. ^[10] но, очевидно, не зная о принципе Ландауэра, не стал развивать эту тему дальше, посвятив большую часть своей карьеры этнолингвистике. В 1973 году Чарльз Х. Беннетт из IBM Research показал, что универсальную машину Тьюринга можно сделать как логически, так и термодинамически обратимой. ^[11] и, следовательно, в принципе способен выполнять сколь угодно большое количество вычислительных шагов на единицу рассеиваемой физической энергии, если работать достаточно медленно. Термодинамически обратимые компьютеры могли бы выполнять полезные вычисления с полезной скоростью, рассеивая при этом значительно меньше кТ энергии на логический шаг. В 1982 году Эдвард Фредкин и Томмазо Тоффоли предложили компьютер для бильярдных шаров , механизм, использующий классические твердые сферы для выполнения обратимых вычислений на конечной скорости с нулевой диссипацией, но требующий идеального начального выравнивания траекторий шаров, и обзор Беннета. ^[12] сравнил эти «броуновскую» и «баллистическую» парадигмы обратимых вычислений. Помимо стимулирования энергоэффективных вычислений, обратимые логические элементы предложили практические улучшения преобразований битовых манипуляций в криптографии и компьютерной графике. С 1980-х годов обратимые схемы вызывают интерес как компоненты квантовых алгоритмов , а в последнее время — в фотонных и нанокомпьютерных технологиях, где некоторые переключающие устройства не обеспечивают усиления сигнала .

Доступны обзоры обратимых схем, их конструкции и оптимизации, а также недавних исследовательских задач. ^[13]^[14]^[15]^[16]^[17]

См. также

Адиабатическая схема - электронные схемы малой мощности, в которых используется обратимая логика для экономии энергии.
Двунаправленное преобразование - компьютерные программы, способные производить входные данные из выходных данных.
Компьютер с бильярдным шаром - тип консервативной логической схемы.
Ворота Фредкина - универсальный обратимый логический вентиль, применяемый в квантовых вычислениях.
Обобщенный подъем — метод вейвлет-анализа.
Янус (язык программирования обратимых во времени вычислений) - язык программирования обратимых во времени вычислений.
Термодинамика максимальной энтропии - Применение теории информации к термодинамике и статистической механике, интерпретация неопределенности второго закона термодинамики.
Демон Максвелла - мысленный эксперимент 1867 года.
Обратное вычисление
Обратимый клеточный автомат - клеточный автомат, который можно запускать в обратном направлении.
Обратимая динамика — тип физического или математического процесса.
Обратимый процесс (термодинамика) - термодинамический процесс, направление которого можно изменить, чтобы вернуть систему в исходное состояние.
Квантовые вычисления - технология, использующая квантовую механику.
Клеточный автомат с квантовыми точками - тип клеточного автомата, вариант обратимого клеточного автомата.
Ворота Тоффоли - универсальный обратимый логический вентиль, применяемый в квантовых вычислениях.
Сверхпроводящие квантовые вычисления - реализация квантовых вычислений
Невычисление - метод, используемый в обратимых схемах.
Нетрадиционные вычисления - вычисления новыми или необычными методами.

Ссылки

^ Уильямс, Колин П. (2011). Исследования в области квантовых вычислений . Спрингер . стр. 25–29. ISBN 978-1-84628-887-6 .
^ «Группа обратимых и квантовых вычислений (Revcomp)» .
^ Ландауэр, Рольф (1961), «Необратимость и выделение тепла в вычислительном процессе» (PDF) , IBM Journal of Research and Development , 5 (3): 183–191, doi : 10.1147/rd.53.0183 , получено 2015-02- 18. Энтропия закрытой системы, например компьютера с собственными батареями, не может уменьшаться; следовательно, эта энтропия должна проявляться где-то еще в виде эффекта нагрева, передавая в окружающую среду 0,6931 кТл на каждый восстановленный бит.
^ Дж. фон Нейман (1966). Теория самовоспроизводящихся автоматов . Издательство Университета Иллинойса . Проверено 21 мая 2022 г. Третья лекция: Статистические теории информации.
^ Берют, Антуан; Аракелян, Артак; Петросян, Артём; Силиберто, Серджио; Дилленшнейдер, Рауль; Лутц, Эрик (март 2012 г.). «Экспериментальная проверка принципа Ландауэра, связывающего информацию и термодинамику». Природа . 483 (7388): 187–189. arXiv : 1503.06537 . Бибкод : 2012Natur.483..187B . дои : 10.1038/nature10872 . ПМИД 22398556 . S2CID 9415026 .
^ Майкл П. Франк. Основы обобщенных обратимых вычислений. Конференция по обратимым вычислениям, 6–7 июля 2017 г., Калькутта, Индия. doi:10.1007/978-3-319-59936-6 2 Препринт доступен по адресу https://www.osti.gov/servlets/purl/1456440 (PDF).
^ Ландауэр, Р. (июль 1961 г.). «Необратимость и тепловыделение в вычислительном процессе». Журнал исследований и разработок IBM . 5 (3): 183–191. дои : 10.1147/рд.53.0183 .
^ Фрэнк, Майкл П.; Шукла, Карпур (1 июня 2021 г.). «Квантовые основы классических обратимых вычислений» . Энтропия . 23 (6): 701. arXiv : 2105.00065 . Бибкод : 2021Entrp..23..701F . дои : 10.3390/e23060701 . ISSN 1099-4300 . ПМЦ 8228632 . ПМИД 34206044 .
^ Фрэнк, Майкл П. (2018). «Физические основы принципа Ландауэра» . В Кари, Яркко; Улидовский, Ирек (ред.). Обратимые вычисления . Конспекты лекций по информатике. Том. 11106. Чам: Springer International Publishing. стр. 3–33. arXiv : 1901.10327 . дои : 10.1007/978-3-319-99498-7_1 . ISBN 978-3-319-99498-7 . S2CID 52135244 .
^ Лецерф (Ю.): Математическая логика: обратимые машины Тьюринга. Труды сессий Академии наук, 257: 2597–2600, 1963.
^ CH Bennett, « Логическая обратимость вычислений », IBM Journal of Research and Development, vol. 17, нет. 6, стр. 525–532, 1973 г.
^ Беннетт, Чарльз Х. (декабрь 1982 г.). «Термодинамика вычислений - обзор». Международный журнал теоретической физики . 21 (12): 905–940. Бибкод : 1982IJTP...21..905B . дои : 10.1007/BF02084158 . S2CID 17471991 .
^ Рольф Дрекслер, Роберт Вилле. От таблиц истинности к языкам программирования: прогресс в разработке обратимых схем. Международный симпозиум по многозначной логике, 2011 г. http://www.informatik.uni-bremen.de/agra/doc/konf/11_ismvl_reversible_circuit_design_tutorial.pdf
^ Саиди, Мехди; Марков, Игорь Л. (1 февраля 2013 г.). «Синтез и оптимизация обратимых схем — обзор». Обзоры вычислительной техники ACM . 45 (2): 1–34. arXiv : 1110.2574 . дои : 10.1145/2431211.2431220 . S2CID 6302811 .
^ Рольф Дрекслер и Роберт Вилле. Реверсивные схемы: недавние достижения и будущие задачи новой технологии. Международный симпозиум по проектированию и испытаниям СБИС, 2012 г. http://www.informatik.uni-bremen.de/agra/doc/konf/2012_vdat_reversible_circuits_accompl_chall.pdf
^ Коэн, Эяль; Долев, Шломи; Розенблит, Майкл (26 апреля 2016 г.). «Полностью оптическая конструкция для энергосберегающих обратимых вентилей и схем» . Природные коммуникации . 7 (1): 11424. Бибкод : 2016NatCo...711424C . дои : 10.1038/ncomms11424 . ПМЦ 4853429 . ПМИД 27113510 .
^ Анг, Ю.С.; Ян, SA; Чжан, К.; Ма, З.С.; Анг, ЛК (2017). «Valleytronics в объединении конусов Дирака: полностью электрический фильтр долины, клапан и универсальный обратимый логический вентиль». Физический обзор B . 96 (24): 245410. arXiv : 1711.05906 . Бибкод : 2017PhRvB..96x5410A . дои : 10.1103/PhysRevB.96.245410 . S2CID 51933139 .

Дальнейшее чтение

Фрэнк, Майкл П. (2017). «Будущее вычислений зависит от их обратимости» (Интернет) / «Переворот вычислений в обратную сторону» (печать). IEEE Spectrum . 54 (9): 32–37. doi:10.1109/MSPEC.2017.8012237 .
Деннинг, Питер; Льюис, Тед (2017). «Компьютеры, которые могут работать в обратном направлении». Американский учёный . 105 (5): 270. дои : 10.1511/2017.105.5.270 . S2CID 125446656 .
Глюк, Роберт; Ёкояма, Тецуо (2023). «Обратимые вычисления с точки зрения языка программирования» . Теоретическая информатика . 953 : 113429. doi : 10.1016/j.tcs.2022.06.010 .
Ланге, Клаус-Йёрн; Маккензи, Пьер; Тапп, Ален (апрель 2000 г.). «Обратимое пространство равно детерминированному пространству» . Журнал компьютерных и системных наук . 60 (2): 354–367. дои : 10.1006/jcss.1999.1672 .
Перумалла К.С. (2014), Введение в обратимые вычисления , CRC Press .
Витаньи, Пол (2005). «Время, пространство и энергия в обратимых вычислениях». Материалы 2-й конференции по передовым технологиям – CF '05 . стр. 435–444. дои : 10.1145/1062261.1062335 . ISBN 1595930191 . S2CID 5252384 .

Внешние ссылки

Вводная статья об обратимых вычислениях
Первый международный семинар по обратимым вычислениям
Публикации Майкла П. Франка: Sandia (2015-) , FSU (2004-'15) , UF (1999-2004) , MIT 1996-'99 ).
Резервная копия Интернет-архива «Вики-сайта сообщества обратимых вычислений», которым руководил Фрэнк.
Серия семинаров/конференций по обратимым вычислениям
Семинар CCC по физико-техническим проблемам адиабатических/обратимых классических вычислений
Набор инструментов с открытым исходным кодом для обратимого проектирования схем

[Williams-1] Уильямс, Колин П. (2011). Исследования в области квантовых вычислений . Спрингер . стр. 25–29. ISBN 978-1-84628-887-6 .

[2] «Группа обратимых и квантовых вычислений (Revcomp)» .

[landauer-3] Ландауэр, Рольф (1961), «Необратимость и выделение тепла в вычислительном процессе» (PDF) , IBM Journal of Research and Development , 5 (3): 183–191, doi : 10.1147/rd.53.0183 , получено 2015-02- 18. Энтропия закрытой системы, например компьютера с собственными батареями, не может уменьшаться; следовательно, эта энтропия должна проявляться где-то еще в виде эффекта нагрева, передавая в окружающую среду 0,6931 кТл на каждый восстановленный бит.

[neumann-4] Дж. фон Нейман (1966). Теория самовоспроизводящихся автоматов . Издательство Университета Иллинойса . Проверено 21 мая 2022 г. Третья лекция: Статистические теории информации.

[5] Берют, Антуан; Аракелян, Артак; Петросян, Артём; Силиберто, Серджио; Дилленшнейдер, Рауль; Лутц, Эрик (март 2012 г.). «Экспериментальная проверка принципа Ландауэра, связывающего информацию и термодинамику». Природа . 483 (7388): 187–189. arXiv : 1503.06537 . Бибкод : 2012Natur.483..187B . дои : 10.1038/nature10872 . ПМИД 22398556 . S2CID 9415026 .

[6] Майкл П. Франк. Основы обобщенных обратимых вычислений. Конференция по обратимым вычислениям, 6–7 июля 2017 г., Калькутта, Индия. doi:10.1007/978-3-319-59936-6 2 Препринт доступен по адресу https://www.osti.gov/servlets/purl/1456440 (PDF).

[7] Ландауэр, Р. (июль 1961 г.). «Необратимость и тепловыделение в вычислительном процессе». Журнал исследований и разработок IBM . 5 (3): 183–191. дои : 10.1147/рд.53.0183 .

[8] Фрэнк, Майкл П.; Шукла, Карпур (1 июня 2021 г.). «Квантовые основы классических обратимых вычислений» . Энтропия . 23 (6): 701. arXiv : 2105.00065 . Бибкод : 2021Entrp..23..701F . дои : 10.3390/e23060701 . ISSN 1099-4300 . ПМЦ 8228632 . ПМИД 34206044 .

[9] Фрэнк, Майкл П. (2018). «Физические основы принципа Ландауэра» . В Кари, Яркко; Улидовский, Ирек (ред.). Обратимые вычисления . Конспекты лекций по информатике. Том. 11106. Чам: Springer International Publishing. стр. 3–33. arXiv : 1901.10327 . дои : 10.1007/978-3-319-99498-7_1 . ISBN 978-3-319-99498-7 . S2CID 52135244 .

[10] Лецерф (Ю.): Математическая логика: обратимые машины Тьюринга. Труды сессий Академии наук, 257: 2597–2600, 1963.

[11] CH Bennett, « Логическая обратимость вычислений », IBM Journal of Research and Development, vol. 17, нет. 6, стр. 525–532, 1973 г.

[12] Беннетт, Чарльз Х. (декабрь 1982 г.). «Термодинамика вычислений - обзор». Международный журнал теоретической физики . 21 (12): 905–940. Бибкод : 1982IJTP...21..905B . дои : 10.1007/BF02084158 . S2CID 17471991 .

[13] Рольф Дрекслер, Роберт Вилле. От таблиц истинности к языкам программирования: прогресс в разработке обратимых схем. Международный симпозиум по многозначной логике, 2011 г. http://www.informatik.uni-bremen.de/agra/doc/konf/11_ismvl_reversible_circuit_design_tutorial.pdf

[14] Саиди, Мехди; Марков, Игорь Л. (1 февраля 2013 г.). «Синтез и оптимизация обратимых схем — обзор». Обзоры вычислительной техники ACM . 45 (2): 1–34. arXiv : 1110.2574 . дои : 10.1145/2431211.2431220 . S2CID 6302811 .

[15] Рольф Дрекслер и Роберт Вилле. Реверсивные схемы: недавние достижения и будущие задачи новой технологии. Международный симпозиум по проектированию и испытаниям СБИС, 2012 г. http://www.informatik.uni-bremen.de/agra/doc/konf/2012_vdat_reversible_circuits_accompl_chall.pdf

[16] Коэн, Эяль; Долев, Шломи; Розенблит, Майкл (26 апреля 2016 г.). «Полностью оптическая конструкция для энергосберегающих обратимых вентилей и схем» . Природные коммуникации . 7 (1): 11424. Бибкод : 2016NatCo...711424C . дои : 10.1038/ncomms11424 . ПМЦ 4853429 . ПМИД 27113510 .

[17] Анг, Ю.С.; Ян, SA; Чжан, К.; Ма, З.С.; Анг, ЛК (2017). «Valleytronics в объединении конусов Дирака: полностью электрический фильтр долины, клапан и универсальный обратимый логический вентиль». Физический обзор B . 96 (24): 245410. arXiv : 1711.05906 . Бибкод : 2017PhRvB..96x5410A . дои : 10.1103/PhysRevB.96.245410 . S2CID 51933139 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]