• Читаемое за неделю
  • Последние ответы
  • Новые темы

Авторская Обратимые вычисления: технология и применение

Talomir

Местный
Местный

Talomir

Местный
Местный
Статус
Offline
Регистрация
20 Мар 2021
Сообщения
7
Реакции
138
ОБРАТИМЫЕ ВЫЧИСЛЕНИЯ: ТЕХНОЛОГИЯ И ПРИМЕНЕНИЕ



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

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

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

Именно из-за потерь энергии на трение, шарик не отскакивает на ту-же самую высоту, с которой он брошен. Ведь энергия шарика U = mgh, где U - потенциальная энергия, m - масса шарика, g - гравитационная постоянная, h - высота, с которой мячик отпущен. Если есть потери энергии, мячик не возвращается в начальное состояние. Тогда, если мячик возвращается в начальное состояние, то - нет потерь энергии! Этот физический принцип, возврат к начальному состоянию, можно применить и к вычислениям. Такие вычисления принято называть обратимыми, так как они проводятся в две стороны: слева-направо, от входов - к выходам, и справа-налево, от выходов к входам, обратно.

Обратимая электрическая схема слева имеет несколько входных линий, а справа - несколько выходных линий. На каждой линии сигнал может иметь логический уровень 0 или 1. При прямых вычислениях на входах устанавливаются начальные значения, и схема вырабатывает выходные значения на выходных линиях - выходы. При обратных вычислениях на выходных линиях устанавливаются выходные значения, и схема, уже справа-налево, вырабатывает на входные линии начальные входные значения. Это - обратная работа схемы.

При обратимой схеме, при тех-же выходах, на входе получаются те-же начальные значения, схема возвращается в начальное состояние, и информация - не стирается, что приводит к энерго-сберегающему режиму вычислений, который называется адиабатическими вычисления. Слово адиабатический тут обозначает 'без рассеивания тепла'. Уже существуют адиабатические, обратимые процессоры, которые производят вычисления почти без рассеивания энергии. Например, один из первых полностью-адиабатических процессоров Pendulum, или - адиабатический процессор VMM, изображённый на фотографии ниже



ЛОГИЧЕСКИ-ОБРАТИМЫЕ ВЫЧИСЛЕНИЯ

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

Такая задача, счёт функции от результата к аргументам, возникает при майнинге биткоинов, когда программный CPU майнер соперничает по скорости криптодобычи с аппаратными ASIC - майнерами. Алгоритм добычи биткоина состоит в двойном вычислении хэш-функции SHA256 от заголовка из байтов, склеенного с 4-байтовым числом nonce. Если при пробуемом nonce хэш-значение получается меньше некоторого числа, называемого текущей сложностью, то говорят, что найдена 'шара', и майнер получает денежную премию.

Вместо полного перебора всех чисел nonce и подсчёта хэш-функций от них, можно пойти другим путём. А именно - провести вычисления снизу вверх, от небольшого числа, меньше сложности, на выходе, до числа nonce на входе. А это - как раз те самые обратимые вычисления! При этом, точное восстановление nonce оказывается невозможным, так как невозможно задать фиксированные байты заголовка блока на входе, однако в троичной логике и обратимых вычислениях на них можно восстановить несколько битов числа nonce и, этим самым, сократить полный перебор числа nonce. Так, если известен один бит nonce, то это сокращает перебор в два раза - майнинг ускоряется вдвое. Если известны два бита, то это сокращает перебор в 4 раза. Если известны 3 бита, то сокращение перебора - 8 раз. А если удалось восстановить 4 бита, то это сокращает перебор и ускоряет майнинг в 16 раз! То есть, CPU майнинг можно ускорить в 16 раз на обычном процессоре Intel и конкурировать по скорости с ASIC - майнерами с ноутбука, написав несложный забор заданий у пула в строках JSON протокола Stratum.

Итак, логически-обратимые вычисления это прямые и обратные вычисления на программном уровне, прямое и обратное выполнение программ. Программы, в конечном итоге, переводятся в ассемблер, или - же, изначально на нём пишутся. И для обратимых вычислений достаточно иметь обратимый ассемблер. То есть такой ассемблер, который можно выполнять и сверху-вниз, и снизу - вверх. Сложность проектирования обратимого RISC ассемблера (RISC - Redused Command Set, сокращённый набор инструкций) - два месяца расчётов на двух пачках бумаги по 500 листов А4 в каждой! Эту проблему помогает решить троичная логика и двухадресный код.

ТРОИЧНАЯ ЛОГИКА

Обычная, двоичная логика, имеет два значения истинности: 0 и 1. Её проблема заключается в том, что по выходу 0 или 1 нельзя точно восстановить два аргумента логической функции, такой как AND и OR - двоичная логика не обратима.

Однако, если добавить третье значение истинности, -1, например означающее "не знаю", кроме 0 (нет) и 1 (да), и правильно задать таблицы истинности, таблицы результатов функций NOT, AND, OR, XOR, для всех значений аргументов, то можно получить обратимую троичную логику: для любого выхода логического вентиля можно однозначно указать входы, дающие этот выход, по построению. Такие логические функции оказываются обратимыми, и на них можно реализовать вначале побитовую обратимую арифметику, а затем - обратимый ассемблер. Например, имея обратимую логику, строится обратимый сумматор - обратимая функция побитового сложения чисел. А потом - обратимое умножение, деление, вычитание. Всё это требует тщательной работы с бумагой и ручкой и знания компьютерной схемотехники и математики.

ДВУХАДРЕСНЫЙ КОД

Двухадресный код тоже находит применения в логически-обратимый вычислениях. Прежде всего, напомним читателям, что такое трёхадресный код, на котором основаны почти все ассемблеры.

Для инструкции a = b + c ассемблер с трёхадресным кодом имеет запись команды ADD B, C, A. B тут называется регистром - источником, C называется регистровым аргументом, А называется регистром-приёмником. Такой код очень сложен для обращения, из-за сложных уравнений, получающихся при проектировании обратных инструкций. Вместо него проще использовать двухадресный код.

Вместо a = b + c можно записать:

a = b
a += c

Тогда обратным кодом для этого двухадресного будет:

a -= c

И так, можно сделать для всех арифметических инструкций:

Прямо
a += b
Обратно
a -= b

Прямо
a -= b
Обратно
a += b

Прямо
a *= b
Обратно
a /= b

Прямо
a /= b
Обратно
a *= b

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

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



ССЫЛКИ

- мой второй сайт по обратимым вычислениям

Э - мой первый сайт по обратимым вычислениям
 

Talomir

Местный
Местный

Talomir

Местный
Местный
Статус
Offline
Регистрация
20 Мар 2021
Сообщения
7
Реакции
138
И, вот ещё аналитическая записка проекта BLACK, важная для статьи выше:
 
Последнее редактирование:

Сверху