Синтаксическая модель обратимого вычислителя и его язык ассемблера

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:25, 18 декабря 2017.
Open book.svg Авторство
А. С. Сосенко
Согласовано: 18 декабря 2017 года

Введение

В соответствии с принципом Ландауэра[Источник 1] в любой вычислительной системе, независимо от её физической реализации, при потере 1 бита информации выделяется определенное количество теплоты. Этот принцип находит экспериментальное подтверждение[Источник 2]. Остро встает вопрос о принципиально новом подходе к выполнению вычислений и построению вычислительных систем. Таким подходом может стать использование вычислителей, реализующих обратимые вычисления[Источник 3].

На данный момент описано множество высокоуровневых обратимых языков программирования[Источник 3]. Но вопросы, связанные с изучением устройства самих обратимых вычислителей и низкоуровневых языков для них – языков ассемблера, раскрыты хуже. Поэтому в данной статье было принято решение описать собственную модель обратимого вычислителя и его язык ассемблера. Данную информацию можно будет использовать в дальнейших работах по исследованию возможностей улучшения конструкций обратимых вычислителей и оптимизации обратимых языков программирования. Особый интерес представляет изучение особенностей обратимых языков программирования в вопросах обеспечения информационной безопасности вычислений – отказоустойчивость вычислений, сохранение целостности информации при возникновении ошибок.

Синтаксическая модель обратимого вычислителя

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

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

Служебных регистров (PC – Program Counter – регистр, содержащий адрес инструкции, которая выполнится следующей; PS – Program State – регистр состояния программы, содержит флаги) не будет по крайней мере в первой версии модели вычислителя, т.к. элегантно организовать обратимые операции над ними – сложная задача.

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

Язык ассемблера обратимого вычислителя

Начальная версия языка ассемблера обратимого вычислителя поддерживает следующие операции:

NOP
NOT
XOR
CXOR
CCXOR

Далее рассмотрим каждую из операций подробнее. Для каждой операции будем давать эквивалентное описание на псевдокоде (микрокод операции). Операнды операции обозначаются . Если в качестве операнда используется адрес в памяти, то подразумевается работа со значением по этому адресу. Если в качестве операнда используется константа, то подразумевается работа напрямую со значением константы.

NOP

NOP – незначащая операция. Может быть использована для создания задержек или синхронизации исполнения.

NOT

NOT op1 – выполняет отрицание операнда op1 и записывает результат в op1. Возможен один вариант данной операции, когда в качестве op1 выступает адрес в памяти данных:

NOT m1

Микрокод операции:

op1 ~= op1

XOR

XOR op1, op2 – выполняет операцию исключающего ИЛИ над операндами op1 и op2, результат записывает в op1. Возможно три варианта данной операции. В качестве op1 может выступать только адрес в памяти данных, а в качестве op2 – адрес в программной памяти или памяти данных, или константа:

XOR m1, p1
XOR m1, m2
XOR m1, c1

Микрокод операции:

op1 ^= op2

CXOR

CXOR op1, op2, op3 – выполняет операцию XOR op2, op3, если op1 равен нулю, иначе выполняет операцию NOP. Возможно три варианта данной операции. В качестве op1 и op3 может выступать только адрес в памяти данных, а в качестве op2 – адрес в программной памяти или памяти данных, или константа. При этом op2 не должен быть равен op1:

CXOR m1, m2, p1
CXOR m1, m2, m3
CXOR m1, m2, c1

Микрокод операции:

if op1 == 0:
    op2 ^= op3
else:
    nop

CCXOR

CCXOR op1, op2, op3, op4 – выполняет операцию XOR op3, op4, если результат выполнения операции логического И над операндами op1 и op2 равен нулю, иначе выполняет операцию NOP. Возможно девять вариантов данной операции. В качестве op1 и op3 может выступать только адрес в памяти данных, а в качестве op2 и op4 – адрес в программной памяти или памяти данных, или константа. При этом op3 не должен быть равен op1 или op2:

CCXOR m1, p1, m2, p2
CCXOR m1, p1, m2, m3
CCXOR m1, p1, m2, c1
CCXOR m1, m2, m3, p1
CCXOR m1, m2, m3, m4
CCXOR m1, m2, m3, c1
CCXOR m1, c1, m2, p1
CCXOR m1, c1, m2, m3
CCXOR m1, c1, m2, c2

Микрокод операции:

if op1 & op2 == 0:
    op3 ^= op4
else:
    nop

Обратимость программ

Для того чтобы показать, что любую из программ, написанных на данном языке можно обратить, покажем, что можно обратить любую из операций этого языка. Очевидно, что операции NOP и NOT являются обратными для самих себя. Операция XOR также является обратной для самой себя, т.к. в ходе ее выполнения изменяется только значение op1, а значение op2 не изменяется. Операции CXOR и CCXOR являются обратными для самих себя, т.к. их выполнение сводится к обратимым операциям XOR и NOP и в ходе их выполнения не изменяются операнды, отвечающие за условие (op1 и op1, op2 соответственно).

Функциональная полнота

Предложенный язык ассемблера является функционально полным, т.к. с его помощью можно смоделировать работу любой обратимой схемы[Источник 3]. При этом в качестве линий будут выступать ячейки памяти данных, а работу элементов NOT, CNOT и CCNOT можно смоделировать при помощи элементов NOT, CXOR и CCXOR соответственно.

Источники

  1. Landauer R. Irreversibility and heat generation in the computing process // IBM Journal of Research and Development, Vol. 5, 1961. pp. 183–191.
  2. Bérut.A. Experimental verification of Landauer’s principle linking information and thermodynamics // Nature, 2012. pp. 187-189.
  3. 3,0 3,1 3,2 Perumalla K.S. Introduction to Reversible Computing. CRC Press, 2014. 320 p.