Амузинский Артем Андреевич, P3206
- Вариант:
forth | stack | neum | mc | tick | binary | stream | port | pstr | prob1 | cache - Расшифровка варианта:
forth: forth-like stack-based syntax with Reverse Polish Notation (RPN)stack: stack-based CPU architectureneum: Von Neumann architecturemc: microcoded control unittick: cycle-accurate simulationbinary: true binary machine codestream: stream based I/Oport: port-mapped I/Opstr: Length-prefixed (Pascal string)prob1: Find the largest palindrome made from the product of two 3-digit numbers.
Почему-то удалился комментарий из гугл таблицы
- Стратегия вычислений - стековая.
- Постфиксная запись (обратная польская нотация).
- Стек возврата — хранит адреса возврата для работы процедур и иногда хранит промежуточное значение, например для команды swap, но после выполнения команды возвращается в изначально значение.
- Сначала код полностью транслируется, потом последовательно выполняется.
- Область видимости: все переменные и все функции доступны везде.
- Термом S" <последовательность_символов>" объявляются строки, любое число определяется как знаковое. Строки, записанные не в указанном формате, трактуются как названия переменных или функций. Число может быть записано в десятичном или шестнадцатиричном формате.
- Код всегда будет начинать выполнение с метки
_start:
<program> ::= <line>*
<line> ::= <label> <comment>? "\n"
| <instr> <comment>? "\n"
| <comment> "\n"
<label> ::= <label_name> ":"
<instr> ::= <op0>
| <op1> " " <label_name>
| <op1> " " <integer>
| <op1> " " <variable>
<op0> ::= "drop"
| "dup"
| "swap"
| "+"
| "-"
| "*"
| "/"
| "mod"
| "negate"
| "="
| "<"
| ">"
| "and"
| "or"
| "xor"
| "invert"
| "if"
| "!"
| "@"
| "halt"
| "ret"
| "c"
<op1> ::= "lit"
| "call"
| "jump"
| "in"
| "out"
<positive_integer> ::= [0-9]+
<lowercase_letter> ::= [a-z]
<uppercase_letter> ::= [A-Z]
<letter> ::= <lowercase_letter> | <uppercase_letter>
<digit> ::= [0-9]
<integer> ::= "-"? <digit>+
string ::= S" <любые символы>"
<letter_or_digit> ::= <letter> | <digit>
<letter_or_digit_or_underscore> ::= <letter_or_digit> | "_"
<label_name> ::= <letter> <letter_or_digit_or_underscore>*
<comment> ::= " "* ";" " "* <comment_text>?
<comment_text> ::= <letter_or_digit_or_underscore> ( " " <letter_or_digit_or_underscore> )*
Организация памяти:
- Вся внешняя память - статическая, SRAM
- Адресация – прямая абсолютная.
Загрузка значения на вершину стека (
LIT). - Программа и данные хранятся в общей памяти согласно
архитектуре Фон-Неймановского процессора.
Программа состоит из
набора инструкций, последняя инструкция –
HALT. Процедуры размещаются в той же памяти, они обязаны завершаться при помощи инструкцииRET. - Операция записи в память перезапишет ячейку памяти как ячейку с данными. Программист имеет доступ на чтение/запись в любую ячейку памяти.
Организация стека:
- Стек реализован в виде отдельной структуры память, представляющего собой массив, у которого можно использовать только первое и второе значение.
- Стек 32-разрядный и позволяет полностью помещать один операнд в одну ячейку памяти.
Особенности процессора:
- Доступ к памяти осуществляется по адресу из специального регистра. Значение в нем может быть защелкнуто либо из PC, либо из вершины стека
- Обработка данных осуществляется в стеке. Данные попадают в стек из памяти, либо из устройств ввода/вывода.
- Поток управления:
- Значение
PCинкрементируется после исполнения каждой инструкции, - Условные (
if) и безусловные (jump) переходы.
- Значение
Набор инструкций:
drop – Удаляет верхний элемент стека.
dup – Дублирует верхний элемент стека.
swap – Меняет местами два верхних элемента стека.
+ – Складывает два верхних элемента стека.
- – Вычитает верхний элемент из второго.
* – Умножает два верхних элемента.
/ – Делит второй элемент на верхний.
mod – Остаток от деления второго элемента на верхний.
negate – Инвертирует знак верхнего элемента.
= – Проверяет равенство двух верхних элементов, кладет 1 (истина) или 0 (ложь).
< – Проверяет, меньше ли второй элемент, чем верхний.
> – Проверяет, больше ли второй элемент, чем верхний.
and – Побитовая операция И для двух верхних элементов.
or – Побитовая операция ИЛИ для двух верхних элементов.
xor – Побитовая операция Исключающее ИЛИ.
invert – Инвертирует все биты верхнего элемента.
if {address} – Условное выполнение: если верхний элемент стека не 0, выполняет код после if.
! – Записывает значение во вторую ячейку памяти (store).
@ – Читает значение из памяти (addr @).
in {port} – Считывает один символ с клавиатуры и кладет его код в стек.
lit <literal> – Загрузка литерала в вершину стека.
out {port} – Загрузка вершины стека в буфер вывода.
jump {address} – Переход на метку.
call {address} – Вызов процедуры.
ret – Возвращение из процедуры.
c – Загрузить значение Carry-flag в стек.
halt – остановка тактового генератора.
запуск:
translator.py input output.bin
input - входной файл с ассемблерным кодом
output.bin - бинарный файл, в который будет транслироваться код, так же
будет сделан output.bin.hex с мнемониками и 16-ричной трансляцией кода
Трансляция реализуется в два прохода:
- Первый проход — генерация машинного кода без подстановки переходов и расчёт меток
-
1.1 Парсинг исходного текста в термы (text_to_terms)
- Исходный текст разбивается на строки, каждая строка — на слова.
-
Каждое слово анализируется:
- Если это метка (оканчивается на
:), она сохраняется отдельно. - Если это известный символ (операция, литерал, имя переменной), он сохраняется как Term(line, pos, symbol).
- Если это метка (оканчивается на
-
1.2 Формирование таблицы меток (labels)
- Итерация 1: считаем количество инструкций до каждой метки (метки не входят в подсчёт).
- Итерация 2: присваиваем каждой метке её смещённый адрес.
-
В new_labels производится корректировка адресов с учётом инструкций с аргументами (lit, jump, call, if, in, out), которые занимают дополнительное место в памяти (4 байта вместо 1–2).
-
- Второй проход — генерация команд с подстановкой адресов переходов
- 2.1 Фильтрация термов
- Метки удаляются из списка термов: они уже обработаны и присутствуют в labels.
- 2.2 Генерация инструкций
- По каждому Term строится инструкция:
- if, jump, call: преобразуются в соответствующий Opcode, аргументом становится адрес из new_labels.
- lit: за ним ожидается число (десятичное или шестнадцатеричное 0x...), сохраняется как аргумент.
- in, out: за ними указывается номер порта.
- Остальные команды: трансляция без аргумента, ищется соответствующий Opcode в symbol_to_opcode.
- По каждому Term строится инструкция:
- 2.1 Фильтрация термов
- Преобразование в машинный код
- to_bytes
Каждая инструкция переводится в байты:
- 1 байт на opcode;
- 3 байта на аргумент (если он есть). Команда с аргументом:
- to_bytes
Каждая инструкция переводится в байты:
┌─────────┬─────────────────────────────────────────────────────────────┐
│ 31...24 │ 23 0 │
├─────────┼─────────────────────────────────────────────────────────────┤
│ опкод │ аргумент │
└─────────┴─────────────────────────────────────────────────────────────┘
Команда без аргумента:
┌─────────┐
│ 7...0 │
├─────────|
│ опкод │
└─────────┘
- Сохранение результатов
- Исходный код читается из файла.
- Переводится в список инструкций.
- Генерируются два представления:
- бинарное (.bin);
- шестнадцатеричное (.hex).
- Все сохраняется в указанный путь
запуск:
machine.py output.bin input_stream [--quiet <without prints>]
output.bin - входной файл с уже транслированным бинарным кодом
input_stream - поток ввода
--quiet - флаг для отключения вывода процессора
Описание реализации:
- Микропрограммное управление.
- Функция
process_next_commandпереводит Opcode в микрокод и исполняет его потактово (каждый такт выполняется сигнал). - Процесс моделирования – потактовый.
- Начало симуляции происходит в функции
simulation. Процесс моделирования продолжается до исполнения инструкцииHALT. - Переполнения стека в данной модели не предусмотрено.
- Особенность реализации: реализован mpc, который позволяет избежать множественного дублирования микрокоманд, например такое есть во всех операциях АЛУ. Микрокод на команду будет выполняться, пока меняется mpc.
Описание микрокода: Каждая микропрограмма содержит 41 сигнала
1. sf - открыть защелку с первого значения стека
2. ss - открыть защелку со второго значения стека
3. sm - сдвинуть стек
4. sp - запушить на стек
5. alul - открыть левый вход алу
6. alur - открыть правый вход алу
7. c - выставить carry флаг
8. z - выставить zero флаг
9. ta - из стека в регистр а
10. fa - из регистра а в стек
11. rspu - запушить в стек возврата
12. rspo - запопить из стека возварата
13. ioi - ввод с контроллера ввода-вывода
14. ioo - вывод с контроллера ввода-вывода
15 - 28. - арифметические и логические операции в алу (+ - * ... and or ...)
29 - 30. muxPC - мультиплексор у PC (00 - ничего, 01 - с верхенго входа, 10 - с нижнего)
31 - 34. muxALUS - мультиплексор у алу и стека (000 - tos, 001 - fromRS, 010 - fromA, 011 - fromIOC, 100 - fromALU, 101 - fromMEM, 110 - ничего)
35 - 37. pcinc - увеличение PC (000 - увеличиваем на 1, 001 - увеличиваем на 3, 010 - берем адрес из дата стека, 011 - берем адрес из ретурн стека, 100 - не изменяем)
38. mpcinc - увеличение mpc (0 - +1, 1 - из LUT)
39. mux2CU - защелкнуть из мукса в control unit
40. mux2stack - защелкнуть из мукса в stack
41. mux2alu - защелкнуть из мукса в alu
Рассмотрим как работает команда ADD
Она работает в 3 такта, за них выполняются 3 микрокоманды:
-
micro_add (1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 00 000 100 0 0 0 0 0)берем первое и второе значение стека, открываем оба входа алу, выполняем сложение и оставляем результат в алу, увеличиваем mpc, и выставляем флаги
-
micro_alu_2_stack (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 100 100 0 0 1 0 0)сохраняем значение из алу в стек, увеличиваем mpc
-
micro_next_command (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 110 000 0 0 0 0 1)берем следующую микрокоманду, увеличиваем PC
Микрокод представляет собой массив, в котором последовательно расположены микрокоманды, каждая машинная команда может выполниться как за одну микрокоманду, так и за несколько.
Control Unit:
Data Path:
S" Hello, world!" VARIABLE hello_world ; переменная со строкой
0x0 VARIABLE index ; переменная с индексом строки
0x0 VARIABLE len ; переменная с длиной строки (тк паскаль строки)
_start:
lit len
lit hello_world @
! ; сохраняем в переменную len длину паскаль строки
lit index
lit hello_world
lit 4
+
! ; сохраняем индекс первой буквы
while:
lit index @ @ ; загружаем первую букву и выводим ее
out 2
lit index
dup
@
lit 4
+ ; переходим на индекс следующей буквы
!
lit 1
lit len @ ; уменьшаем и сохраняем счетчик длины
-
dup
if end ; проверяем счетчик длины на 0, если да, то переходим на метку end, если нет, то продолжаем выводить буквы
lit len
swap
!
jump while ; продолжаем цикл
end: ; завершаем работу программы
halt
output.bin.hex
0x8 - 1500008C - lit (0000008C)
0xc - 15000050 - lit (00000050)
0x10 - 12 - @
0x11 - 11 - !
0x12 - 15000088 - lit (00000088)
0x16 - 15000050 - lit (00000050)
0x1a - 15000004 - lit (00000004)
0x1e - 3 - +
0x1f - 11 - !
0x20 - 15000088 - lit (00000088)
0x24 - 12 - @
0x25 - 12 - @
0x26 - 16000002 - out (00000002)
0x2a - 15000088 - lit (00000088)
0x2e - 1 - dup
0x2f - 12 - @
0x30 - 15000004 - lit (00000004)
0x34 - 3 - +
0x35 - 11 - !
0x36 - 15000001 - lit (00000001)
0x3a - 1500008C - lit (0000008C)
0x3e - 12 - @
0x3f - 4 - -
0x40 - 1 - dup
0x41 - 1000004F - if (0000004F)
0x45 - 1500008C - lit (0000008C)
0x49 - 2 - swap
0x4a - 11 - !
0x4b - 17000020 - jump (00000020)
0x4f - 14 - halt
0x50 - D - hello_world
0x54 - 48 - hello_world
0x58 - 65 - hello_world
0x5c - 6C - hello_world
0x60 - 6C - hello_world
0x64 - 6F - hello_world
0x68 - 2C - hello_world
0x6c - 20 - hello_world
0x70 - 77 - hello_world
0x74 - 6F - hello_world
0x78 - 72 - hello_world
0x7c - 6C - hello_world
0x80 - 64 - hello_world
0x84 - 21 - hello_world
0x88 - 0 - index
0x8c - 0 - len
(.venv) ~\PycharmProjects\csa-lab4 git:[main]
pytest
C:\Users\artem\PycharmProjects\csa-lab4\.venv\Lib\site-packages\pytest_golden\plugin.py:53: GoldenTestUsageWarning: Add 'enable_assertion_pass_hook=true' to pytest.ini for safer usage of pytest-golden.
warnings.warn(
==================================================================================================== test session starts ====================================================================================================
platform win32 -- Python 3.11.8, pytest-8.3.5, pluggy-1.6.0
rootdir: C:\Users\artem\PycharmProjects\csa-lab4
configfile: pytest.ini
plugins: anyio-4.9.0, golden-0.2.2
collected 7 items
golden_test.py ....... [100%]
===================================================================================================== 7 passed in 1.24s =====================================================================================================```
работа тестов на github:
Run poetry run coverage run -m pytest
/home/runner/.cache/pypoetry/virtualenvs/forth-yJKRdTo1-py3.11/lib/python3.11/site-packages/pytest_golden/plugin.py:53: GoldenTestUsageWarning: Add 'enable_assertion_pass_hook=true' to pytest.ini for safer usage of pytest-golden.
warnings.warn(
============================= test session starts ==============================
platform linux -- Python 3.11.12, pytest-7.4.4, pluggy-1.6.0
rootdir: /home/runner/work/csa-lab4/csa-lab4
configfile: pytest.ini
plugins: golden-0.2.2
collected 7 items
golden_test.py ....... [100%]
============================== 7 passed in 2.65s ===============================
Run poetry run coverage report
Name Stmts Miss Cover
------------------------------------
golden_test.py 53 0 100%
isa.py 113 8 93%
machine.py 396 61 85%
translator.py 118 13 89%
------------------------------------
TOTAL 680 82 88%
Для тестирования использовал все необходимые программы, а именно:
- программа вывода Hello World!
- программа hello_user - golden/hello_user_name0.yml (для вопроса про имя), golden/hello_user_name1.yml (для приветствия пользователя)
- программа cat для вывода пользовательского ввода - golden/cat.yml
- программа arifm, которая отвечает за переполнение 32-битного регистра алу и сохранения этого числа в памяти - golden/carry_check.yml
- программа sort - сортировка массива, который ввел пользователь - golden/sort.yml
- программа prob1 для решения проблемы Эйлера - golden/prob.yml