Обратимые вычисления

[kaipa]

Разбирая завал на столе, нашел распечатку статьи Conservative Logic. Совершенно не помню, когда ее распечатал "на потом". Начал читать, стало интересно. Основная мысль -- создание схемотехники, "работающей" не по традиционной логической схеме (в дискретной математике это называется СФЭ -- схема функциональных элементов), а по совсем другой, основное свойство которой сохранение (отсюда conservative) энергии, которая в традиционных системах совершенно расточительно рассеивается. Необходимым образом в таких схемах вытекает обратимость вычислительных и логических процессов. Статья старая, 1982г. Погуглил, нашелся вольный перевод этой статьи год назад на Хабре, веб-сайт критиков консервативной партии США и... почти все. Меня это очень озадачило, так как тема казалась важной. Я предположил, что само название "Консервативная логика" скорее всего не прижилось, и оказался прав. В современном мире это направление называется обратимыми вычислениями, а соответствующая схемотехника -- адибатической логикой.

На самом деле тут проблема очень глубокая и принципиальная, уходящая в самые основы современного понимания устройства мира. Из связи термодинамической и информационной энтропии следует, что любые манипуляции с информацией приводят к рассеиванию энергии. Есть даже теоретическая оценка минимума энергии, которая равна E ≥ kT ln2 на один бит. Это было известно все довольно давно, уже лет 50, но только сейчас, когда вычислительные мощности впечатляюще выросли, начинает по-настоящему припекать. Так, 100-петафлопсные суперкомьютеры (кажется, такие уже есть), излучают только "теоретического" тепла порядка 1 мегаватт, а практически гораздо больше. А это уже сегодняшний день. Завтра суперкомьютеры могут быть в 10-100-1000 раз мощнее, и соответственно вырастет количество теряемой энергии. Обратимые вычисления тут решают теоретически сразу две вещи. Во-первых, энергия не рассеивается, а используется. Как именно это может быть достигнуто, можно прочитать в вышеупомянутой статье. А во-вторых, появляется возможность "делать" схемы еще более "мелкими". Сейчас мешает термодинамический шум.

В настоящее время исследования в этой области проводятся в MIT и University of Florida. Уже есть прототипы чипов на адиабатической логике, а список текущих проектов показывает, что разрабатывается все, от физики, до системы программирования и теории сложности.

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

Comments

[fat-crocodile.livejournal.com]

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

Статью посмотрю, спасибо за наводку.

[ushastyi.livejournal.com]

Мне кажется, что важность экономии энергии стали осознавать не так давно, когда появились датацентры с десятками и сотнями тысяч компьютеров. Гугл, например, строит свои датацентры рядом с крупными электростанциями. С Яндексом тоже понятно. Но основной тренд -- это использование уже существующих технологий более эффективно. Гугл и Фейсбук собирает компьютеры сами, и даже появилось целое движение Open Source Hardware (http://en.wikipedia.org/wiki/Open-source_hardware), одной из целью которого является разработка более эффективных схем и компьютеров. Интерес к программированию FPGA оттуда же.

Консервативная логика и обратимые вычисления, или квантовые компьютеры, если они появятся, -- это радикальное изменение. Но разговоры о них идут давно, а прорыва пока не видно. Хотя на сайте UF пишут, что прототипы устройств на адиабатической логике уже есть, небольшие кубитовые процессоры тоже вроде как существуют (http://www.dwavesys.com/en/products-services.html). Параллельно разрабатываются новые принципы в рамках традиционной схемотехники, например туннельный транзистор (http://www.gazeta.ru/science/2012/02/03_a_3985461.shtml) или спиновый транзистор (http://elementy.ru/news/430624).

[evil-gryphon.livejournal.com]

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

"Основателем" обычно называется R. Landauer который написал статью "Irreversibility and heat generation in the computing process" в журнале "IBM Journal of Research and Development".

Меня (в каком-то споре) хватило на то чтобы найти этот IBM Journal и оригинальную статью Лаундера 1961 года, прочитать её внимательно и, (это было открытием) оказывается, избавление от нереверсивности в ходе вычислений создаёт эквивалентную нереверсивность на входе компьютера (то есть, не даёт абсолютно ничего для уменьшения мощности расходуемой на вычисления!!)

[ushastyi.livejournal.com]

Статью Лаундера я, к сожалнию, не читал. Знаю только то, что описано выше. А ее стоит почитать? Мне кажется, что более современные статьи должны быть более адекватны.

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

[evil-gryphon.livejournal.com]

оригинальная статья доступна например по ссылке:
http://www.cs.duke.edu/~reif/courses/complectures/AltModelsComp/Landauer/Landauer.irreversibility.pdf

(возможно стоит прочитать чтобы понять насколько ясным было мышление инженеров в 61-м году).
основные выводы:

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

[evil-gryphon.livejournal.com]

оригинальная статья доступна например по ссылке:
(сообщение со ссылкой отмечается как спам, но PDF-документ можно найти набрав в гугле запрос:
landauer Irreversibility and heat generation in the computing process pdf )

(возможно стоит прочитать чтобы понять насколько ясным было мышление инженеров в 61-м году).
основные выводы:

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

[evil-gryphon.livejournal.com]

Интересно что в статье на Хабре есть ссылка на PDF Ландауэра (R. Landauer я неправильно напечатал его фамилию) но эту статью похоже никто давно не читает.

[vincentfischer.livejournal.com]

есть сборник статей на русском, что-то типа "Квантовые вычисления", там переведено несколько основных статей на эту тему (перевод не очень, кстати), всё очень доступно, про обратимость в том числе. синяя книжка примерно на 200 страниц.

[ushastyi.livejournal.com]

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

[vincentfischer.livejournal.com]

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

(если бы вы расшарили личные сообщения, мы бы могли познакомиться, если вы не против, кстати)

[ushastyi.livejournal.com]

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

[vincentfischer.livejournal.com]

а вот вам книжка в ответ :)

http://www.booksgid.com/other/22900-kvantovyjj-kompjuter-i-kvantovye.html

если не скачается тут, у меня есть своя пиратская в электронном виде

[ushastyi.livejournal.com]

Судя по именам, действительно, сборник классических статей. Спасибо.

[ushastyi.livejournal.com]

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

[vincentfischer.livejournal.com]

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

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

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

[ushastyi.livejournal.com]

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

Квантовую аналогию я понял. Но Вы делаете как минимум два неявных предположения, которые надо как-то обосновать:
1) коробка -- замкнутая система. Что в случае квантовых преобразований обеспечить непросто
2) квантовые преобразования обратимы во времени. Что, насколько я понимаю, совсем не так. В силу вероятностной природы всех преобразований.

[vincentfischer.livejournal.com]

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

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

> квантовые преобразования обратимы во времени. Что, насколько я понимаю, совсем не так.
так-так, пока вы не сделали измерение .