Трёхадресная учебная машина

Трёхадресная архитектура — наиболее «естественная» (операнд × операнд → результат),

Использование констант

Перепишем пример с дискриминантом таким образом, чтобы константа 4 хранилась в самой программе

.cpu mm-3
; a,b,c и d разместим по адресам 010a, 010b, 010c и 010d
.input 0x010a, 0x010b, 0x010c
.output 0x010d

.code
03 010b 010b 0100 ; b*b (умножение со знаком), результат в ячейке 0100
03 010a 010c 0101 ; a*c, результат в 0101
03 0101 0005 0101 ; ac*4, результат в 0101
02 0100 0101 010d ; b²-4ac
99 0000 0000 0000
00 0000 0000 0004 ; константа 4

.enter 5 8 3

• Ячейки УМ хранят просто числа, интерпретация этих чисел как команд или как чисел целиком зависит от хода программы

• Адрес ячейки, в которой хранится константа 4, пришлось высчитывать вручную — 0005

• В данной реализации эмулятора можно вставлять пробелы, а можно и не вставлять (зато нельзя сокращать количество 16-ричных знаков и использовать отрицательные числа)

Запуская программу, мы можем попросить эмулятор вводить данные не из директивы .enter, а со стандартного ввода (клавиатуры) или из заданного файла:

$ modelmachine run discr2.mmach --enter -
Ram[0x010a] = 7
Ram[0x010b] = 10
Ram[0x010c] = 3
Ram[0x010d] = 16

• Параметр --enter — это имя файла, из которого будут вводиться данные, если это имя — минус, то ввод пойдёт с клавиатуры

• Первые три строки — это ввод

То, что адрес нашей константы равен 0005, стало понятно только после написания программы. Если добавить в неё ещё каких-то вычислений (например, проверку отрицательности дискриминанта), адрес этот увеличится. Для удобства программирования некоторые архитектуры предполагают, что выполнение программы начинается не с самого первого адреса, а, например, с 0x100. Тогда у программиста остаётся 256 адресов для переменных, которые не будут изменяться, как бы он не двигал команды в программе.

Что будет, если забыть в конце программы поставить команду 99?

Слегка упростить себе жизнь можно, если указать директиве .code явный адрес. Здесь константа явно размещена по адресу x0102:

…
.code
03 010b 010b 0100 ; b*b (умножение со знаком), результат в ячейке 0100
03 010a 010c 0101 ; a*c, результат в 0101
03 0101 0102 0101 ; ac*4, результат в 0101
02 0100 0101 010d ; b²-4ac
99 0000 0000 0000
.code 0x0102
00 0000 0000 0004 ; константа 4
…

Команда перехода

Для реализации ветвления в архитектуре фон Неймана требуется как минимум два свойства

• Сравнение значений в ячейках памяти

• Вычисление адреса следующей выполняемой команды на основании результатов сравнения (условный переход)

Рассмотрим безусловный переход — команду 80, при выполнении которой в счётчик команд записывается поле РЕЗ. Напишем программу сложения двух констант, которые будут находится по фиксированным адресам 1 и 2, а в ячейке 0 будет переход по адресу 3.

.cpu mm-3
.output 0x0001
.code
80 0000 0000 0003 ; безусловынй переход на 3
00 0000 0001 47ad ; первая константа
ff ffff ffff fff3 ; вторая константа
01 0001 0002 0001 ; сумма
99 0000 0000 0000

Выполним программ пошагово

$ modelmachine debug jump.mmach
Welcome to interactive debug mode
Legend:
  0x0000:         address in ram
  00000000000000  filled memory cell
  00000000000000  next command
  00000000000000  updated by last command
  00000000000000  dirty unused memory
  00000000000000  breakpoint

Cycle:    0 | RAM access count:    0 words | Next opcode: jump

0x0000: 80000000000003 000000000147ad fffffffffffff3 01000100020001
0x0004: 99000000000000 00000000000000 00000000000000 00000000000000

  PC               0x0000
  IR     0x00000000000000
  ADDR             0x0000
  S      0x00000000000000
  FLAGS  0x00000000000000
  R1     0x00000000000000
  R2     0x00000000000000

Enter
  step [count=1]        make count of steps
  continue              continue until breakpoint or halt
  breakpoint [addr]     set/unset breakpoint at addr
  memory <begin> <end>  view random access memory
  rstep [count=1]       make count of steps in reverse direction
  rcontinue             continue until breakpoint or cycle=0 in reverse direction
  quit

> s
Cycle:    1 | RAM access count:    1 words | Next opcode: add

0x0000: 80000000000003 000000000147ad fffffffffffff3 01000100020001
0x0004: 99000000000000 00000000000000 00000000000000 00000000000000

  PC               0x0003
  IR     0x80000000000003
  ADDR             0x0003
  S      0x00000000000000
  FLAGS  0x00000000000000
  R1     0x00000000000000
  R2     0x00000000000000
>
Cycle:    2 | RAM access count:    5 words | Next opcode: halt

0x0000: 80000000000003 000000000147a0 fffffffffffff3 01000100020001
0x0004: 99000000000000 00000000000000 00000000000000 00000000000000

  PC               0x0004
  IR     0x01000100020001
  ADDR             0x0003
  S      0x000000000147a0
  FLAGS  0x00000000000001
  R1     0x000000000147ad
  R2     0xfffffffffffff3
>
machine halted
Cycle:    3 | RAM access count:    6 words | Next opcode: move

0x0000: 80000000000003 000000000147a0 fffffffffffff3 01000100020001
0x0004: 99000000000000 00000000000000 00000000000000 00000000000000

  PC               0x0005
  IR     0x99000000000000
  ADDR             0x0003
  S      0x000000000147a0
  FLAGS  0x00000000000010
  R1     0x000000000147ad
  R2     0xfffffffffffff3

Итак, команда 80 0000 0000 0003 записала в СА (PC) значение 3, в результате чего содержимое ячеек 0001 и 0002 не выполнялось как команды

Условный переход

Команда условного перехода в трёхадресной УМ включает в себя и проверку условия, и переход. Общая схема:

• Сравнить содержимое ОП1 с содержимым ОП2
• Если сравнение истинно, записать в СА значение РЕЗ, иначе ничего не делать

Пример:

.cpu mm-3

.input 0x100, 0x101
.output 0x100

.code
83 0100 0101 0002  ; 0 если содержимое 0100 меньше содержимого 0101, перейти на 2
99 0000 0000 0000  ; 1 в 0100 и так лежит максимум
00 0101 0000 0100  ; 2 переложить максимум в 0100
99 0000 0000 0000  ; 3

.enter 12 21

• Когда редактирушь уже написанную, прогармму то и дело приходится вставлять или удалять команды — отчего «плывут» практически все заданные адреса, как переменных, так и переходов. Для (чуть большего) удобства будем вручную расставлять эти адреса в комментариях — тогда хотя бы не придётся каждый раз считать, куда «переехала» ячейка после редактирования.

Вообще говоря, сравнений достаточно двух — на равенство и на больше, остальные моделируются. Например, проверка на A<B — это суперпозиция проверки B>A и B==A

Заметим, что для знаковых и беззнаковых целых алгоритм сравнения на больше (стало быть, и остальные три вида сравнений) отличается, следовательно, надо предусмотреть различные коды операций. Для удобства в УМ3 добавлены и остальные виды сравнений.

Как всегда, знаковые (s-) и беззнаковые (u-) версии сравнений в УМ отличаются значением четвёртого бита в поле КОП.

Пример: : Ввести два числа, вывести 1, если первое делится на второе, и 0, если не делится. Для удобства адреса ячеек указаны в комментариях, а вот со значением команд предлагается разобраться самостоятельно (напоминаем, что команда деления 04 заполняет две ячейки — частным и остатком)

.cpu mm-3

.input 0x100, 0x101
.output 0x104

.code
04 0100 0101 0102; 0
81 0103 0006 0004; 1
00 0006 0000 0104; 2
99 0000 0000 0000; 3
00 0007 0000 0104; 4
99 0000 0000 0000; 5
00000000000000; 6 =0
00000000000001; 7 =1

.enter 10 3

Кстати, если вы запускаете modelmachine из командной строки Bash или Zsh, можно воспользоваться вот такой конструкцией для того, чтобы задать ввод:

$ mm run divid.mmach --enter - <<<"12 3"
Ram[0x0104] = 1
$ mm run divid.mmach --enter - <<<"172 3"
Ram[0x0104] = 0

• Здесь эмулятору говорят, что ввод будет со стандартного ввода, а командной строке — что на стандартный ввод надо подать строку "12 3" или "172 3", а клавиатуру не задействовать.

Более сложный пример: ввести три числа, вывести максимум

.cpu mm-3

.input 0x100, 0x101, 0x102
.output 0x103

.code
86 0100 0101 0006 ; 0 sjg 100 101 6
86 0102 0101 0004 ; 1 sjg 102 101 4
00 0101 0000 0103 ; 2 mov 101 103
99 0000 0000 0000 ; 3
00 0102 0000 0103 ; 4 mov 102 103
99 0000 0000 0000 ; 5
86 0100 0102 0009 ; 6 sjg 100 102 9
00 0102 0000 0103 ; 7 mov 102 103
99 0000 0000 0000 ; 8
00 0100 0000 0103 ; 9 mov 100 103
99 0000 0000 0000 ; A

.enter 123 1234 456

в приведённом коде есть повторяющиеся инструкции. Можно ли как-то сократить его?

Цикл

Циклы в архитектуре фон Неймана — это просто переходы назад — по адресу, выполнение программы с которого может привести снова к тому же самому переходу.

Пример: ввести число, вывести его факториал

.cpu mm-3

.input 0x6
.output 0x7

.code
00 0005 0000 0007 ; 0 move 1 R
03 0007 0006 0007 ; 1 smul R N =: R
02 0006 0005 0006 ; 2 sub N 1 =: N
86 0006 0005 0001 ; 3 N > 1 -> 0001
99 0000 0000 0000 ; 4 halt
00 0000 0000 0001 ; 5 =1
                  ; 6 N
                  ; 7 R
.enter 6

Цикл образуется за счёт операции сравнения на «больше» 86 с переходом по адресу 01 в случае успешного сравнения. Цикл заканчивается, т. к. сравниваемая ячейка 6 уменьшается при каждом обороте цикла.

Для краткости программы мы использовали т. н. «цикл с пост-условием», в котором сначала вычисляется тело и изменение, а потом проверяется истинность сравнения. Особенность такого цикла — в том, что его тело обязательно выполняется хотя бы один раз. Чаще всего такое требование неактуально, и проверку условия надо ставить перед телом цикла. Тогда условный переход будет вперёд (за пределы цикла), а переход на начало цикла будет безусловным.

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

• Инициализация
• Проверка условия
• Тело
• Изменение данных условия В архитектуре фон Неймана добавляется пятый шаг — переход на начало цикла:
• Присваивание начальных значений
• Проверка условия окончания цикла и переход на окончание цикла при успехе
• Тело
• Изменение ячеек, участвующих в проверке условия
• Безусловный переход на шаг 2

.cpu mm-3

.input 0x100
.output 0x101

.code
00 0103 0000 0101 ; 0 move 1 R
00 0100 0000 0102 ; 1 move N M
85 0102 0103 0006 ; 2 M ⩽ 1 -> halt
03 0101 0102 0101 ; 3 smul R M =: R
02 0102 0103 0102 ; 4 sub M 1 =: M
80 0000 0000 0002 ; 5 -> ⩽
99 0000 0000 0000 ; 6 halt

.code 0x100
00000000000000    ; 0 N
00000000000000    ; 1 R
00000000000000    ; 2 M
00000000000001    ; 3 1

.enter 6

• Здесь мы применили уже знакомый приём «переменные в отдельном фрагменте кода»

Пример: ввести два числа A и B, вывести сумму квадратов A²+(A+1)²+…+B²

.cpu mm-3

.input 0x100, 0x101
.output 0x102

.code
00 0105 0000 0102 ; 0 move 0 S
00 0100 0000 0103 ; 1 move A I
86 0103 0101 0007 ; 2 I > B -> 0007
03 0103 0103 0104 ; 3 mul I I -> Q
01 0104 0102 0102 ; 4 add Q S -> S
01 0106 0103 0103 ; 5 add 1 I -> I
80 0000 0000 0002 ; 6 -> 0002
99 0000 0000 0000 ; 7

.code 0x0100
00000000000000    ; 0 A
00000000000000    ; 1 B
00000000000000    ; 2 S
00000000000000    ; 3 I
00000000000000    ; 4 Q
00000000000000    ; 5 0
00000000000001    ; 6 1

.enter 3 10

Для чего нужна самая первая команда (по адресу 0)?