Хакнуть Ландауэра

В 1961-м году Рольф Ландауэр в своей статье «Irreversibility and heat generation in the computing process» сформулировал принцип, согласно которому в любой вычислительной системе, независимо от её физической реализации, при потере 1 бита информации выделяется теплота в количестве по крайней мере W = kB T ln2, где kB − постоянная Больцмана, а T − температура вычислительной системы в кельвинах.

То есть если вычисление производится при комнатной температуре (300K), то при потере 1 бита данных вычислительная система не может не рассеять в окружающее пространство примерно 2,7×10-21 Дж.

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

Откуда взялось ограничение


Ключ к пониманию того, из чего следует принцип Ландауэра − во фразе "A simple binary device consists of a particle in a bistable potential well" (простейшее двоичное устройство состоит из частицы в двухстабильной потенциальной яме):


Для того, чтобы переключить систему с состояния «0» в состояние «1» (или наоборот), мы должны:

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

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

Преодолеваем ограничение


Будем исходить из того, что все приведённые выше рассуждения верны (у сообщества с 1961 года было достаточно времени проверить все теоретические выкладки), и, как следствие, для случая двухстабильной потенциальной ямы верна формула W = kB T ln2.

Для преодоления ограничения вместо двоичной системы кодирования данных применим четверичную. Соответственно изменится схема устройства:


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

W = kB T ln2 / 2

Барьер Ландауэра оказался снижен ровно в два раза. Если в системе сделать не 4 потенциальных ямки, а 8, то величина необходимо рассеиваемой энергии станет W = kB T ln2 / 3. В предельном случае, когда количество потенциальных ямок устремляется к бесконечности (не представляю себе, как это может быть реализовано на практике, но в теории такое имеет право на существование) барьер Ландауэра устремляется к нулю.

Вывод


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

UPD (необходимое уточнение, спасибо Pshir): обратите пожалуйста внимание на вот эту цепочку комментариев: этотэтоти вот этот.
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 29

    +1
    Только теперь энергия W расходуется не на один бит данных, а на два.
    А откуда следует, что величина W сохранится и что она по-прежнему будет расходоваться один раз, а не два или три?
      –2
      А почему высота барьерчиков в четырёхстабильной яме должна быть другой? Высота барьерчика должна быть ровно такая, чтобы исключить самопроизвольное перескакивание шарика, и поэтому определяется только температурой, но никак не количеством ямок.
      +5
      В данной статье содержится элементарнейшая логическая ошибка: автор совершенно безосновательно предполагает, что глубина ямы (и, соответственно, величина отбираемой энергии) в системе из 4 состояний в точности равна глубине ямы в системы из двух состояний.

      И пока он не сможет ДОКАЗАТЬ это своё допущение, все остальные его рассуждения не имеют никакого смысла.
        0
        Это действительно странно. Имхо, очевидно что два первых перехода (00 -> 01 и 01 -> 10) отличаются по энергозатратам, не говоря уже о том, что в реальности переходы бывают и другими (00 -> 11), сводящие всю экономию к нулю (если точнее, средняя энергия потраченная на все варианты переходов, если её посчитать математически, остаётся неизменной как для одно-знаковых переходов так и для дву-знаковых). Хотя может я и не прав =)

        Возможно нужно всю «научность статьи» списать на то, что «это же Гиктаймс и так сойдёт» (с) немоё.
          0
          В микромире немножко не те законы, как в нашем грешном макромире.
          Это нас шарик, перекатившись из 00 в 01, потратит энергию на трение и на сопротивление воздуха, и следующую горку уже не одолеет. А в микромире в той конструкции, которая нарисована на рисунке, если шарик имеет энергию, достаточную для преодоления одной горки, он начинает вечно туда-сюда кататься, пока в какой-нибудь из лунок у него энергию специально не отберут.
          Это, собственно, и будет тот самый dissipation, который необходим в необратимых вычислениях.
            0
            Речь о том, что изменение состояния: 00 -> 01 и 01 -> 10 либо отличаются по затратам энергии либо нет (определитесь в этом месте и чётко напишите) и о том, что так же в природе (уже в нашей с вами) так же бывают преобразования вида 00 -> 11. И если взять все возможные комбинации переходов состояний вашей модели и модели Ландауэра окажется, что по модулю потери энергии остались прежними, просто вы увеличили количество вариантов (где-то мы тратим меньше, где то больше).
              0
              На первый взгляд действительно может показаться, что переключения «00->01», «00->10» и «00->11» принципиально отличаются друг от друга. В первом случае нужно преодолеть один холмик, во втором два, в третьем все три. Но что если добавить измерений и сделать конструкцию двумерной? Например, вот так:
               00 | 01
              ---------
               10 | 11

              Получаем, что переключения «00->01» и «00->10» перестали отличаться друг от друга, но «00->11» по-прежнему особняком. А теперь представьте себе тетраэдр… Намёк понятен?

              Помните пожалуйста, что картинка с ямками и холмиками — это всего лишь визуализация. По оси «иксов» у нас совсем не обязательно пространственная координата.
                0
                Подождите, речь именно о переходах между состояниями.
                Ответьте чётко:
                1. Верно ли что переходы «00->01», «01->10» требуют одинаковой энергии?
                Повнимательнее к битности. Это важно. В вашем комментарии выше в указываете не те переходы, что я.
                2. Верно ли что переход «00->11» осуществляется с одинаковым импульсом энергии что и любой вида 00->01», «00->10»?

                Если второе верно — покажите тип памяти (прототип) или логику ваших рассуждений.
                  –1
                  1. Все переходы требуют одинаковой энергии. Если энергия частицы поднялась так, что ей становится доступным преодоление первого холмика, то и все остальные ей становятся одинаково доступны.
                  2. Да, конечно.

                  >> Если второе верно — покажите тип памяти (прототип) или логику ваших рассуждений.

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

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

                  Допустим, результатом вычисления является направление, в котором вылетает фотон. Регистрируем этот результат двумя фотоэлементами. Такая система, как и положено, будет на запись (скорее, на последующее стирание) одного бита тратить минимум kB T ln2 джоуля. Но если фотоэлементов не два, а четыре? А если сто? А если миллион? Количество рассеиваемых джоулей остаётся неизменным, но количество бит уже другое. Для миллиона это почти 20.
                    0
                    Вот теперь отлично. Спасибо.

                    Добавьте что-то подобное в пост.
                    Изначально не ясно (или мне не ясно), что речь идёт не про переход одного состояния бита в другое состояние бита, а про то, что мы строим модель памяти таким образом, что состояния ячеек для 00,01,10,11 являются независимыми и могут быть выбраны (изменены), за любую одну транзакцию. Исходя из этого, логично, что цена транзакции для изменения одного бита становится меньше, ведь по факту в ситуации 00 -> 11 мы за туже «цену» меняем два бита.

                    Однако думаю всё это концепции и теории.
                    Но если что, упоминайте меня в патентах, пожалуйста. =)

                    **я не минусовал, минусовал не я.
                      –1
                      Ну, не знаю… Лично для меня очевидно, что картинка с четырьмя ямками и тремя горбиками всё наглядно иллюстрирует. Тут же важен принцип, а детали физической реализации традиционно могут быть любыми. В том числе и такими, о которых мы даже помыслить не можем.

                      >> Однако думаю всё это концепции и теории.

                      Всё когда-то начиналось как концепции и теории ;)

                      Вообще, сочиняя эту шалость, я меньше всего думал о новых элементных базах (хотя если мобильник будет чуть медленнее разряжаться, то это тоже сладко). Настоящий интерес, конечно, сильно глубже. Дело в том, что принцип Ландауэра [был] самым сильным аргументом в пользу эквивалентности термодинамической и информационной энтропий. Остальные аргументы значительно слабее. Если устраняется фундаментальность принципа Ландауэра, то всё становится намного интереснее, чем было раньше.
        +3
        Мы по-прежнему для переключения состояния должны придать частице энергию для преодоления барьера и по-прежнему должны (в случае необратимого вычисления) излишек энергии рассеять в виде тепла.
        И в результате попадём в случайную яму из трёх других. Для того, чтобы попасть в конкретную, придётся потратить дополнительную энергию. И что-то (знакомство с термодинамикой) мне подсказывает, что верный расчёт даст тот же самый результат Ландауэра.
          0
          В двухстабильной потенциальной яме шарик попадает в ту яму, в которой у него отобрали излишек энергии. В четырёхстабильной — та же история. Разницы — никакой.
            0
            То есть вам нужно дополнительное устройство, которое будет выбирать яму?
              –1
              Обязательно. Но только эта штука не учитывается Ландауэром в его оригинальной статье (по всей видимости, очень не зря не учитывается), и поэтому здесь мы тоже не будем её учитывать, ладно?
                0
                В оригинальной статье Ландауэром рассматривается замкнутая система. Именно для замкнутой системы получен результат. Если вы рассматриваете открытую систему, то в такой системе в тепло можно вообще ничего не переводить в идеале (всё тепло будет выделяться где-то снаружи), но ничего нового или интересного этот результат не представляет — так любая система охлаждения работает.
                  –1
                  В том-то всё и дело, что я в данном случае вообще не забиваю себе голову никакими термодинамическими выкладками. Суть происходящего — именно хакинг, что и отражено в названии. Весь математический аппарат и весь физический бэкграунд я априорно считаю правильным (ремарка «у сообщества с 1961 года было достаточно времени проверить все теоретические выкладки»). Просто на вход этих теоретических выкладок подаю систему не с двумя ямками, а с четырьмя и вижу, что сумма «к оплате» не изменилась. Только мы теперь платим её не за 1 бит, а за два.

                  Если бы сейчас был 1961-год и уважаемый господин Ландауэр запостил свою статью не в IBM Journal, а на форум, то суть своей претензии я мог бы выразить примерно таким комментом: «Hey, bro, why do you considered simple binary device as a bistable? What if such device has more then two stable states?»
                    +1
                    В том-то всё и дело, что я в данном случае вообще не забиваю себе голову никакими термодинамическими выкладками.
                    И очень зря.
                    Просто на вход этих теоретических выкладок подаю систему не с двумя ямками, а с четырьмя и вижу, что сумма «к оплате» не изменилась.
                    Это не так.
                    What if such device has more then two stable states?
                    Then W=kT*ln(N), where N is the number of the stable states.
                      0
                      Теперь понятно. Спасибо. Имеет место мой косячок. Даже два. В первый раз косякнул, когда поделил на два (этого реально не следовало делать), а второй раз — когда не включил критическое восприятие на фразе "Note that our argument here does not necessarily depend upon connections, frequently made in other writings, between entropy and information" (верх правой колонки 5-й страницы файла).

                      Ведь зависит. Очень даже зависит. Никак нельзя ввести в рассуждение о количестве информации постоянную Больцмана (которая меряется в джоулях на кельвин) без того, чтобы не приравнять информационную энтропию термодинамической. Сделав это, конечно, следующим шагом мы умножаем получившееся на температуру в кельвинах, и получаем джоули. На редкость простая и незатейливая магия. Потому-то формула и получилась такой красивой. А я-то ещё думал-гадал, каким же таким образом удалось избавиться от некоторой всегда присутствующей в термодинамических системах неопределённости энергии частицы… Да никаким.

                      В сухом остатке, про принцип Ландауэра можно сказать следующее (поправьте меня, если я не прав):

                      1. Само по себе требование рассеивания энергии при выполнении необратимого вычисления выглядит разумным, поскольку от необходимости «забывания» данных после манипуляции энергетическими уровнями никуда не деться.

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

                      Эх, никому нельзя верить. Ни другим, ни себе, ни, тем более, авторитетному мнению старших товарищей :))
                        0
                        Да, совершенно правильные выводы
          0
          Вы не учли геометрию пространства, допустим 2-х битный транзистор имеет размер 50 нм, тогда при том же тех. процессе ваш 4-х битный транзистор будет иметь размер ~100 нм (конечно небольшая экономия расстояния будет), так же имейте в виду, что в процессоре справа от двухбитного транзистора, стоит еще 1 транзистор, слева, впереди и сзади тоже транзистор, сверху теплоотвод, снизу контакты с памятью, т.е. — свободного места нет, и от увеличения длины транзистора, плотность информации не поменяется.

          Так же учтите что теплота(энтропия), распространяется равномерно во все 6 сторон и если транзистор слева использует энергию соседа, что бы сменить свое состояние, то так же ОБЯЗАТЕЛЬНО поступят транзисторы со всех сторон.
          Вы можете сделать транзисторы из разных материалов, тогда они будут по разному реагировать на действия соседа, но тогда после каждого такта процессора вам придется переставлять транзисторы из разных материалов.

          Дело не в «удалении информации» — дело в движении материи, которое всегда сопровождается повышением температуры «движущейся частицы», после чего и появляется теплообмен.

          Вы не можете изменить состояние транзистора — ничего ни куда не двигая.

            0
            Понимаете, дело ведь совсем не в конструкциях транзисторов. Вычислительный процесс — это ведь не только кремний, подложка, электрические контакты и прочие знакомые с детства вещи.

            Коварство принципа Ландауэра как раз в том, что требование рассеивания порции энергии при выполнении необратимого вычисления выдвигаются вне зависимости от того, на каких физических принципах реализовано вычисление. Электроника — да, он работает. Какая-нибудь спинтроника или фотоника — тоже. Именно поэтому этот принцип всегда рассматривается как фундаментальное ограничение.

            Теперь же понятно, что это никакое не фундаментальное ограничение, и при желании и некоторой сноровке планочку можно понизить в два раза. Или в три. Или, особо исхитрившись, убрать совсем.
          • НЛО прилетело и опубликовало эту надпись здесь
              0
              Я не настолько хорошо знаком с тематикой «квантовые компьютеры», чтобы браться рассуждать об их термодинамике. Хотя что-то мне подсказывает, что кубит гораздо больше похож на устремлённое к бесконечности количество потенциальных ямок, чем на нашу родную двухстабильную, хранящую классический бит.
                0

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


                Автору поста — Принцип Ландауэра работает, когда нам нужно стереть неизвестную нам информацию. Т.е. частица есть в одной из 2 ям, но мы не знаем в какой именно (если мы знаем текущий уровень, переключения можно достичь с меньшем уровнем энергии — http://www.ethlife.ethz.ch/archive_articles/110601_Naturepaper_Renner_su/index_EN " Landauer Principle holds true only if the value of the bits to be deleted is unknown. Erasing a memory is normally an irreversible process, but if the memory content is known, it is possible to delete it in such a way that, in theory, it could be restored.").
                Также — уже при приближении к уровню тепловыделения Ландауэра снижается надежность вычислений (обычно берут уровень 100 k_b T как надежный — http://userweb.eng.gla.ac.uk/douglas.paul/images/PvsSpeed.gifhttp://userweb.eng.gla.ac.uk/douglas.paul/SiGe/limits.html).
                Ваши идеи с большим количеством стабильных состояний и предельный случай с бесконечным количеством (даже если бы большое количество ям было бы физически реализуемо) значительно снизят надежность хранения и обработки информации. Чтобы улучшить надежность — надо увеличивать высоту барьеров, т.е. увеличивать энергию, требуемую на стирание.

                  –1
                  Уже здесь разобрались с тем, что фокус с четырьмя ямками не прокатит, о чём в конец поста торжественно вписан «UPD».

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

                  Может быть, можно вообще по этому поводу ни капли не переживать, и темой «обратимые вычисления» себе голову не забивать?
                    0

                    Обратимые вычисления — единственный способ строить квантовые алгоритмы (на которых квантовый компьютер даст значительное ускорение по сравнению с классическими).
                    Также они полезны в ряде криогенных неCMOS-вычислителей (например, сверхпроводниковых, http://spectrum.ieee.org/semiconductors/design/superconductor-logic-goes-lowpower) для уменьшения тепловыделения в "холодной части" (холодильная машина потребляет примерно в 1000 раз больше энергии, чем отводит от вычислителя, находящегося при температуре единицы кельвинов и ниже).
                    Ландауэр — лишь один из нескольких лимитов, и точно не из тех проблем, с которыми создатели компьютеров столкнуться в ближайшее время (закон Мура кончится раньше, чем столкнется с Ландауэром). Часть из лимитов можно обойти, часть — нет, см https://en.wikipedia.org/wiki/Limits_to_computation. В частности, из-за ряда лимитов существуют https://en.wikipedia.org/wiki/Transcomputational_problem.


                    Из некоторых более близких ограничений, рассматриваемых в контексте крупнейших суперкомпьютеров (exascale, zettascale и далее?): нельзя потратить на вычисления больше электричества, чем добывается на этой планете (слайд 4); стоимость производства чипов растет — требуются все большие тиражи проектов (слайд.24, но больше нескольких млрд чипов продать тяжело); пересылка данных вне чипа уже потребляет на порядок или два больше энергии, чем вычисления (https://doi.ieeecomputersociety.org/cms/Computer.org/dl/mags/cs/2013/06/figures/mcs20130600165.gif). Также — 5. Challenges in Going to the Exascale — стр 46 http://science.energy.gov/~/media/ascr/ascac/pdf/reports/Exascale_subcommittee_report.pdf


                    Перед Ландауэровским лимитом будет тепловой шум, значительно снижающий надежность логических элементов (до уровня полной непригодности для построения схем) — см https://books.google.ru/books?id=U1Gcp1S__hEC&pg=PA114& — 5.7.1 Thermal Noise — Un=sqrt(kT/C) "To provide adequate protection against the occurrence of errors, ..such that the voltage difference between a 1 and 0 is about 11 or 12 times Un.… Landauer's limit is very much a lower bound for a gate. A gate dissipating energy at this rate so close to the thermal noise level would be too unreliable for practical use." Уже сейчас в суперкомпьютерах ставят столько памяти, что двойные ошибки ECC в оперативной практике могут встречаться ежедневно — http://moss.csc.ncsu.edu/~mueller/ftp/pub/mueller/papers/sc12.pdf "While double bit flips were deemed unlikely, the density of DIMMs at Oak Ridge National Lab’s Cray XT5 causes them to occur on a daily basis (at a rate of one per day for 75,000+ DIMMs) [8]". Уже ставят ECC на все уровни кэш-памяти (а не только L3/L2 как раньше) и думают про детектирование ошибок в АЛУ: "only caches feature ECC while register files or even ALUs typically do not."


                    Пишут, что на начало 2010-х CMOS работал на уровнях в на 6 порядков дальше Ландауэра и может приблизиться к 5 порядкам — http://snf.ieeecsc.org/sites/ieeecsc.org/files/ST242.pdf "in modern CMOS
                    chips, the practical switching energy is about 10^6 x E_BITMIN in order to ensure practical requirements for reliability, speed, drivability, and data communication (local and global interconnect). It is hoped that with advances in localizing interconnects (e.g., with 3D packaging), it would be possible to reduce power associated with charging long interconnect lines. This would decrease the practical CMOS switching energy to ~10^5 x E_BITMIN [3]
                    "


                    PS: Статья о других способах "взломать" Ландауэра — https://arxiv.org/pdf/1406.2562v2.pdf Conditional entropy and Landauer principle — 2015

                      –1
                      Обратимые вычисления — единственный способ строить квантовые алгоритмы

                      Квантовые вычисления — на редкость любопытная штука. Но раз уж Вы в теме, не сочтите за труд хотя бы намекнуть, какие реальные профиты с неё ожидаются кроме всем известного угробления гражданской криптографии?

                      https://en.wikipedia.org/wiki/Limits_to_computation

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

                      А что такое вещественное число, если его выразить в битах? Это строго бесконечное разнообразие. Которое везде. Которое есть естественное состояние нашего мира. И в микро, и в макро. Целый океан бесконечных разнообразий, и мы естественным образом сами являемся его бесконечно разнообразными частями. И ничего ведь, что интересно, ни в какие чёрные дыры не коллапсирует. Как так получается? Тут определённо есть над чем подумать…
                        –2
                        Кстати, спасибо за «Conditional entropy». Идея иметь не сумму PilnPi, а интеграл — чудо как хороша.

                        Вы мне написали ещё один комментарий, но я его здесь не вижу. Но это же не значит, что я его не читал и не могу на него ответить, правда?
                        dwave.wordpress.com/2007/02/24/factoring-as-a-red-herring
                        Maybe it’s time to put away the fish

                        Вот это уже совсем другое дело. Что ж, единственное, что мне в данном случае остаётся — это пожелать удачи в этих делах.

                        geektimes.ru/post/281476 в котором не более 10 комментов несут смысл

                        Будьте снисходительны. В такой скользкой теме это не "всего лишь", а "аж целых" 10 комментов.

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

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

                Самое читаемое