Newer
Older
[](https://travis-ci.org/vslutov/modelmachine)
## Модельная машина
Модельная машина - это чистая архитектурная концепция, позволяющая понять
логику функционирования центральных процессоров. По своей структуре она близка
к компьютерам первого поколения. Подробнее читайте по ссылкам внизу.
## Quickstart
Установка пакета происходит командой:
# python3 -m pip install --upgrade modelmachine
После этого вам становится доступна консольная команда `modelmachine`.
Для проверки вы можете сделать `modelmachine test`. Будет выполнена
серия тестов, все тесты должны закончиться успехом.
Посмотрите примеры в папке <samples>, по их образу можно начинать писать
программы для модельных машин. Запуск программы делается командой:
$ modelmachine run program.mmach
Также доступна пошаговая отладка командой:
$ modelmachine debug program.mmach
Поддерживается компилирование ассемблера модельной машины (mmasm) в ее машинный
код.
$ modelmachine asmg source.mmasm result.mmach
[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
.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`.
считывание команд из памяти и запускающее необходимые методы в
арифметико-логическом устройстве
* `io.py` - устройство ввода-вывода
* `cpu.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` для арифметических операций.
* `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.
### Таблица команд модельных машин
|0x01 | add | add | add | add | add |
|0x02 | sub | sub | sub | sub | sub |
|0x03 |smul |smul |smul |smul | smul |
|0x04 |sdiv |sdiv |sdiv |sdiv | sdiv |
|0x05 | |comp |comp |comp | comp |
|0x13 |umul |umul |umul |umul | umul |
|0x14 |udiv |udiv |udiv |udiv | udiv |
|0x10 | | | |store|store |
|0x20 | | | |swap | move |
|0x21 | | | | | radd |
|0x22 | | | | | rsub |
|0x23 | | | | |rsmul |
|0x24 | | | | |rsdiv |
|0x25 | | | | |rcomp |
|0x33 | | | | |rumul |
|0x34 | | | | |rudiv |
|0x80 |jump |jump |jump |jump | jump |
|0x81 | jeq | jeq | jeq | jeq | jeq |
|0x82 |jneq |jneq |jneq |jneq | jneq |
|0x83 | sjl | sjl | sjl | sjl | sjl |
|0x84 |sjgeq|sjgeq|sjneq|sjgeq|sjgeq |
|0x85 |sjleq|sjleq|sjleq|sjleq|sjleq |
|0x86 | sjg | sjg | sjg | sjg | sjg |
|0x93 | ujl | ujl | ujl | ujl | ujl |
|0x94 |ujgeq|ujgeq|ujgeq|ujgeq|ujgeq |
|0x95 |ujleq|ujleq|ujleq|ujleq|ujleq |
|0x96 | ujg | ujg | ujg | ujg | ujg |
|0x99 |halt |halt |halt |halt | halt |
Ниже дана таблица команд условных переходов.
Откуда берутся операнды для сравнения зависит от архитектуры модельной
машины. Подробнее смотри *[1]*.
|:----------------|:--------------:|:--------------------------------|
|jeq | == |jump if equal |
|jneq | != |jump if not equal |
|sjl | < s |signed jump if less |
|sjgeq | >= s |signed jump if greater or equal |
|sjleq | <= s |signed jump if less or equal |
|sjg | > s |signed jump if greater |
|ujl | < u |unsigned jump if less |
|ujgeq | >= u |unsigned jump if greater or equal|
|ujleq | <= u |unsigned jump if less or equal |
|ujg | > u |unsigned jump if greater |
* Размер ячейки оперативной памяти: 7 байт.
* Размер адреса: 2 байта.
* Арифметические вычисления производятся с одной ячейкой оперативной памяти.
* Код команды помещается в одну ячейку оперативной памяти `КОП А1 А2 А3`.
Назначение регистров:
* `S` - регистр сумматор, в него записывается результат арифметической операции.
* `R1`, `R2` - регистры операндов арифметических операций.
* `FLAGS` - регистр флагов.
* `PC` - регистр указатель инструкции.
* `RI` - регистр для хранения инструкции.
* `ADDR` - регистр для хранения адреса для инструкции перехода.
Действия процессора для арифметических инструкций (`add`, `sub`,
`smul`, `sdiv`, `umul`, `udiv`) `КОП A1 A2 A3`:
1. Загрузить содержимое ячейки оперативной памяти с адресом `А1` в
2. Загрузить содержимое ячейки оперативной памяти с адресом `А2` в
3. Запустить в АЛУ схему, реализующую операцию, задаваемую `КОП`.
4. Записать результат из регистра `S` в ячейку оперативной памяти с
адресом `А3`.
Если выполняется операция деления, в оперативную память записываются
два результата: частное – в ячейку с адресом `А3`, остаток – в следующую
ячейку, по адресу `(А3+1) mod 16^4`.
* Условные переходы: сравниваются `R1` и `R2`, в зависимости от результата
* Размер ячейки оперативной памяти: 5 байт.
* Размер адреса: 2 байта.
* Арифметические вычисления производятся с одной ячейкой оперативной памяти.
* Код команды помещается в одну ячейку оперативной памяти `КОП А1 А2`.
Действия для арифметических команд `add`, `sub`, `smul`, `sdiv`, `umul`,
`udiv`:
2. Запустить в АЛУ схему `sub`, выставить регистр `FLAGS`
* `move A1 A2`: `[A1] := [A2]`
* Команда останова `halt` взводит флаг `HALT` в регистре `FLAGS`
Архитектура модельной машины с переменным (variable) фарматом команд.
* Размер ячейки оперативной памяти: 1 байт.
* Размер адреса: 2 байта.
* Арифметические вычисления производятся со словами в 5 ячеек оперативной
памяти.
* Код команды занимает разное количество ячеек в зависимости от выполняемой
операции.
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
Таблица кодов команд:
|Код команды|Мнемоник|Формат |Длина (в байтах)|
|:----------|:------:|:---------|---------------:|
|0x00 |move |move A1 A2| 5|
|0x01 |add |add A1 A2| 5|
|0x02 |sub |sub A1 A2| 5|
|0x03 |smul |smul A1 A2| 5|
|0x04 |sdiv |sdiv A1 A2| 5|
|0x05 |comp |comp A1 A2| 5|
|0x13 |umul |umul A1 A2| 5|
|0x14 |udiv |udiv A1 A2| 5|
|0x80 |jump |jump A1 | 3|
|0x81 |jeq |jeq A1 | 3|
|0x82 |jneq |jneq A1 | 3|
|0x83 |sjl |sjl A1 | 3|
|0x84 |sjgeq |sjgeq A1 | 3|
|0x85 |sjleq |sjleq A1 | 3|
|0x86 |sjg |sjg A1 | 3|
|0x93 |ujl |ujl A1 | 3|
|0x94 |ujgeq |ujgeq A1 | 3|
|0x95 |ujleq |ujleq A1 | 3|
|0x96 |ujg |ujg A1 | 3|
|0x99 |halt |halt | 1|
Действия для арифметических команд `add`, `sub`, `smul`, `sdiv`, `umul`,
`udiv`:
1. `R1 := [A1], R2 := [A2]`
3. `[A1] := S`
Действия для команды сравнения `cmp`:
1. `R1 := [A1], R2 := [A2]`
2. Запустить в АЛУ схему `sub`, выставить регистр `FLAGS`
* Условные переходы делаются исходя из регистра `FLAGS`
* `move A1 A2`: `[A1] := [A2]`
* Команда останова `halt` взводит флаг `HALT` в регистре `FLAGS`
Архитектура одноадресной модельной машины.
* Размер ячейки оперативной памяти: 3 байта.
* Размер адреса: 2 байта.
* Арифметические вычисления производятся с одной ячейкой оперативной памяти.
* Код команды помещается в одну ячейку оперативной памяти `КОП А`.
Регистры `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`
* Условные переходы делаются исходя из регистра `FLAGS`
* `load A`: `S := [A]`
* `store A`: `[A] := S`
* `swap`: `S, S1 := S1, S`
* Команда останова `halt` взводит флаг `HALT` в регистре `FLAGS`
Архитектура модельной машины с модификацией адресов (modification).
* Арифметические вычисления производятся со словом в 4 байта.
* Код команды занимает разное количество ячеек в зависимости от выполняемой
операции. Арифметические команды имеют формы регистр-регистр и регистр-память.
Команды регистр-регистр имеют формат `КОП RA1 RA2` и занимают 2 байта.
Команды регистр-память имеют формат `КОП R M A` и занимают 4 байта.
Команды перехода имеют формат `КОП 0 0 A` и занимают 4 байта.
Основное отличие этой машины от предыдущих - наличие адресуемых регистров
общего назначения `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]`.
|Код команды|Мнемоник|Формат |Длина (в байтах)|
|:----------|:------:|:----------|---------------:|
|0x00 |load |load R M A | 4|
|0x01 |add |add R M A | 4|
|0x02 |sub |sub R M A | 4|
|0x03 |smul |smul R M A | 4|
|0x04 |sdiv |sdiv R M A | 4|
|0x05 |comp |comp R M A | 4|
|0x13 |umul |umul R M A | 4|
|0x14 |udiv |udiv R M A | 4|
|0x10 |store |store R M A| 4|
|0x20 |rmove |rmove RX RY| 2|
|0x21 |radd |radd RX RY | 2|
|0x22 |rsub |rsub RX RY | 2|
|0x23 |rsmul |rsmul RX RY| 2|
|0x24 |rsdiv |rsdiv RX RY| 2|
|0x25 |rcomp |rcomp RX RY| 2|
|0x33 |rumul |rumul RX RY| 2|
|0x34 |rudiv |rudiv RX RY| 2|
|0x80 |jump |jump 0 M A | 4|
|0x81 |jeq |jeq 0 M A | 4|
|0x82 |jneq |jneq 0 M A | 4|
|0x83 |sjl |sjl 0 M A | 4|
|0x84 |sjgeq |sjgeq 0 M A| 4|
|0x85 |sjleq |sjleq 0 M A| 4|
|0x86 |sjg |sjg 0 M A | 4|
|0x93 |ujl |ujl 0 M A | 4|
|0x94 |ujgeq |ujgeq 0 M A| 4|
|0x95 |ujleq |ujleq 0 M A| 4|
|0x96 |ujg |ujg 0 M A | 4|
Действия для загрузки исполнительного адреса в регистр `addr R M A`:
1. `S := [M] + A`
2. `R := S`
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
Действия для арифметических команд регистр-память (исключая деление) `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`
* Условные переходы делаются исходя из регистра `FLAGS`
* Команда останова `halt` взводит флаг `HALT` в регистре `FLAGS`
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>