Войти
Обратимые вычисления - это любая модель вычислений, в которой вычислительный процесс до некоторой степени обратим во времени. В модели вычислений, которая использует детерминированные переходы из одного состояния абстрактной машины к другой, является необходимым условием для обратимости является то, что соотношение в отображении из состояний их наследников должно быть один-к-одному. Обратимые вычисления - это форма нетрадиционных вычислений.
Из - за унитарности в квантовой механике, квантовые схемы являются обратимыми, пока они не « крах » квантовых состояний они работают на.
Есть два основных, тесно связанных типа обратимости, которые представляют особый интерес для этой цели: физическая обратимость и логическая обратимость.
Процесс называется физически обратимым, если он не приводит к увеличению физической энтропии ; он изэнтропичен. Существует стиль проектирования схем, идеально демонстрирующий это свойство, которое называется логикой восстановления заряда, адиабатическими схемами или адиабатическими вычислениями (см. Адиабатический процесс ). Хотя на практике ни один нестационарный физический процесс не может быть точно физически обратимым или изоэнтропическим, нет известного предела близости, с которой мы можем приблизиться к идеальной обратимости в системах, которые достаточно хорошо изолированы от взаимодействий с неизвестными внешними средами, когда законы физики описывающие эволюцию системы точно известны.
Мотивация для изучения технологий, направленных на реализацию обратимых вычислений является то, что они предлагают то, по прогнозам, будет единственным потенциальным способом повышения вычислительной энергоэффективности компьютеров за пределами фундаментального предела фон Нейман-Ландауэр из кТ Ln (2) энергия рассеивается в необратимая битовая операция. Хотя предел Ландауэра был в миллионы раз ниже энергопотребления компьютеров в 2000-х и в тысячи раз меньше в 2010-х, сторонники обратимых вычислений утверждают, что это можно отнести в основном к архитектурным накладным расходам, которые эффективно усиливают влияние ограничения Ландауэра на практическую работу. схемные решения, так что практическим технологиям может оказаться трудно продвинуться намного дальше нынешних уровней энергоэффективности, если не используются принципы обратимых вычислений.
Как впервые заявил Рольф Ландауэр во время работы в IBM, для того, чтобы вычислительный процесс был физически обратимым, он также должен быть логически обратимым. Принцип Ландауэра - строго обоснованное наблюдение, что незаметное стирание n бит известной информации всегда должно приводить к затратам в nkT ln (2) термодинамической энтропии. Дискретный детерминированный вычислительный процесс называется логически обратимым, если функция перехода, отображающая старые вычислительные состояния в новые, является взаимно однозначной функцией ; т.е. выходные логические состояния однозначно определяют входные логические состояния вычислительной операции.
Для вычислительных процессов, которые являются недетерминированными (в смысле вероятности или случайности), связь между старым и новым состояниями не является однозначной функцией, и требование, необходимое для получения физической обратимости, становится несколько более слабым условием, а именно, что размер данного ансамбля возможных начальных вычислительных состояний не уменьшается в среднем по мере продолжения вычислений.
Принцип Ландауэра (и, действительно, второй закон термодинамики ) также можно понимать как прямое логическое следствие лежащей в основе обратимости физики, что отражено в общей гамильтоновой формулировке механики и в унитарном операторе эволюции во времени. квантовая механика, точнее.
Таким образом, реализация обратимых вычислений сводится к изучению того, как характеризовать и контролировать физическую динамику механизмов для выполнения требуемых вычислительных операций настолько точно, что мы можем накапливать незначительную общую неопределенность в отношении полного физического состояния механизма для каждой логической операции. что выполняется. Другими словами, нам нужно будет точно отслеживать состояние активной энергии, которая участвует в выполнении вычислительных операций внутри машины, и спроектировать машину таким образом, чтобы большая часть этой энергии рекуперировалась в организованной форме, которая может повторно использоваться для последующих операций, а не рассеиваться в виде тепла.
Хотя достижение этой цели представляет собой серьезную проблему для проектирования, производства и описания сверхточных новых физических механизмов для вычислений, в настоящее время нет фундаментальных оснований полагать, что эта цель в конечном итоге не может быть достигнута, что позволит нам когда-нибудь создавать компьютеры, которые генерируют гораздо меньше, чем 1 бит физической энтропии (и рассеивают гораздо меньше, чем kT ln 2 энергии на нагрев) для каждой полезной логической операции, которую они выполняют внутри.
Сегодня в этой области существует значительный объем академической литературы. Физиками, инженерами-электриками и компьютерными учеными было разработано и проанализировано большое количество концепций обратимых устройств, логических вентилей, электронных схем, архитектур процессоров, языков программирования и прикладных алгоритмов.
В этой области исследований ожидается детальная разработка высококачественной, рентабельной, почти обратимой технологии логических устройств, которая включает в себя высокоэффективные механизмы тактирования и синхронизации или устраняет необходимость в них за счет асинхронной конструкции. Такого рода серьезный инженерный прогресс потребуется, прежде чем большая часть теоретических исследований обратимых вычислений сможет найти практическое применение, позволяя реальной компьютерной технологии преодолевать различные краткосрочные барьеры на пути к ее энергоэффективности, включая границу фон Неймана-Ландауэра. Этого можно избежать только с помощью логически обратимых вычислений из-за второго закона термодинамики.
Чтобы реализовать обратимое вычисление, оценить его стоимость и оценить его пределы, его можно формализовать в терминах схем на уровне вентилей. Упрощенная модель таких схем - это модель, в которой потребляются входы (однако, обратите внимание, что реальные логические элементы, реализованные, например, в CMOS, этого не делают). В этой структуре моделирования вентиль инвертора (НЕ) является обратимым, потому что его можно отменить. Элемент исключающее ИЛИ (ИСКЛЮЧАЮЩЕЕ ИЛИ) необратим, потому что два его входа не могут быть однозначно восстановлены из его единственного выхода. Однако обратимая версия логического элемента XOR - управляемый вентиль НЕ (CNOT) - может быть определена путем сохранения одного из входов. Вариант с тремя входами ворот CNOT называется вентилем Тоффоли. Он сохраняет два из своих входов a, b и заменяет третий c на. С, это дает функцию И, а с этим дает функцию НЕ. Таким образом, вентиль Тоффоли универсален и может реализовывать любую обратимую булеву функцию (при наличии достаточного количества инициализированных нулем вспомогательных битов). В более общем смысле, у реверсивных вентилей, которые потребляют свои входы, входов не больше, чем выходов. Реверсивная схема соединяет реверсивные ворота без разветвлений и петель. Следовательно, такие схемы содержат равное количество входных и выходных проводов, каждый из которых проходит через всю цепь. Точно так же, в машине Тьюринг модели вычислений, обратимый машин Тьюринга является одним которого функция переходов обратят, так что каждая машину состояние имеет не более одного предшественника.
Ив Лесерф предложил обратимую машину Тьюринга в статье 1963 года, но, очевидно, не зная принципа Ландауэра, не стал развивать эту тему дальше, посвятив большую часть своей карьеры этнолингвистике. В 1973 году Чарльз Х. Беннетт из IBM Research показал, что универсальная машина Тьюринга может быть сделана как логически, так и термодинамически обратимой, и, следовательно, способной в принципе выполнять сколь угодно большое количество вычислительных шагов на единицу рассеиваемой физической энергии, если ее эксплуатировать в достаточной степени. медленно. Термодинамически обратимые компьютеры могут выполнять полезные вычисления с полезной скоростью, рассеивая при этом значительно меньше kT энергии на логический шаг. В 1982 году Эдвард Фредкин и Томмазо Тоффоли предложили компьютер с бильярдным шаром, механизм, использующий классические твердые сферы для выполнения обратимых вычислений с конечной скоростью с нулевой диссипацией, но требующий идеального начального совмещения траекторий шаров, и в обзоре Беннета сравнивались эти «броуновские» и «баллистические» парадигмы обратимых вычислений. Помимо мотивации энергоэффективных вычислений, обратимые логические вентили предлагали практические усовершенствования преобразований манипулирования битами в криптографии и компьютерной графике. С 1980-х годов обратимые схемы вызывают интерес как компоненты квантовых алгоритмов, а в последнее время - в технологиях фотонных и нанокомпьютерных вычислений, где некоторые переключающие устройства не обеспечивают усиления сигнала.
Доступны обзоры обратимых схем, их конструкции и оптимизации, а также недавние исследовательские задачи.
