modelmachine

Model machine emulator

TODO

• Проверить test.alu.swap
• Работа с плавающей запятой
• Подумать еще о mock в тестах
• Переделать документацию модулей
• Исправить опечатки в документации
• Расширить howto

Модельная машина

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

Quickstart

Установка пакета происходит командой:

# python3 -m pip install --upgrade modelmachine

После этого вам становится доступна консольная команда modelmachine. Для проверки вы можете сделать modelmachine test. Будет выполнена серия тестов, все тесты должны закончиться успехом.

Посмотрите примеры в папке , по их образу можно начинать писать программы для модельных машин. Запуск программы делается командой:

$ modelmachine run program.mmach

Также доступна пошаговая отладка командой:

$ modelmachine debug program.mmach

Поддерживается компилирование ассемблера модельной машины (mmasm) в ее машинный код.

$ modelmachine asmg source.mmasm result.mmach

Пример

mm3

[config]
input = 0x100,0x101
output = 0x103

[code]
; x = ((a * -21) % 50 - b) ** 2 == 178929
03 0100 0005 0103 ; x := a * -21
04 0103 0006 0102 ; [0102] := x / 50, x := x % 50
02 0103 0101 0103 ; x := x - b
03 0103 0103 0103 ; x := x * x
99 0000 0000 0000 ; halt
; ---------------------
FFFFFFFFFFFFEB ; -21
00000000000032 ; 50

[input]
-123 456

• Все, что идет после символа ; - комментарий.
• Первая строчка - обязательное название архитектуры. Список поддерживаемых архитектур смотри ниже.
• После этого должна идти секция config, описывающая ячейки памяти, по которым нужно производить ввод и вывод.
• После этого секция кода, содержащая набор 16-ричных чисел, записываемых в память модельной машины. Пропускать часть машинного слова нельзя. Рекомендуется писать по одному машинному слову в строке, по желанию разбивая разряды на части пробелами.
• Пустые строки игнорируются.
• После этого идет секция ввода - несколько чисел, разделенных пробельными символами. Их число должно совпадать с числом ячеек для ввода в параметре input в секции config.
• Если секция ввода отсутствует или если она пустая, то входные данные читаются со стандартного потока ввода до исполнения программы.
• По окончании работы на экран будут напечатаны десятичные числа со знаком, лежащие в ячейках, перечисленных в параметре output в секции config.

Язык ассемблера

Для машины с модификаией адресов поддерживается ассемблер. Ассемблер нечувствителен к регистру. Команды компилятору предворяются точкой. Доступные команды компилятора:

• .config число - дальнейшие команды и данные располагать начиная с адреса число.
• .code - дальше идет исходный код, который нужно располагать начиная с адреса 0x00.
• .word список_чисел - разместить список чисел в памяти как есть, каждое число занимает пару ячеек.
• .dump имя_метки - по завершении работы программы вывести содержимое памяти по адресу имя_метки, команда выводит содержимое двух ячеек как одно число. Для вывода массива фиксированного размера используйте формат .dump имя_метки(размер). Также метки для вывода можно перечислять через запятую. Например: .dump array(5), sum

Коды команд те же, что и в таблице кодов mmm. Имя метки - последовательность английских букв, цифр и знака _, первый символ последовательности - не цифра. Адрес представляет собой либо имя метки, либо строку вида имя_метки(имя_регистра), где имя_регистра - одно из значений R0-RF.

Ввод данных не поддерживается.

.config 0x100
sum: .word 0
array: .word -1, 2, 3, 4, 5
zero: .word 0
size_word: .word 2
size_array: .word 10
.dump array(5), sum
.code
load R2, size_word
load RF, size_array
load R5, zero
rsub R6, R6
rpt: add R5, array(R6)
radd R6, R2
rcomp R6, RF
jneq rpt
store R5, sum
halt

Внутреннее устройство

Данная реализация модельной машины состоит из классов, разбитых на файлы-модули:

• memory.py - память; делится на два класса: регистровая и оперативная; оперативная делится на little-endian и big-endian
• numeric.py - целочисленная арифметика с фиксированным числом двоичных знаков
• alu.py - арифметико-логическое устройство, работает с четко специализированными регистрами: R1, R2, S, FLAGS и PC.
• cu.py - контролирующее устройство, выполняющее считывание команд из памяти и запускающее необходимые методы в арифметико-логическом устройстве
• io.py - устройство ввода-вывода
• cpu.py - финальное объединение составляющих устройств в единое целое
• asm.py - ассемблер для машины с модификацией адресов

Здесь дано поверхностное описание модулей. За более подробным обращайтесь к документации конкретных модулей и их исходным кодам.

memory.py

AbstractMemory - класс абстрактной памяти, предоставляющий интерфейс для надежной связи частей компьютера. Основные методы: fetch и put, которые принимают на вход адрес в памяти и количество битов, с которыми нужно работать, количество должно быть кратно размеру ячейки (слова). Строго рекомендуется их использовать везде.

RandomAccessMemory - класс, реализующий память прямого доступа. При инициализации указывается размер машинного слова и количество этих слов. Если is_protected=True, то при попытке считывания из неинициализированной ячейки будет выброшено исключение, иначе, метод fetch вернет нуль.

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

numeric.py

Класс Integer реализует целочисленную арифметику фиксированной длины. Поддерживаемые операторы: +, -, *, /, %, ==, !=. Плюс методы get_value и get_data. Округление при делении производится в сторону нуля.

alu.py

Арифметико-логическое устройство работает с четко специализированными регистрами:

• R1, R2, S для арифметических операций.
• FLAGS для хранения флагов состояния.
• PC только для пересылки туда адреса из регистра R1 при условных переходах.

Схема работы:

• Арифметические команды: add, sub, smul, sdiv, umul, udiv, sdivmod, udivmod. За исключением команд divmod арифметические команды работают следующим образом: S := R1 op R2. Плюс в зависимости от результата выставляется регистр FLAGS - комбинация флагов CF, OF, SF и ZF.
• add и sub - сложение и вычитание соответсвенно.
• smul и sdiv - знаковое умножение и деление соответсвенно.
• umul и udiv - беззнаковое умножение и деление соответсвенно.
• sdivmod и udivmod - знаковое и беззнаковое соответственно деление с остатком. S := R1 / R2; R1 := R1 % R2.
• Команда пересылки move: S := R1.
• Команды безусловного перехода jump и условного перехода cond_jump работают по схеме PC := R1, режим работы cond_jump зависит от того, какие дополнительные аргументы будут переданы.
• Команда останова halt просто выставляет флаг остановки HALT в регистре флагов

cu.py

Управляющее устройство.

AbstractControlUnit

Обычно управляющее устройство работает по схеме:

1. fetch_and_decode - загрузка и расшифровка очередной команды. Содержимое ячейки оперативной памяти с адресом записанным в регистре PC загружается в регистр RI, затем из него извлекается код операции и адреса операндов, затем счетчик PC увеличивается на длину только что считанной команды.
2. load - данные по только что считанным адресам загружаются в регистры процессора R1 и R2
3. execute - в зависимости от кода операции в арифметико-логическом устройстве запускается та или иная схема вычислений.
4. write_back - результат вычислений записывается куда полагается (например, по одному из адресов считанных в начале).

Все эти методы поддерживаются в AbstractControlUnit. Также в нем написаны использующие их методы, являющиеся интерфейсом устройства управления:

• step - сделать один шаг, описанный алгоритмом выше.
• get_status - вернуть статус процессора (выполняется/остановлен). Остановка производится командой останова halt.
• run - выполнять один шаг за другим, пока процессор не будет остановлен.

Далее, наследники AbstractControlUnit определяют первые 4 метода.

io.py

Устройство ввода-вывода.

• При инициализации устанавливается адрес с которого нужно загружать программы пользователя.
• Метод load_source загружает последовательность шеснадцатиричных слов по указанному адресу.
• Метод load_data загружает данные (полученные из строки чисел) по данным адресам.
• Методы get_int и put_int работают с содержимым одного слова. Размер слова устанавливается при инициализации.

cpu.py

Финальная сборка всех составных устройств в единое целое.

• Поддерживается доступ к составным устройствам. Например, доступ к устройству ввода/вывода можно получить через cpu.io_unit, к регистрам через cpu.registers и так далее.
• load_program - загрузка программы, конфигурации и данных в оперативную память.
• print_result - печать результата работы программы.
• run_file - загрузка, исполнение и печать результата.

Поддерживаемые архитектуры

Как добавить новую архитектуру?

1. Выписать все команды устройстройства и их коды.
2. Добавить их в таблицу ниже и описание еще ниже.
3. Добавить новый класс устройства управления на основе существующего.
4. Добавить новый класс CPU использующий это устройство управления, добавить этот класс в список CPU_LIST в файле cpu.py.
5. Добавить тесты для обоих этих классов в файлы tests/test_cu.py и tests/test_cpu.py.
6. Добавить примеры в папку samples.
7. Прислать pull request.

Таблица команд модельных машин

На самом деле операция div запускает в АЛУ схему divmod.

Ниже дана таблица команд условных переходов. Откуда берутся операнды для сравнения зависит от архитектуры модельной машины. Подробнее смотри [1].

mm-3

Архитектура трехадресной модельной машины.

• Размер ячейки оперативной памяти: 7 байт.
• Размер адреса: 2 байта.
• Арифметические вычисления производятся с одной ячейкой оперативной памяти.
• Код команды помещается в одну ячейку оперативной памяти КОП А1 А2 А3.
• Регистры: S, R1, R2, FLAGS, PC, RI, ADDR.

Назначение регистров:

• S - регистр сумматор, в него записывается результат арифметической операции.
• R1, R2 - регистры операндов арифметических операций.
• FLAGS - регистр флагов.
• PC - регистр указатель инструкции.
• RI - регистр для хранения инструкции.
• ADDR - регистр для хранения адреса для инструкции перехода.

Действия процессора для арифметических инструкций (add, sub, smul, sdiv, umul, udiv) КОП A1 A2 A3:

1. Загрузить содержимое ячейки оперативной памяти с адресом А1 в регистр R1 (R1 := [A1]).
2. Загрузить содержимое ячейки оперативной памяти с адресом А2 в регистр R2 (R2 := [A2]).
3. Запустить в АЛУ схему, реализующую операцию, задаваемую КОП.

4. Записать результат из регистра S в ячейку оперативной памяти с адресом А3. Если выполняется операция деления, в оперативную память записываются два результата: частное – в ячейку с адресом А3, остаток – в следующую ячейку, по адресу (А3+1) mod 16^4.

• jump A1 A2 A3: PC := A3
• Условные переходы: сравниваются R1 и R2, в зависимости от результата происходит PC := A3.
• Команда пересылки move: [A3] := R1.

mm-2

Архитектура двухадресной модельной машины.

• Размер ячейки оперативной памяти: 5 байт.
• Размер адреса: 2 байта.
• Арифметические вычисления производятся с одной ячейкой оперативной памяти.
• Код команды помещается в одну ячейку оперативной памяти КОП А1 А2.
• Регистры: R1, R2, FLAGS, PC, RI, ADDR.

Действия для арифметических команд add, sub, smul, sdiv, umul, udiv:

1. R1 := [A1], R2 := [A2]
2. R1 := R1 op R2
3. [A1] := R1

Действия для команды сравнения cmp:

1. R1 := [A1], R2 := [A2]

2. Запустить в АЛУ схему sub, выставить регистр FLAGS

• jump A1 A2: PC := A2
• Условные переходы делаются исходя из регистра FLAGS
• move A1 A2: [A1] := [A2]
• Команда останова halt взводит флаг HALT в регистре FLAGS

mm-v

Архитектура модельной машины с переменным (variable) фарматом команд.

• Размер ячейки оперативной памяти: 1 байт.
• Размер адреса: 2 байта.
• Арифметические вычисления производятся со словами в 5 ячеек оперативной памяти.
• Код команды занимает разное количество ячеек в зависимости от выполняемой операции.
• Регистры: R1, R2, FLAGS, PC, RI, ADDR.

Таблица кодов команд:

Действия для арифметических команд add, sub, smul, sdiv, umul, udiv:

1. R1 := [A1], R2 := [A2]
2. R1 := R1 op R2
3. [A1] := S

Действия для команды сравнения cmp:

1. R1 := [A1], R2 := [A2]

2. Запустить в АЛУ схему sub, выставить регистр FLAGS

• jump A1: PC := A1
• Условные переходы делаются исходя из регистра FLAGS
• move A1 A2: [A1] := [A2]
• Команда останова halt взводит флаг HALT в регистре FLAGS

mm-1

Архитектура одноадресной модельной машины.

• Размер ячейки оперативной памяти: 3 байта.
• Размер адреса: 2 байта.
• Арифметические вычисления производятся с одной ячейкой оперативной памяти.
• Код команды помещается в одну ячейку оперативной памяти КОП А.
• Регистры: S, R, S1, FLAGS, PC, RI.

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

Действия для арифметических команд (исключая деление) add, sub, smul, umul:

1. R := [A]
2. S := S op R

Действия для команд деления sdivmod, udivmod:

1. R := [A]
2. S := S / R; S1 := S % R

Действия для команды сравнения cmp:

1. R := [A]

2. Запустить в АЛУ схему sub, выставить регистр FLAGS

• jump A: PC := A
• Условные переходы делаются исходя из регистра FLAGS
• load A: S := [A]
• store A: [A] := S
• swap: S, S1 := S1, S
• Команда останова halt взводит флаг HALT в регистре FLAGS

mm-m

Архитектура модельной машины с модификацией адресов (modification).

• Размер ячейки оперативной памяти: 2 байта.
• Размер адреса: 2 байта.
• Арифметические вычисления производятся со словом в 4 байта.
• Код команды занимает разное количество ячеек в зависимости от выполняемой операции. Арифметические команды имеют формы регистр-регистр и регистр-память. Команды регистр-регистр имеют формат КОП RA1 RA2 и занимают 2 байта. Команды регистр-память имеют формат КОП R M A и занимают 4 байта. Команды перехода имеют формат КОП 0 0 A и занимают 4 байта.
• Регистры: R0-RF, S, RZ, FLAGS, PC, RI.

Основное отличие этой машины от предыдущих - наличие адресуемых регистров общего назначения R0-RF, используемых для арифметических вычислений и адресации памяти. S, RZ - неадресуемые регистры для работы АЛУ.

Также адресация данных теперь производится таким алгоритмом:

1. Возьмем содержимое адресуемого регистра с номером M (от 0x0 до 0xF): [M]. Если номер регистра M равен нулю, значение [M] также равно нулю вне зависимости от содержимого регистра R0.
2. Добавим к нему адрес A (от 0x0000 до 0xFFFF): [M] + A.
3. Возьмем остаток от деления этого адреса на 2^16: ([M] + A) % 2^16.
4. Возьмем из ОЗУ данные по полученному адресу: [[M] + A].

Таблица кодов команд:

Действия для загрузки исполнительного адреса в регистр addr R M A:

1. S := [M] + A
2. R := S

Действия для арифметических команд регистр-память (исключая деление) add, sub, smul, umul (формат op R M A):

1. S, RZ := R, [[M] + A]
2. S := S op RZ
3. R := S

Действия для команд деления регистр-память sdivmod и udivmod (формат op R M A, R_next - регистр, следующий за регистром R):

1. S, RZ := S, [[M] + A]
2. S, RZ := S / RZ, S % RZ
3. R, R_next := S, RZ

Действия для команды сравнения comp R M A:

1. S, RZ := S, [[M] + A]
2. Запустить в АЛУ схему sub S RZ, выставить регистр FLAGS

Действия для команды загрузки load R M A:

1. R := [[M] + A]

Действия для команды выгрузки store R M A:

1. [[M] + A] := R

Действия для арифметических команд регистр-регистр (исключая деление) radd, rsub, rsmul, rumul (формат op RX RY):

1. S, RZ := RX, RY
2. S := S op RZ
3. RX := S

Действия для команд деления регистр-регистр rsdiv и rudiv (формат - op RX RY; RX_next - регистр, следующий за регистром RX, если RX = RF, то RX_next = R0):

1. S, RZ := RX, RY
2. S, RZ := S / RZ, S % RZ
3. RX, RX_next := S, RZ

Действия для команды сравнения rcomp RX RY:

1. S, RZ := RX, RY

2. Запустить в АЛУ схему sub S RZ, выставить регистр FLAGS

• jump 00 A: PC := A
• Условные переходы делаются исходя из регистра FLAGS
• Команда останова halt взводит флаг HALT в регистре FLAGS

References

1. E. А. Бордаченкова - "Модельные ЭВМ" http://al.cs.msu.su/files/ModComp.pdf
2. Е. А. Бордаченкова - "Архитектура ЭВМ. Учебные машины. Методическое пособие" http://al.cs.msu.su/files/bordachenkova.architecture.model.machines.2010.doc
3. В. Г. Баула - "Введение в архитектуру ЭВМ и системы программирования" http://arch.cs.msu.ru/Page2.htm
4. http://cmcmsu.no-ip.info/1course/um3.command.set.htm