The Significance of Universality in Rule 110

http://www.wolframscience.com/nksonline/page-690-text


Practical computers and computer languages have traditionally been the only common examples of universality that we ever encounter. And from the fact that these kinds of systems tend to be fairly complicated in their construction, the general intuition has developed that any system that manages to be universal must somehow also be based on quite complicated underlying rules.

But the result of the previous section shows in a rather spectacular way that this is not the case. It would have been one thing if we had found an example of a cellular automaton with say four or five colors that turned out to be universal. But what in fact we have seen is that a cellular automaton with one of the very simplest possible 256 rules manages to be universal.

So what are the implications of this result? Most important is that it suggests that universality is an immensely more common phenomenon than one might otherwise have thought. For if one knew only about practical computers and about systems like the universal cellular automaton discussed early in this chapter, then one would probably assume that universality would rarely if ever be seen outside of systems that were specifically constructed to exhibit it.

But knowing that a system like rule 110 is universal, the whole picture changes, and now it seems likely that instead universality should actually be seen in a very wide range of systems, including many with rather simple rules.

A couple of sections ago we discussed the fact that as soon as one has a system that is universal, adding further complication to its rules cannot have any fundamental effect. For by virtue of its universality the system can always ultimately just emulate the behavior that would be obtained with any more complicated set of rules.

So what this means is that if one looks at a sequence of systems with progressively more complicated rules, one should expect that the overall behavior they produce will become more complex only until the threshold of universality is reached. And as soon as this threshold is passed, there should then be no further fundamental changes in what one sees.

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



Вооруженные жидким азотом оверклокеры неоднократно показывали, что современные чипы могут стабильно работать на частотах в разы выше номинальных, обеспечивая соответствующий рост производительности. Тем не менее, прогресс в области «гонки гигагерц» остановился давно и надежно. Первый «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. Наконец, вопрос об устойчивости системы к малым шумам пока остается без ответа.

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


Сам факт того, что управляемо перемешивая проводки в пучке или кабеле между входом и выходом и не используя никаких других элементов, кроме «перехлестывателей» и повторителей, можно получить на выходе результат вычисления любой функции от входа — далеко не очевиден. Лежащая в основе вычислительная логика необычна, но в отличие от других полных по Тьюрингу математических абстракций, таких как алгоритмы Маркова, выглядит очень «технологичной», готовой к использованию в реальных процессорах. Вполне возможно, квантовые компьютеры будут работать на чем-то похожем, с поправкой на чисто квантовые «трюки». Если совместить консервативную квантовую логику еще и со сверхпроводящими межсоединениями, получится построить действительно практически не поглощающий энергию компьютер. Чтож, будущее покажет.
+108
7 февраля 2011, 22:59
73

комментарии (38)

0
amarao#
Да, что-то такое рассказывали на доп. занятиях по термодинамике в институте.
+5
VitaZheltyakov#
— Во-первых, идея квантового компьютера продвигается для того, что бы обойти принцип Ландауэра. И соответственно, консервативная логика для квантовых компьютеров не нужна.

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

— В-третьих, от предложения «В основе «проблемы тепловыделения» лежит глубокая связь между информационной и термодинамической энтропией, а также второе начало термодинамики, запрещающее уменьшение общей энтропии замкнутой системы.» Эйнштейн и Планк переворачиваются в гробу. Скорее всего в в оригинале имелось в виду под «информационной энтропией» — электромагнитная энтропия.
+5
chainik#
Ну как бы вам сказать, это перевод, а не мое исследование. В оригинале «the two quantities can be identified, the conversion factor being given by relation 1 bit = k ln 2» = «эти две величины (информационную и термодинамическую температуру) можно отождествить, с учетом множителя 1 бит = k ln 2» (вторая страница, последняя строка). И дальше эта фраза много раз повторяется в разных вариантах.
И ничего я не перепутал. Это вы что-то путаете, по крайней мере фразу «электромагнитная энтропия» изобрели вы и сделали это только что, яндекс по крайней мере о таком ничего не слышал.
+1
VitaZheltyakov#
Информационная и термодинамическая энтропия связаны через энтропию электромагнитного состояния, но никак напрямую.
Это примерно как, если заявить, что качество работы программиста напрямую зависит от количества, выпитых им во время работы, кружек чая. Нельзя допускать таких упрощений.
0
nanodust#
>консервативная логика для квантовых компьютеров не нужна.
всё ровно наоборот. Только для квантовых и нужна, ибо там выделение лишней критично для функционирования, у нынешних классических же тепловые и электромагнитные потери на много порядков превосходят потери диктуемые принципом Ландауэра.
0
wirzus#
> В одном грамме любого вещества имеется огромное, порядка…
В одном моле, если не ошибаюсь
+2
grep0#
Вы знаете слово «порядка»?
+3
wirzus#
«Угадай именительный падеж, зная один другой»?
+1
chainik#
Я знаю, что правильно «моль», но в тексте почему-то грамм. Ну, если я не ошибаюсь в арифметике, в одном грамме кремния примерно 0.21*1023 атомов, что вполне укладывается в выражение «порядка 1023»… вот только не помню, сколько у одного атома там степеней свободы.
+1
EGarbuzov#
Для атомарных веществ с небольшой атомной массой (как кремний) это соотношение может примерно сохраняться, но утверждать, что это справедливо длялюбого вещества — точно не стоит. Например, один моль (6,022*10^23 атомов) урана будет весить ~1,4 кг, что в пересчёте на количество атомов в грамме даст результат порядка на 2 меньше.

Степеней свободы, я полагаю, должно быть 3, также как у одноатомного газа.
0
Kolegg#
Прим. пер.: статья рассчитана на физиков, поэтому авторы не приводят иллюстрации к очевидным для физиков вещам.
В физике такие логические скачки встречаются очень часто.
+5
RadioAgent#
давно такого удовольствия от текста и слога не получал. Спасибо за выбранную тему, качественный перевод и отличную в целом статью.
За ссылку на КТ отдельно спасибо. В общем-то Ваш текст мне и напомнил лучшие, с моей точки зрения, времена это замечательного журнала.
0
chainik#
Если честно, где-то в те годы я даже публиковался в «Терре» ;)
0
RadioAgent#
я сразу полез в профиль, как статью прочитал, подумал, может автор из КТ, вдруг узнаю :) не узнал, но как чувствовал
0
Derailed#
До сих пор жалею, что «Терру» уронили… Другого такого бумажного журнала нет.
0
hb860#
А если произвести вычисление, увеличивающее информационную энтропию — тепловая энтропия уменьшится или нет?
+1
chainik#
Нет. Тепловую энтропию можно только «впарить» внешнему миру.
0
Yoshimura#
Бесовщинкой статья попахивает, хотя прочитал с большим удовольствием.
Прошу прощения, но по моему в послесловии переводчик сделал несколько гм., оптимистичное предположение о возможности не поглощающего(затем выделяющего, полагаю) энергию компьютера. По Тому же Ландауэру, собственно, и не получится. На макроуровне реально обратимых задач, решаемых на компьютерах я и придумать то затрудняюсь. И ЭВМ не замкнутая термодинамическая система.
Вроде все логично и правильно, но что-то вот беспокоит. Надо бы изучить вопрос, интересно.
+2
VovixLDR#
НЯП, на макроуровне обратимые задачи не нужны. Обычная задача, поставленная на макроуровне, на микроуровне расширяется до обратимой, с сохранением тех данных, которые обычно удаляются. Грубо говоря, мы просто игнорируем эти данные, но в железе они сохраняются именно в таком состоянии, которое требуется для отвода энергии оттуда, откуда она раньше непосредственно вылетала в трубу (т. е. в тепло).
0
vsviridov#
Классная статья, спасибо.
+1
VovixLDR#
К тегам стоило бы добавить «обратимые вычисления» (reversible computing), именно под этим заголовком я впервые прочитал о данной теме где-то в Компьютерре.
en.wikipedia.org/wiki/Reversible_computing
0
chainik#
тег добавил
ссылка на «где-то в компьютерре» есть в статье)
0
nekt#
Сложно, спорно. Но как минимум, если я понимаю суть верно это позволяет пусть даже не уменьшить тепловыделение, но сместить его куда подальше от вычислительной схемы используя стоки.
+1
ncix#
прямая связь информации с энтропией завораживает. Не знал, зря прогуливал лекции, спасибо!
+1
yopopt#
Интересно, но спорно в части тепловыделения. В теории всё хорошо, а на практике к стокам прибавятся тепловыделение при прохождении тока через элемент логики, потери на соединениях и пр. Как бы в результате реализуя блок + инвертированный не приблизится или даже не превзойти по тепловыделению классическую схему даже не смотря на высокое тепловыделение последней.
+3
GrossHo#
«Мужик, я ничего не понял, что ты сказал. Но ты мне близок. Ты… достучался до моего сердца.» (с) Джей и Молчаливый Боб наносят ответный удар.
На самом деле, пока не понял, как это может пригодится, но это одна из наиболее интересных статей за последнее време.
0
paladin#
Является ли формула k∙T∙ln 2 доказательством того, что информация является материей?
+1
kirushik#
Нет, какая связь?

Это просто энтропия, приписываемая объекту с двумя состояниями (как частный случай формулы k×T×ln(Z) для объекта с Z состояниями).
+1
Yaraife#
Допустим, мы сможем создать процессор основанный на обратимых вычислениях, и что нам это даст?
Поясню, если вычисления обратимы, то нам необходимо где-то сохранять каждое значение.
Имея процессор с тактовой частотой 3 Ггц, по 4 вычисления с плавающей точкой на такт, с 4мя ядрами, мы получим (3*10^9)*(4*2)*4=9.6*10^10 байт\сек, что соответствует 96 Гбайт\сек. У вас есть память, способная сохранять мусорные, никому не нужные результаты вычислений в таких количествах?

Да, принцип Ландауэра интересен, но не в наше время, как уже говорилось выше, нашим процессорам до него ещё на несколько порядков можно оптимизироваться. Поэтому пока(ближайшие пару десятилетий) — это не более чем занимательная теория.
+1
Yaraife#
Более того… Я скажу что обойти принцип Ландауэра тайим способом хотя и можно, но это не более, чем способ утилизации тепла посредством одноразового использования памяти. Т.е. говоря другими словами вы пытаетесь поймать считанные кванты тепла и вместо рассеивания попытаться уместить их в ячейке памяти(будь то маленький конденсатор или химическая реакция на уровне молекул).

Пытаться построить процессор по этим требованиям просто утопично. Гораздо выгоднее поставить машину, которая работает на разнице температур процессора и окружающей среды. Эффект тот же, но нет необходимости извращаться с архитектурой процессора.
+2
chainik#
Вы ничего не поняли.
1. Промежуточные результаты, если все инструкции обратимы, хранить не нужно — они пойдут в дело на следующих шагах алгоритма.
2. В реальных алгоритмах да, появляются ненужные побочные результаты. Но они появляются не на каждом шаге, а только в конце алгоритма (те сливы, которые появляются на внутренних шагах, эффективно убиваются инвертной схемой). Вот конечные сливы придется или загонять в память, или рассеивать в пространстве. Но количество этих сливов есть O(N). А требуемое количество вентилей — O(2N). Вот именно это «оно нам даст».
+1
Yaraife#
Возможно, некоторые алгоритмы можно таким методом решать с меньшим выделением тепла. Но что если взять в качестве примера вычисления в реальном времени (графика в играх, обработка входящих пакетов). Далеко не все вычисления можно представить в виде линейного алгоритма.

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

Это может иметь смысл при оптимизации процессоров в тысячи раз, исключительно линейных алгоритмах, когда тепловое выделение от уничтожения информации можно будет хотя бы сравнить с другими источниками выделения тепла.
+1
chainik#
Не, там всё не так.
Сейчас компы работают на базе транзисторов в ключевом режиме. Более 90% тепла выделяется в операции переключения транзисторов между открытым и закрытым состоянием (между 0 и 1). Остальное — это разные паразитные потери. Сами транзисторы, пока их не переключают, потребляют совсем крошечный процент мощности.
Консервативная логика реализуется на колебательных LRC контурах и транзисторах в ключевом режиме. Частоты подобраны так, чтобы колебательные контуры были в резонансе, поэтому реактивное сопротивление схемы почти ноль, активное — копеечное. Переключения транзисторов практически не происходит, поэтому остаются только те самые паразитные 10%.
Проблема только в том, что в отличие от сопротивлений и конденсаторов, в кремнии нельзя сделать катушки (L).
+1
chainik#
Блин, предыдущий комент рано отправился.
Так вот, сказать «усложнение в несколько раз» нельзя. Если считать по количеству вентилей, то схемы консервативной логики в среднем проще, чем аналогичные традиционные.
Но при этом сам вентиль Фредкина устроен намного сложнее вентиля И-НЕ. Но самое главное, конечно, необхомость использования индуктивностей.
+1
Yaraife#
Пока не будет найден способ реализовать в наномаштабе компонент с индуктивностью, это всего лишь теория… Или реальность, но с большим количеством усложнений.

Мне стало интересно сколько именно дж\сек выдает процессор только из-за Ландауэра:
k*T*ln(2)*(транзисторов)*(частота) — 56.9С*, камень Tukwila для серверов, 100% загрузки
(1.38*10^-23)*330*ln(2)*(2*10^9)*(2*10^9)*1 = 0.0126 Дж\сек
Средний процессор выделяет 70 Дж\сек
Ландауэр вносит свой вклад в размере 0.018% или 1\5560

Согласно закону Мура потребуется ещё 11 циклов (16.5-22 года), пока пока принцип Ландауэра будет влиять на тепловыделение процессора хотя бы на треть.

www.kgs.ru/articles/tehnologii/news_2008-02-04-23-44-50-216.html — Tukwila
www.advercom.kz/index.php?option=com_content&task=view&id=126&Itemid=43 — Тепловыделение

— Хотя в предыдущих комментариях я действительно не учел внутренние шаги при вычислениях. Если обратимые вычисления действительно смогут снизить количество сливов с O(2^N) до O(N), то это будет действительно скачком вперед. Только ландауэр тут будет уже ни при чем. На данный момент даже квантовые компьютеры к нам ближе, чем обратимые вычисления.

П.С. мне кажется весьма сложным сделать реальный процессор, в котором все вентили подогнаны так, чтобы быть в резонансе друг с другом, несмотря на проводимые вычисления, взаимодействие магнитных полей друг с другом, быстрый саморазряд конденсаторов и принципиально иной способ построения логических схем.
0
Yaraife#
Не учел, что некоторые транзисторы могут содержать несколько логических вентилей, но думаю это можно компенсировать тем, что в процессоре % активных транзисторов не превышает 75% в пиковые нагрузки(а при нормальной работе соответственно, меньше).
0
barbalion#
> те сливы, которые появляются на внутренних шагах, эффективно убиваются инвертной схемой
Может я что-то не до конца понял, но почему нельзя просто сливы замкнуть через диодный мост на константы? Тем самым весь заряд «ненужный» в данном месте пойдет туда, где он нужен…
Где я не прав?
0
DankoUA#
Красота