Почему не используются реверсивные ворота?

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

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

Я ни в коем случае не эксперт по этой теме, но просто из случайного чтения Википедии:

он основан на движении сферических бильярдных шаров в среде без трения, выполненной из буферов, от которых шары отскакивают идеально

... это звучит очень реалистично.

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

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

Теоретический предел, на который претендует Reversible Computing, заключается в том, что стирание 1 бита информации генерирует по крайней мере энергии в тепле. Для компьютера, работающего со скоростью с транзисторами, каждый составляющий биты исчезают со скоростью , что соответствует выработки тепла. Это составляет лишь небольшую часть ( ) от энергопотребления компьютера.$kT\ln 2$10 9$60\,{}^\circ\mathrm{C}$$10^9$$5\,\mathrm{GHz}$ 1 /$16\,\mathrm{mW}$$1/10000$

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

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

Я знаю, что исследовательская группа Тома Найта в MIT изготовила небольшой адиабатический процессор в конце 1990-х годов. Разработанное ими семейство практической логики называется разделенной логикой восстановления заряда и может быть реализовано с использованием стандартных (CMOS) технологий изготовления. Я полагаю, что работа была продолжена Майклом П. Фрэнком из Университета штата Флорида. Примером работы в группе Тома Найта является следующая магистерская работа (которая имеет довольно приличный раздел о смежных работах в начале 1990-х годов.) Вьери, CJ: Маятник: обратимая компьютерная архитектура , магистерская работа, кафедра MIT EECS, 1995.

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

Если я правильно помню мою термодинамику, вы можете сделать энергию обратимого вычисления сколь угодно малой, но минимальное действие (время-энергия) должно быть небольшой константой.

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

Закон Мура стал чем-то вроде самоисполняющегося пророчества; Как видно из графика выпуска Tick Tock , производители микросхем считают выполнение закона Мура сложной задачей. Из-за необходимости выполнять закон Мура, мы стали все более искусными в уменьшении размера чипов, продвигая литографию (и часто используя читы, такие как мультипаттерны).

Какое все это имеет отношение к реверсивным воротам? Поскольку литейные заводы стремятся выпустить новые и меньшие размеры транзисторов, компании, которые хотят печатать новые микросхемы, видят легкий путь к увеличению скорости, просто добавляя больше кеша и переработав свои традиционные конструкции, чтобы лучше использовать этот кеш.

Убийца лучшего - это не технологические проблемы; это успех достаточно хорошо .

Полезные вычислительные устройства требуют обратной связи, что позволяет одному элементу схемы выполнять по существу неограниченное количество последовательных вычислений. Используемые цепи обратной связи должны содержать секции, чье общее количество входов (считая как те, которые возвращаются с выходов, так и нет) превышает количество выходов, которые возвращаются на вход (единственный способ, которым количество входов не будет ' Превышение числа выходов с обратной связью было бы, если бы цепи не реагировали каким-либо образом на внешние раздражители). Поскольку совершенно обратимо-логические функции не могут иметь больше входов, чем выходов, невозможно построить из них какую-либо структуру обратной связи, необходимую для многократного выполнения любых нетривиальных вычислительных задач., Обратите внимание, что с технологией CMOS, используемой в современных компьютерах, обратная связь необходима для обеспечения того, чтобы результаты, представленные вычислениями в разных частях схемы, были доступны одновременно другим частям, поскольку если бы они не были относительной синхронизацией, с которой поступают сигналы, составляют «информацию», которая не может быть полностью передана вниз по течению; другие технологии могут позволить множеству вентилей распространять сигналы с одинаковой скоростью, сохраняя при этом обратимость, но я не знаю практической технологии для этого.

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

Если разрешено иметь выходы, которые игнорируются, если при надлежащих входных условиях они никогда не будут повышаться, тогда может быть возможно разработать систему, которая теоретически получит выгоду от обратимой логики. Например, если у кого-то был алгоритм, который работал на 256-слововом блоке оперативной памяти, а другой хотел использовать «процессор с обратимой логикой», который выполнял 1 000 000 операций в секунду, и каждая операция обновляла либо регистр, счетчик программ, либо один Слово RAM, можно использовать «обратимый процессор», который бы:

• выполнил кучу инструкций и, на каждой, отправил все, что было перезаписано в буфер LIFO
• после выполнения нескольких инструкций скопируйте ОЗУ в изначально пустой буфер пересылки
• используя значения в LIFO, запустите все вычисления в обратном порядке
• перезаписать содержимое основного ОЗУ буфером пересылки, который будет удален в процессе.

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

Однако для того, чтобы эта способность перешла в какую-либо экономию энергии, необходимо иметь LIFO, который будет накапливать энергию при вводе информации и с пользой возвращать эту энергию при считывании. Кроме того, LIFO должен быть достаточно большим, чтобы хранить данные о состоянии для достаточного количества шагов, чтобы любая энергия, затрачиваемая на его использование, была меньше, чем количество энергии, которое оно экономно использовало. Учитывая, что количество энергии, потерянной при хранении и извлечении N байтов из любого практического FIFO, вряд ли будет равно O (1), неясно, что увеличение N значительно уменьшит потребление энергии.

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

Другой основной момент заключается в том, что каждый раз, когда рассеяние энергии на микросхеме уменьшается, это, по сути, переводит систему затворов в «более обратимое состояние», а рассеяние микросхем с более низкой энергией уже давно является высоким приоритетом в мобильных вычислениях (что представляет собой своего рода изменение отраслевой парадигмы). В течение десятилетий прирост производительности чипов (по аналогии с законом Мура) был вызван тем, что он был несколько «ослаблен» или даже «неаккуратен» из-за рассеяния энергии, но это достигло точки снижения отдачи несколько лет назад. Intel, ведущий мировой производитель микросхем, пытается внедрить чипы с более низким энергопотреблением, чтобы конкурировать с Arm, который имеет преимущество, никогда не создавая ничего, кроме.

Возможно, недавно были проведены прорывные исследования с использованием сверхпроводящих технологий (июнь 2014 г.), и есть другие активные исследовательские проекты в этой области.

См., Например, Двусторонние логические элементы с использованием адиабатических сверхпроводящих устройств / Такеучи, Яманаси, Йошикава, Природа:

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

Ворота Фредкина реалистичны и многие были реализованы. Есть целые платы FPGA, строго использующие реверсивные логические вентили, которые реализованы с использованием Fredkin и Toffoli gate в качестве их LU.

Есть несколько проблем, влияющих на их широкое использование в компьютерной архитектуре. У ворот Фредкина есть несколько «рекламируемых» преимуществ, которые не обязательно работают так, как ожидается в реальных цепях. Экономия энергии реверсивных логических вентилей обусловлена ​​главным образом тем, что они не требуют создания энтропии при выполнении операции. Как заявил Том ван дер Занден, это главная причина, по которой обратимая логика может быть гораздо более эффективной. Почему это не так в реальных цепях:

1. В настоящее время транзисторная технология - это больше, что ограничивает скорость компьютера и энергопотребление, и, к сожалению, требуется больше транзисторов, чтобы сделать затвор Фредкина в отличие от традиционных затворов nand или nor. Это означает, что ворота Фредкина тратят больше энергии из-за утечки транзистора и требуют больше места на кремнии (что означает более дорогой). Одного этого достаточно, чтобы оправдать использование nand / or over fredkin gates
2. Поскольку основной формой потери мощности является транзистор, а не создание энтропии из-за фактических вычислений, вам все равно нужно провести линии питания и заземления для входа Фредкина, чтобы компенсировать эту потерю мощности. Эти большие шины представляют собой веерные шины, которые также занимают много места на кремнии. Поскольку в затворе Фредкина больше транзисторов, это приводит к большему разветвлению и, таким образом, к потере пространства на кремнии.
3. Хотя у нас есть обратимые ворота Фредкина, они построены из необратимых устройств (транзисторов). Это означает, что некоторые из приростов энергии не реализуются с помощью современной технологии затвора (за пределами квантовых цепей).
4. Размер и скорость связаны с кремнием, чем ближе друг к другу, тем быстрее вы можете их сделать. Поскольку ворота Фредкина используют больше транзисторов и имеют больше соединений для питания и т. Д., Они имеют тенденцию быть значительно медленнее.
5. Преимущества энергопотребления и скорости реализуются только тогда, когда биты успешно используются повторно. Большинство наших алгоритмов ужасно неконсервативны. Вы можете убедиться в этом, исследуя реализацию полного сумматора или сдвигового регистра, используя ворота Фредкина. Поскольку обратимая логика не допускает логического разветвления и разветвления, это приводит к большому количеству битовых вычислений, которые не в конечном итоге используются для выполнения полезной операции. Нечто такое, как сложение двух 8-битных чисел, даст 9-битную или полезную информацию (8-битный результат, 1 бит переноса), но потребует входную шину с множеством 1 и 0 констант и создаст много битов вывода ненужных данных. Поскольку у вас более широкая шина, это приводит к еще большему распространению цепи на кремнии.
6. Кроме того, ненужные биты должны быть сброшены процессором, что в любом случае приведет к потере энергии, поскольку они никогда не используются.

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

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