Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Обратимость [ править ]

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

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

Вероятно , самая большая мотивация для изучения технологий , направленных на реальное осуществление обратимого вычислений является то , что они предлагают то , по прогнозам, будет единственным потенциальным способом повышения вычислительной энергоэффективности компьютеров за пределами фундаментального предела фон Неймана-Ландауэра [2] из кТ ЛУ (2) энергия, рассеиваемая при необратимой битовой операции . Хотя предел Ландауэра был в миллионы раз ниже энергопотребления компьютеров в 2000-х и в тысячи раз меньше в 2010-х [3]Сторонники обратимых вычислений утверждают, что это можно отнести в основном к архитектурным накладным расходам, которые эффективно усиливают влияние предела Ландауэра в практических схемах, так что для практических технологий может оказаться трудным продвинуться далеко за пределы нынешних уровней энергоэффективности, если принципы обратимых вычислений не используются. [4]

Отношение к термодинамике [ править ]

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

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

Физическая обратимость [ править ]

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

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

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

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

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

Логическая обратимость [ править ]

Чтобы реализовать обратимое вычисление, оценить его стоимость и оценить его пределы, его можно формализовать в терминах схем на уровне вентилей. Упрощенная модель таких схем - это модель, в которой потребляются входы (однако, обратите внимание, что реальные логические элементы, реализованные, например, в CMOS, этого не делают). В этой структуре моделирования вентиль инвертора (НЕ) является обратимым, потому что его можно отменить . Элемент исключающее ИЛИ (ИСКЛЮЧАЮЩЕЕ ИЛИ) необратим, потому что два его входа не могут быть однозначно восстановлены из его единственного выхода. Однако обратимая версия логического элемента XOR - управляемый вентиль НЕ (CNOT) - может быть определена путем сохранения одного из входов. Вариант с тремя входами ворот CNOT называется вентилем Тоффоли.. Он сохраняет два из своих входов a, b и заменяет третий c на . С , это дает функцию И, а с этим дает функцию НЕ. Таким образом, вентиль Тоффоли универсален и может реализовывать любую обратимую булеву функцию (при наличии достаточного количества инициализированных нулем вспомогательных битов). В более общем смысле, у реверсивных вентилей, которые потребляют свои входы, входов не больше, чем выходов. Реверсивная схема соединяет реверсивные ворота без разветвлений и петель. Следовательно, такие схемы содержат равное количество входных и выходных проводов, каждый из которых проходит через всю цепь. Точно так же в машине ТьюрингаВ модели вычислений обратимая машина Тьюринга - это машина, переходная функция которой обратима, так что каждое состояние машины имеет не более одного предшественника.

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

Доступны обзоры обратимых схем, их конструкции и оптимизации, а также недавние исследовательские задачи. [9] [10] [11] [12] [13]

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ "Группа обратимых и квантовых вычислений (Revcomp)" .
  2. ^ Дж. Фон Нейман, Теория самовоспроизводящихся автоматов , Univ. Иллинойс Пресс, 1966.
  3. ^ Берут, Antoine; Аракелян, Артак; Петросян, Артем; Чилиберто, Серджио; Дилленшнайдер, Рауль; Лутц, Эрик (март 2012 г.). «Экспериментальная проверка принципа Ландауэра, связывающего информацию и термодинамику». Природа . 483 (7388): 187–189. Bibcode : 2012Natur.483..187B . DOI : 10,1038 / природа10872 . PMID 22398556 . 
  4. ^ Майкл П. Франк, «Основы обобщенных обратимых вычислений», будет опубликован на 9-й конференции по обратимым вычислениям, 6-7 июля 2017 г., Калькутта, Индия. Препринт доступен по адресу https://cfwebprod.sandia.gov/cfdocs/CompResearch/docs/grc-rc17-preprint2.pdf .
  5. ^ Ландауэр, Р. (июль 1961 г.). «Необратимость и тепловыделение в вычислительном процессе». Журнал исследований и разработок IBM . 5 (3): 183–191. DOI : 10.1147 / rd.53.0183 .
  6. ^ Лесерф (У.): Logique Mathematique: Машины Тьюринга де реверсивные дни . Comptes rendus des séances de l'académie des Sciences, 257: 2597-2600, 1963.
  7. ^ CH Bennett, " Логическая обратимость вычислений ", IBM Journal of Research and Development, vol. 17, нет. 6. С. 525-532, 1973.
  8. ↑ Беннет, Чарльз Х. (декабрь 1982 г.). «Термодинамика вычислений - обзор». Международный журнал теоретической физики . 21 (12): 905–940. Bibcode : 1982IJTP ... 21..905B . DOI : 10.1007 / BF02084158 .
  9. ^ Рольф Дрекслер, Роберт Вилле. От таблиц истинности к языкам программирования: прогресс в разработке обратимых схем. Международный симпозиум по многозначной логике, 2011 г. http://www.informatik.uni-bremen.de/agra/doc/konf/11_ismvl_reversible_circuit_design_tutorial.pdf
  10. ^ Саиди, Мехди; Марков, Игорь Леонидович (1 февраля 2013 г.). «Синтез и оптимизация обратимых схем - обзор». ACM Computing Surveys . 45 (2): 1–34. arXiv : 1110,2574 . DOI : 10.1145 / 2431211.2431220 .
  11. ^ Рольф Дрекслер и Роберт Вилле. Обратимые схемы: последние достижения и будущие задачи для появляющейся технологии. Международный симпозиум по проектированию и тестированию СБИС, 2012 г. http://www.informatik.uni-bremen.de/agra/doc/konf/2012_vdat_reversible_circuits_accompl_chall.pdf
  12. ^ Коэн, Эяль; Долев, Шломи; Розенблит, Майкл (26 апреля 2016 г.). «Полностью оптическая конструкция для реверсивных вентилей и схем с сохранением энергии» . Nature Communications . 7 (1): 11424. Bibcode : 2016NatCo ... 711424C . DOI : 10.1038 / ncomms11424 . PMC 4853429 . PMID 27113510 .  
  13. ^ Ang, YS; Ян, С.А.; Zhang, C .; Ma, ZS; Анг, LK (2017). «Valleytronics в слиянии конусов Дирака: долинный фильтр с электрическим управлением, клапан и универсальный реверсивный логический вентиль». Physical Review B . 96 (24): 245410. arXiv : 1711.05906 . Bibcode : 2017PhRvB..96x5410A . DOI : 10.1103 / PhysRevB.96.245410 .

Дальнейшее чтение [ править ]

  • Деннинг, Питер; Льюис, Тед (2017). «Компьютеры, которые могут работать в обратном направлении». Американский ученый . 105 (5): 270. DOI : 10,1511 / 2017.105.5.270 .
  • Ланге, Клаус-Йорн; Маккензи, Пьер; Тэпп, Ален (апрель 2000 г.). «Обратимое пространство равно детерминированному пространству». Журнал компьютерных и системных наук . 60 (2): 354–367. DOI : 10.1006 / jcss.1999.1672 .
  • Перумалла К.С. (2014), Введение в обратимые вычисления , CRC Press .
  • Витани, Пол (2005). «Время, пространство и энергия в обратимых вычислениях». Труды 2-й конференции по компьютерным границам - CF '05 . п. 435. DOI : 10,1145 / 1062261,1062335 . ISBN 1595930191.

Внешние ссылки [ править ]

  • Вводная статья об обратимых вычислениях
  • Первый международный семинар по обратимым вычислениям
  • Последние публикации Майкла П. Франка
  • Резервная копия Интернет-архива "Вики сообщества обратимых вычислений", которую администрирует Фрэнк
  • Недавние семинары по обратимым вычислениям
  • Набор инструментов с открытым исходным кодом для проектирования обратимых схем