7 February 2011

Консервативная логика

System Programming
Вооруженные жидким азотом оверклокеры неоднократно показывали, что современные чипы могут стабильно работать на частотах в разы выше номинальных, обеспечивая соответствующий рост производительности. Тем не менее, прогресс в области «гонки гигагерц» остановился давно и надежно. Первый «Pentium 4» с частотой больше 3 ГГц появился в далеком 2002 году, почти 10 лет назад. За прошедшие годы нормы техпроцессов уменьшились со 180 до 32 нм, но даже это не позволило существенно поднять штатные рабочие частоты. Все упирается в огромное тепловыделение элементов цифровой логики.

В основе «проблемы тепловыделения» лежит глубокая связь между информационной и термодинамической энтропией, а также второе начало термодинамики, запрещающее уменьшение общей энтропии замкнутой системы. Любое вычисление, уменьшающее энтропию информационную, обязано приводить к увеличению энтропии термодинамической, то есть к выделению тепла. Рольф Ландауэр в 1961 году показал [pdf], что уничтожение одного бита информации должно приводить к выделению не менее k∙T∙ln 2 джоулей энергии, где k – постоянная Больцмана и T – температура системы. Само по себе эта энергия невелика: для T=300K она составляет всего 0.017 эВ на бит, но в пересчете на процессор в целом суммарная энергия вырастает уже до величин порядка одного Джоуля за каждую секунду работы, то есть порядка одного Ватта [Компьютерра №538]. На практике этот теоретический минимум умножается на ненулевое сопротивление и прочие неидеальности реальных полупроводников. В результате мы получаем процессоры, которые по тепловыделению обгоняют утюги.


Уничтожение информации в современных процессорах происходят постоянно и на самом низком уровне, в вентилях «И-НЕ», являющихся «кирпичиками» любой современной цифровой схемы. Принимая на вход два бита, вентиль выдает результат размером всего один бит, по которому, разумеется, нельзя восстановить значения исходных аргументов. Более строго, каждое вычисление вентилем «И-НЕ» уменьшает информационную энтропию на 1.189 бита, и, соответственно, рассеивает не менее ~0.02 эВ тепла. С непопулярными сегодня «ИЛИ-НЕ» ситуация аналогична.

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

Уже более 30 лет известен способ организации вычислений без уничтожения информации, который не попадает под принцип Ландауэра и позволяет создавать теоретически энергоэффективные процессоры. Такой способ называется консервативной, или «сохраняющей», логикой. К сожалению, для него так и не удалось создать компактную физическую реализацию в кремнии, известен только способ реализации на МОП-транзисторах с плохо миниатюризируемыми индуктивностями. С другой стороны, этот подход является естественным для большинства типов квантовых компьютеров, в том числе для оптических (модель Бениофа и др.)

За эти годы выяснилось, что консервативная логика оказалась полезной математической абстракцией и без реализации «в железе»: на ее базе создаются блочные клеточные автоматы, которые очень удобно использовать при решении задач «на ограниченные ресурсы». Этот раздел математики сейчас очень активно развивается, и, возможно, через десяток лет блочные клеточные автоматы будут даже более известны среди программистов, чем обычные.

«Взмахом крыла бабочки», приведшим к появлению этой статьи, стал поднятый товарищем Плаховым вопрос «как это по-русски?», ответ на который не знает даже Яндекс. Кроме упомянутой выше статьи в «Компьютерре» за 2004 год на русском языке вообще нет какой-либо информации о консервативной логике – что тем более обидно, поскольку ее теоретические основы заложили великие советские физики Ландау и Лифшиц ровно 50 лет назад, в 1961 году. Чтобы хоть немного ликвидировать этот пробел, с одной стороны, и «не пороть отсебятину», с другой, я предлагаю вашему вниманию реферат (перевод основных тезисов) основополагающей статьи по консервативной логике Эдуарда Фредкина и Томассо Тоффоли, опубликованной в журнале «Теоретическая физика» №21 за 1982 год. (Fredkin, Edward and Toffoli, Tomasso, «Conservative Logic», Int. J. Theor. Phys. 21 (1982), 219–253; pdf). В этой статье раскрываются все основные моменты, касающиеся физики, логики и схемотехники систем на базе консервативной логики.

Консервативная логика


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

1. Физические основы



(Нумерация разделов реферата не совпадает с нумерацией частей статьи — прим. пер.)

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

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

На микроуровне наш мир обладает различными фундаментальными однородностями и симметриями, многие из которых приводят к появлению «законов сохранения» на макроуровне. Так, однородность времени обеспечивает выполнение закона сохранения энергии, однородность пространства – закона сохранения импульса, а изотропия пространства (симметрия направлений) приводит к закону сохранения момента вращения.

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

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

Прим. пер.: статья рассчитана на физиков, поэтому авторы не приводят иллюстрации к очевидным для физиков вещам. В последнем предложении речь вот о чем: например, конденсатор ячейки памяти может быть в двух логических состояниях — «заряжен» или «разряжен» (хотя, разумеется, «физический» заряд конденсатора есть величина практически непрерывная, а никак не булева). Устойчивость этих логических состояний обеспечивается специальной электронной схемой регенерации, подзаряжающей заряженные конденсаторы и разряжающей разряженные. При этом разница в энергии между «заряженным» и «разряженным» состояниями должна быть огромна по сравнению с уровнем тепловых шумов, иначе возможна порча хранимых значений.


Хотя фактически эти состояния могут быть электрическими, оптическими и т.п., здесь и далее мы будет называть их «механическими», чтобы отличать от состояний термодинамических. Термодинамические состояния – это степени свободы отдельных атомов и молекул, составляющих вещество. В одном грамме любого вещества имеется огромное, порядка 1023 (число Авогадро), количество таких степеней свободы, и учитывать их можно только статистическими методами и законами.

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

Соответственно, возможны два принципиально разных подхода к физической организации вычислений.

При «консервативном» или «сохраняющем» подходе для хранения информации подбираются такие механические состояния, для которых невозможен обмен энтропией с термодинамическими состояниями. В такой системе должны быть запрещены любые операции, уменьшающие информационную энтропию, в частности, операции уничтожения информации. Поэтому все операции должны быть обратимыми. Ландау и Лившиц показали, что в такой системе должны существовать некие инвариантные аддитивные величины, например, заряды или моменты, «охраняемые» законом сохранения – только тогда переход «зарядов» в «температуру» и обратно будет невозможен. Суммарный уровень этих величин, имеющихся в замкнутой системе, будет величиной постоянной и не зависящей от происходящих в системе процессов.

В отличие от консервативного, при обычном «фон-Неймановском» подходе вычисления изначально необратимы. Для удовлетворения второго начала термодинамики должен существовать путь обмена энтропией и энергией между механическими и термодинамическими степенями свободы. Такой путь должен быть односторонним (то есть необратимым), чтобы тепловые флуктуации не могли разрушить хранящуюся в механических состояниях информацию. Но, поскольку на микроуровне все процессы обратимы, то добиться одностороннего перетекания энтропии можно, только если разность энергий между механическими состояниями будет намного порядков больше, чем между термодинамическими. В современной вычислительной технике (на 1982 г. – прим. пер.) разница составляет от 8 до 12 порядков.

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

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


Вся сегодняшняя вычислительная техника построена по второму, «необратимому» пути. Необратимость специально заложена в базовых логических схемах, в p-n переходах транзисторов, и, даже если вычисляемый высокоуровневый алгоритм формально обратим – при исполнении на современных процессорах как минимум часть его отдельных шагов необратима на самом низком уровне. Необратимость также означает большое тепловыделение, которое ограничивает достижимую производительность.

2. Базовые элементы консервативной логики


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

Прим. пер. : в обычной схемотехнике выход одного логического элемента может подключаться ко входам нескольких других элементов («разветвление»). В консервативной схемотехнике один выход должен попадать строго на один вход следующего элемента; для разветвления необходим специальный логический элемент (см.ниже).


Консервативная логика базируется на двух элементах – повторителе и вентиле Фредкина.

Повторитель (unit wire; буквально «элементарный проводник») просто повторяет на выходе сигнал, поданный на его вход, с задержкой в 1 такт. Именно скорость работы повторителей и определяет тактовую частоту схемы. Формально, функция повторителя выражается как:
yt= xt-1

Условное обозначение:



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

Обратным к повторителю элементом является такой же повторитель, но направленный в обратную сторону.

Значения на выходах повторителей на определенном такте полностью описывают внутреннее состояние цифровой схемы консервативной логики, то есть выходы повторителей являются переменными состояния такой схемы. Сумма значений на выходах повторителей будет той самой аддитивной сохраняемой величиной («суммарным зарядом»), и, для замкнутой системы – величиной постоянной. Общее количество повторителей в схеме можно расценивать как количество степеней свободы этой схемы.

Повторители отдаленно подобны, но далеко не эквивалентны, элементам задержки в обычной «фон-Неймановской» схемотехнике.

Вентиль Фредкина – это устройство с тремя входами u, x1, x2 и тремя выходами v, y1, y2, реализующее функцию управляемого «перехлеста» («кросса») двух линий данных (см. рис). Выход v всегда совпадает со входом u. При u=1 выходы y1,y2 равны входам x1,x2; при u=0 y1=x2 и y2=x1 (см. табл.)

Таблица истинности вентиля Фредкина:
(u, x1, x2) => (v, y1,y2)
0,0,0 => 0,0,0
0,0,1 => 0,1,0
0,1,0 => 0,0,1
0,1,1 => 0,1,1
1,0,0 => 1,0,0
1,0,1 => 1,0,1
1,1,0 => 1,1,0
1,1,1 => 1,1,1

Вентиль Фредкина обратен сам себе.

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

3. Консервативная схемотехника


В консервативной логике можно реализовать машину Тьюринга (Беннетт, 1973) и универсальный клеточный автомат (Тоффоли, 1980). Таким образом, консервативная логика позволяет решать любые вычислимые по Черчу задачи.

Процесс реализации произвольных функций в консервативной логике очень похож на такой же процесс в логике традиционной.

Так же, как и в традиционной схемотехнике, при реализации некоторых функции используются константы – источники постоянных значений 0 или 1. С другой стороны, в результате вычислений могут получиться не только требуемые результаты, но и побочные, не нужные для дальнейшего использования в конкретном алгоритме. Полученные побочные результаты называют «мусором» (garbage) или «стоками» (sink). Так как в консервативной логике сигналы не появляются «из ниоткуда» и не исчезают «в никуда», то просто отбросить линии с «лишними» результатами нельзя, их нужно неким особым образом утилизировать (рассеять в пространстве).

На рисунке показано условное обозначение для блока вычисления некой функции φ:



Вот так устроен блок "И":


(обратите внимание, что в качестве одного из стоков выступает копия аргумента)

На следующем рисунке показаны схемы реализации логических функций «ИЛИ» (a), «НЕ» (b) и разветвителя сигнала 2а-а . Последние два различаются только логической ролью выводов.



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



Далее приведена более сложная схема: демультиплексор, отправляющий сигнал Х по двоичному адресу A0, A1 на один из четырех выходов Y0 – Y3:



В консервативной логике можно реализовать любую схему из «обычной» логики. Например, на следующих трех рисунках показана реализация однобитного последовательного сумматора: первая в обычной логике (в старых обозначениях), а вторая и третья – в консервативной. При этом вторая схема собрана путем простой подстановки замен в первую, а третья создана «с нуля». На схемах видна разница между повторителями и элементами задержки: в консервативных схемах синхронизация сигналов производится явно.





4. Проблема стоков



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

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

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



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

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



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



Вычисленные значения исходной функции можно «достать», если «врезать» в схему «шпионские разветвители»:



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

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

5. Модель бильярдных шаров


В этой части представлена абстрактная физическая модель, в которой реализуема консервативная логика.

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



Логической единицей считается наличие шара, а нулем – его отсутствие.

Произвольную точку сетки можно объявить «вентилем взаимодействия», если в ней перекрестчиваются траектории двух шаров. Направление выхода этих шаров зависит от наличия обоих:



На плоскости могут быть установлены неподвижные стенки, или зеркала. Используя зеркала, можно поворачивать (а), сдвигать (b), задерживать , и безопасно пересекать траектории (d) шаров. Последний элемент (d) называется «нетривиальным кроссовером» и позволяет шарам «как бы проходить друг через друга».



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




Наконец, из простых свитчей и нетривиального кроссовера (обозначен «мостиком») можно сконструировать вентиль Фредкина (поворачивающие зеркала и задержки не показаны для ясности):



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

6. «Сложные» вопросы о консервативной логике


1. Возможны ли произвольные вычисления в консервативной логике? Да, возможны, консервативная логика полна по Тьюрингу.

2. Существуют ли физические эффекты, на которых можно реализовать консервативную логику? Да, ее можно реализовать на базе электронных элементов (дискретные L/R/C элементы плюс МОП-транзисторы) (на практике к 2011 году все остается только на бумаге и в лабораториях – прим. пер.)

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

4. Наконец, вопрос об устойчивости системы к малым шумам пока остается без ответа.

Вместо заключения (от переводчика)


Сам факт того, что управляемо перемешивая проводки в пучке или кабеле между входом и выходом и не используя никаких других элементов, кроме «перехлестывателей» и повторителей, можно получить на выходе результат вычисления любой функции от входа — далеко не очевиден. Лежащая в основе вычислительная логика необычна, но в отличие от других полных по Тьюрингу математических абстракций, таких как алгоритмы Маркова, выглядит очень «технологичной», готовой к использованию в реальных процессорах. Вполне возможно, квантовые компьютеры будут работать на чем-то похожем, с поправкой на чисто квантовые «трюки». Если совместить консервативную квантовую логику еще и со сверхпроводящими межсоединениями, получится построить действительно практически не поглощающий энергию компьютер. Чтож, будущее покажет.
Tags:консервативная логикаквантовый компьютеробратимые вычисленияreversible computing
Hubs: System Programming
+108
18.2k 160
Comments 40