То есть если вычисление производится при комнатной температуре (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): обратите пожалуйста внимание на вот эту цепочку комментариев: этот > этот > и вот этот.
Комментарии (29)
eandr_67
02.11.2016 13:55+5В данной статье содержится элементарнейшая логическая ошибка: автор совершенно безосновательно предполагает, что глубина ямы (и, соответственно, величина отбираемой энергии) в системе из 4 состояний в точности равна глубине ямы в системы из двух состояний.
И пока он не сможет ДОКАЗАТЬ это своё допущение, все остальные его рассуждения не имеют никакого смысла.
ifaustrue
02.11.2016 14:04Это действительно странно. Имхо, очевидно что два первых перехода (00 -> 01 и 01 -> 10) отличаются по энергозатратам, не говоря уже о том, что в реальности переходы бывают и другими (00 -> 11), сводящие всю экономию к нулю (если точнее, средняя энергия потраченная на все варианты переходов, если её посчитать математически, остаётся неизменной как для одно-знаковых переходов так и для дву-знаковых). Хотя может я и не прав =)
Возможно нужно всю «научность статьи» списать на то, что «это же Гиктаймс и так сойдёт» (с) немоё.maslyaev
02.11.2016 14:53В микромире немножко не те законы, как в нашем грешном макромире.
Это нас шарик, перекатившись из 00 в 01, потратит энергию на трение и на сопротивление воздуха, и следующую горку уже не одолеет. А в микромире в той конструкции, которая нарисована на рисунке, если шарик имеет энергию, достаточную для преодоления одной горки, он начинает вечно туда-сюда кататься, пока в какой-нибудь из лунок у него энергию специально не отберут.
Это, собственно, и будет тот самый dissipation, который необходим в необратимых вычислениях.ifaustrue
02.11.2016 14:58Речь о том, что изменение состояния: 00 -> 01 и 01 -> 10 либо отличаются по затратам энергии либо нет (определитесь в этом месте и чётко напишите) и о том, что так же в природе (уже в нашей с вами) так же бывают преобразования вида 00 -> 11. И если взять все возможные комбинации переходов состояний вашей модели и модели Ландауэра окажется, что по модулю потери энергии остались прежними, просто вы увеличили количество вариантов (где-то мы тратим меньше, где то больше).
maslyaev
02.11.2016 15:51На первый взгляд действительно может показаться, что переключения «00->01», «00->10» и «00->11» принципиально отличаются друг от друга. В первом случае нужно преодолеть один холмик, во втором два, в третьем все три. Но что если добавить измерений и сделать конструкцию двумерной? Например, вот так:
00 | 01 --------- 10 | 11
Получаем, что переключения «00->01» и «00->10» перестали отличаться друг от друга, но «00->11» по-прежнему особняком. А теперь представьте себе тетраэдр… Намёк понятен?
Помните пожалуйста, что картинка с ямками и холмиками — это всего лишь визуализация. По оси «иксов» у нас совсем не обязательно пространственная координата.ifaustrue
02.11.2016 15:58Подождите, речь именно о переходах между состояниями.
Ответьте чётко:
1. Верно ли что переходы «00->01», «01->10» требуют одинаковой энергии?
Повнимательнее к битности. Это важно. В вашем комментарии выше в указываете не те переходы, что я.
2. Верно ли что переход «00->11» осуществляется с одинаковым импульсом энергии что и любой вида 00->01», «00->10»?
Если второе верно — покажите тип памяти (прототип) или логику ваших рассуждений.maslyaev
02.11.2016 16:58-11. Все переходы требуют одинаковой энергии. Если энергия частицы поднялась так, что ей становится доступным преодоление первого холмика, то и все остальные ей становятся одинаково доступны.
2. Да, конечно.
>> Если второе верно — покажите тип памяти (прототип) или логику ваших рассуждений.
Ну Вы прям хотите, чтобы я сразу придумал, рассказал и, желательно, показал действующий прототип нового прорыва в элементной базе. Не требуйте от меня такого ужаса. Я простой скромный программист ;)
Мы все привыкли, что в нашем дивном цифровом мире данные всегда записываются отдельными ноликами и единичками. Настолько привыкли, что воспринимаем это как само собой разумеющийся единственный вариант. Но это, конечно, просто привычка. Следствие того, что двухстабильные потенциальные ямы проще реализуются «в кремнии».
Допустим, результатом вычисления является направление, в котором вылетает фотон. Регистрируем этот результат двумя фотоэлементами. Такая система, как и положено, будет на запись (скорее, на последующее стирание) одного бита тратить минимум kB T ln2 джоуля. Но если фотоэлементов не два, а четыре? А если сто? А если миллион? Количество рассеиваемых джоулей остаётся неизменным, но количество бит уже другое. Для миллиона это почти 20.ifaustrue
02.11.2016 17:02Вот теперь отлично. Спасибо.
Добавьте что-то подобное в пост.
Изначально не ясно (или мне не ясно), что речь идёт не про переход одного состояния бита в другое состояние бита, а про то, что мы строим модель памяти таким образом, что состояния ячеек для 00,01,10,11 являются независимыми и могут быть выбраны (изменены), за любую одну транзакцию. Исходя из этого, логично, что цена транзакции для изменения одного бита становится меньше, ведь по факту в ситуации 00 -> 11 мы за туже «цену» меняем два бита.
Однако думаю всё это концепции и теории.
Но если что, упоминайте меня в патентах, пожалуйста. =)
**я не минусовал, минусовал не я.maslyaev
02.11.2016 17:52-1Ну, не знаю… Лично для меня очевидно, что картинка с четырьмя ямками и тремя горбиками всё наглядно иллюстрирует. Тут же важен принцип, а детали физической реализации традиционно могут быть любыми. В том числе и такими, о которых мы даже помыслить не можем.
>> Однако думаю всё это концепции и теории.
Всё когда-то начиналось как концепции и теории ;)
Вообще, сочиняя эту шалость, я меньше всего думал о новых элементных базах (хотя если мобильник будет чуть медленнее разряжаться, то это тоже сладко). Настоящий интерес, конечно, сильно глубже. Дело в том, что принцип Ландауэра [был] самым сильным аргументом в пользу эквивалентности термодинамической и информационной энтропий. Остальные аргументы значительно слабее. Если устраняется фундаментальность принципа Ландауэра, то всё становится намного интереснее, чем было раньше.
Pshir
02.11.2016 14:26+3Мы по-прежнему для переключения состояния должны придать частице энергию для преодоления барьера и по-прежнему должны (в случае необратимого вычисления) излишек энергии рассеять в виде тепла.
И в результате попадём в случайную яму из трёх других. Для того, чтобы попасть в конкретную, придётся потратить дополнительную энергию. И что-то (знакомство с термодинамикой) мне подсказывает, что верный расчёт даст тот же самый результат Ландауэра.maslyaev
02.11.2016 14:58В двухстабильной потенциальной яме шарик попадает в ту яму, в которой у него отобрали излишек энергии. В четырёхстабильной — та же история. Разницы — никакой.
Pshir
02.11.2016 16:00То есть вам нужно дополнительное устройство, которое будет выбирать яму?
maslyaev
02.11.2016 17:13-1Обязательно. Но только эта штука не учитывается Ландауэром в его оригинальной статье (по всей видимости, очень не зря не учитывается), и поэтому здесь мы тоже не будем её учитывать, ладно?
Pshir
02.11.2016 20:11В оригинальной статье Ландауэром рассматривается замкнутая система. Именно для замкнутой системы получен результат. Если вы рассматриваете открытую систему, то в такой системе в тепло можно вообще ничего не переводить в идеале (всё тепло будет выделяться где-то снаружи), но ничего нового или интересного этот результат не представляет — так любая система охлаждения работает.
maslyaev
02.11.2016 21:10-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?»Pshir
02.11.2016 23:21+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.maslyaev
03.11.2016 13:01Теперь понятно. Спасибо. Имеет место мой косячок. Даже два. В первый раз косякнул, когда поделил на два (этого реально не следовало делать), а второй раз — когда не включил критическое восприятие на фразе "Note that our argument here does not necessarily depend upon connections, frequently made in other writings, between entropy and information" (верх правой колонки 5-й страницы файла).
Ведь зависит. Очень даже зависит. Никак нельзя ввести в рассуждение о количестве информации постоянную Больцмана (которая меряется в джоулях на кельвин) без того, чтобы не приравнять информационную энтропию термодинамической. Сделав это, конечно, следующим шагом мы умножаем получившееся на температуру в кельвинах, и получаем джоули. На редкость простая и незатейливая магия. Потому-то формула и получилась такой красивой. А я-то ещё думал-гадал, каким же таким образом удалось избавиться от некоторой всегда присутствующей в термодинамических системах неопределённости энергии частицы… Да никаким.
В сухом остатке, про принцип Ландауэра можно сказать следующее (поправьте меня, если я не прав):
1. Само по себе требование рассеивания энергии при выполнении необратимого вычисления выглядит разумным, поскольку от необходимости «забывания» данных после манипуляции энергетическими уровнями никуда не деться.
2. Количественная оценка минимально необходимо рассеиваемой энергии верна только при условии истинности гипотезы о равенстве (не просто соответствии, а именно равенстве) термодинамической и информационной энтропий. В любом случае, использование принципа Ландауэра для доказательства истинности гипотезы о соответствии энтропий является недопустимой логической петлёй.
Эх, никому нельзя верить. Ни другим, ни себе, ни, тем более, авторитетному мнению старших товарищей :))
SaniaA3
02.11.2016 14:51Вы не учли геометрию пространства, допустим 2-х битный транзистор имеет размер 50 нм, тогда при том же тех. процессе ваш 4-х битный транзистор будет иметь размер ~100 нм (конечно небольшая экономия расстояния будет), так же имейте в виду, что в процессоре справа от двухбитного транзистора, стоит еще 1 транзистор, слева, впереди и сзади тоже транзистор, сверху теплоотвод, снизу контакты с памятью, т.е. — свободного места нет, и от увеличения длины транзистора, плотность информации не поменяется.
Так же учтите что теплота(энтропия), распространяется равномерно во все 6 сторон и если транзистор слева использует энергию соседа, что бы сменить свое состояние, то так же ОБЯЗАТЕЛЬНО поступят транзисторы со всех сторон.
Вы можете сделать транзисторы из разных материалов, тогда они будут по разному реагировать на действия соседа, но тогда после каждого такта процессора вам придется переставлять транзисторы из разных материалов.
Дело не в «удалении информации» — дело в движении материи, которое всегда сопровождается повышением температуры «движущейся частицы», после чего и появляется теплообмен.
Вы не можете изменить состояние транзистора — ничего ни куда не двигая.
maslyaev
02.11.2016 15:39Понимаете, дело ведь совсем не в конструкциях транзисторов. Вычислительный процесс — это ведь не только кремний, подложка, электрические контакты и прочие знакомые с детства вещи.
Коварство принципа Ландауэра как раз в том, что требование рассеивания порции энергии при выполнении необратимого вычисления выдвигаются вне зависимости от того, на каких физических принципах реализовано вычисление. Электроника — да, он работает. Какая-нибудь спинтроника или фотоника — тоже. Именно поэтому этот принцип всегда рассматривается как фундаментальное ограничение.
Теперь же понятно, что это никакое не фундаментальное ограничение, и при желании и некоторой сноровке планочку можно понизить в два раза. Или в три. Или, особо исхитрившись, убрать совсем.
Robotex
02.11.2016 17:02А в квантовых компьютерах, тепло наоборот поглощается. Так что нужно собирать гибридные компьютеры с нулевым тепловыделением :)
maslyaev
02.11.2016 17:59Я не настолько хорошо знаком с тематикой «квантовые компьютеры», чтобы браться рассуждать об их термодинамике. Хотя что-то мне подсказывает, что кубит гораздо больше похож на устремлённое к бесконечности количество потенциальных ямок, чем на нашу родную двухстабильную, хранящую классический бит.
a5b
03.11.2016 15:43В квантовых компьютерах во время вычисления нельзя стирать информацию, т.к. при этом выделится тепло и нарушится суперпозиция между кубитами. Почти вся схема на квантовых вентилях — обратима.
Автору поста — Принцип Ландауэра работает, когда нам нужно стереть неизвестную нам информацию. Т.е. частица есть в одной из 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.gif — http://userweb.eng.gla.ac.uk/douglas.paul/SiGe/limits.html).
Ваши идеи с большим количеством стабильных состояний и предельный случай с бесконечным количеством (даже если бы большое количество ям было бы физически реализуемо) значительно снизят надежность хранения и обработки информации. Чтобы улучшить надежность — надо увеличивать высоту барьеров, т.е. увеличивать энергию, требуемую на стирание.maslyaev
03.11.2016 16:38-1Уже здесь разобрались с тем, что фокус с четырьмя ямками не прокатит, о чём в конец поста торжественно вписан «UPD».
Теперь внезапно открылся вопрос, не является ли принцип Ландауэра красивой, но всё же гипотезой, которую пока что просто не было технической возможности хорошенечко экспериментально прощупать.
Может быть, можно вообще по этому поводу ни капли не переживать, и темой «обратимые вычисления» себе голову не забивать?a5b
03.11.2016 17:47Обратимые вычисления — единственный способ строить квантовые алгоритмы (на которых квантовый компьютер даст значительное ускорение по сравнению с классическими).
Также они полезны в ряде криогенных не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
maslyaev
03.11.2016 21:11-1Обратимые вычисления — единственный способ строить квантовые алгоритмы
Квантовые вычисления — на редкость любопытная штука. Но раз уж Вы в теме, не сочтите за труд хотя бы намекнуть, какие реальные профиты с неё ожидаются кроме всем известного угробления гражданской криптографии?
https://en.wikipedia.org/wiki/Limits_to_computation
Несложно заметить, что существенная часть этих пределов основана на эквивалентности энтропий. Например, предел Бекенштейна, согласно которому разнообразие, запихнутое в некий объём, не может достичь некоего предела без того, чтобы там образовалась чёрная дыра. Это, конечно, впечатляет, но есть серьёзные подозрения, что имеется некоторое количество физических явлений, в которых характеристики естественным образом выражаются вещественными числами. Да, есть вещи, которые только кажутся вещественными, но реально они дискретны (например, электрический заряд), но наверняка есть и такие, которые реально непрерывны. Например, насколько мне известно, направления в пространстве никак не дискретизируются. Энергия, похоже на то, что тоже (фотоны квантуются, и пока фотон жив, о его энергии с абсолютной точностью ничего утверждать нельзя, но когда он гибнет, он отдаёт порцию, выражаемую вещественным числом).
А что такое вещественное число, если его выразить в битах? Это строго бесконечное разнообразие. Которое везде. Которое есть естественное состояние нашего мира. И в микро, и в макро. Целый океан бесконечных разнообразий, и мы естественным образом сами являемся его бесконечно разнообразными частями. И ничего ведь, что интересно, ни в какие чёрные дыры не коллапсирует. Как так получается? Тут определённо есть над чем подумать…
maslyaev
04.11.2016 17:03-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 комментов.
Дело тут в том, что все мы прекрасно знаем, что такое информация. В конце концов, это одно из самых базовых и практически повсеместно используемых понятий. Но это знание у нас имплицитное. А для того, чтобы об этом предмете продуктивно рассуждать, нужно сделать это знание эксплицитным. А для этого нужно выработать адекватный понятийный аппарат. Аккуратно отделить мух от котлет. Пока это не сделано (а это действительно пока что не сделано), у нас при любых попытках обсуждения будет дикая путаница. То котлеты, ползающие по потолку, то поджаристые мухи с корочкой :)
miksoft
maslyaev
А почему высота барьерчиков в четырёхстабильной яме должна быть другой? Высота барьерчика должна быть ровно такая, чтобы исключить самопроизвольное перескакивание шарика, и поэтому определяется только температурой, но никак не количеством ямок.