asm | risc | harv | hw | tick | bin | stream | mem | prob5
Особенность | |
---|---|
ЯП. Синтаксис | синтаксис ассемблера. Необходима поддержка label-ов |
Архитектура | Система команд должна быть упрощенной, в духе RISC архитектур |
Организация памяти | Гарвардская архитектура |
Control Unit | hardwired. Реализуется как часть модели. |
Точность модели | процессор необходимо моделировать с точностью до такта |
Представление маш. кода | бинарное представление. При этом необходимо сделать экспорт в формате с мнемоникой команд для возможности анализа машинного кода. |
Ввод-вывод | Ввод-вывод осуществляется как поток токенов |
Ввод-вывод ISA | Memory-mapped |
Алгоритм | Каково наименьшее положительное число, которое делится без остатка на все числа от 1 до 20? |
<program> ::=
"section data:" <whitespace>* <data_section>?
<whitespace>
"section text:" <whitespace>* <instruction_section>?
<data_section> ::= <data> (<whitespace> <data>)*
<data> ::= (<label_declaration>) " " (<char_literal> | <number>) ("," (<char_literal> | <number>))*
<instruction_section> ::= <instruction> (<whitespace> <instruction>)*
<instruction> ::= (<label_declaration>)? " " <letter>+ (" " (<address> | (<reg> "," <address>) | (<reg> "," <reg> "," <address>)))?
<address> ::= <number> | <label>
<reg> ::= "x" <number>
<label_declaration> ::= <label> ":"
<label> ::= <letter>+
<char_literal> ::= "'" (<letter> | <digit> | <whitespace>)+ "'"
<comment> ::= ";" (<letter> | <digit> | <whitespace>)*
<letter> ::= <lower_letter> | <upper_letter>
<lower_letter> ::= [a-z]
<upper_letter> ::= [A-Z]
<whitespace> ::= " " | "\n" | "\t"
<number> ::= <digit> | ( ([1-9]) <digit>+ )
<digit> ::= [0-9]
В программе должны быть две обязательные секции - для данных (может быть пустой) и для кода - section data: и section text: соответственно
Поддерживаются метки.
Метка - это символьное имя, обозначающее ячейку памяти, которая содержит некоторую команду или данные. Метка обязана начинаться с строчной или прописной буквы, кроме того, может содержать в своём имени цифры
Метки INPUT
и OUTPUT
зарезервированы - используются для ввода-вывода.
В секции данных после метки следуют значения, располагающиеся последовательно по адресам, на которые указывает метка. Поддерживаются строковые литералы. Фактически в памяти будет массив, содержащий коды символов строки. В секции кода метка будет содержать адрес следующей после нее инструкции
Поддерживаются однострочные комментарии, начинаются с символа ;
Код выполняется последовательно.
Пример:
section data:
hello: 'Hello, World!',0
section text:
_start:
addi x2,x0,hello
addi x3,x0,OUTPUT
write:
lw x1,x2
beq x1,x0,end
sw x3,x1
addi x2,x2,1
jmp write
end:
halt
lw rd,rs
- загружает из памяти по адресуrs
в регистрrd
lwi rd,imm
- загружает из памяти по адресуimm
в регистрrd
swi rd,imm
- записывает значениеimm
в память по адресуrd
sw rd, rs
- записывает значение регистраrs
в память по адресуrd
add rd,rs1,rs2
- складываетrs1
иrs2
и записывает результат в регистрrd
sub rd,rs1,rs2
- вычитает изrs1
rs2
и записывает результат в регистр rdmul rd,rs1,rs2
- умножаетrs1
иrs2
и записывает результат в регистр rddiv rd,rs1,rs2
- делитrs1
наrs2
и записывает результат целочисленного деления в регистрrd
rem rd,rs1,rs2
- делитrs1
иrs2
и записывает результат остаток от деления в регистрrd
addi rd,rs1,imm
- складываетrs1
иimm
и записывает результат в регистрrd
subi rd,rs1,imm
- вычитает изrs1
imm
и записывает результат в регистрrd
muli rd,rs1,imm
- умножаетrs1
иimm
и записывает результат в регистрrd
divi rd,rs1,imm
- делитrs1
наimm
и записывает результат целочисленного деления в регистр rdremi rd,rs1,imm
- делитrs1
иimm
и записывает результат остаток от деления в регистрrd
beq rs1,rs2,imm
- условный переход по адресуimm
, если значения в регистрахrs1
==rs2
bne rs1,rs2,imm
- условный переход по адресуimm
, если значения в регистрахrs1
!=rs2
blt rs1,rs2,imm
- условный переход по адресуimm
, если значения в регистрахrs1
<rs2
bgt rs1,rs2,imm
- условный переход по адресуimm
, если значения в регистрахrs1
>rs2
bng rs1,rs2,imm
- условный переход по адресуimm
, если значения в регистрахrs1
<=rs2
bnl rs1,rs2,imm
- условный переход по адресуimm
, если значения в регистрахrs1
>=rs2
jmp imm
- безусловный переход по адресуimm
halt
- завершение программы
Работа с памятью
Модель памяти процессора:
i - number of instructions
Memory
Instruction memory
+-----------------------------+
| 00 : instruct 1 |
| 01 : instruct 2 |
| 02 : instruct 3 |
| ... |
| i : halt |
+-----------------------------+
Data memory
+------------------------------+
| 00 : variable 1 |
| 01 : variable 2 |
| 02 : array variable 1,len=l |
| ... |
| l+2 : variable 3 |
| l+3 : variable 4 |
| ... |
| |
+------------------------------+
| INTPUT |
+------------------------------+
| OUTPUT |
+------------------------------+
Реализовано в модуле translator.py
Особенности процессора:
- Машинное слово - 32 бита
- 4 регистра
- размер команд и типы аргументов фиксированы, имеет 4 типа
- Register
- Immediate
- Branch
- Jump
- каждая инструкция выполняется за 5 этапов (по такту на каждый)
fetch_instruction
- загрузка инструкции из памяти данныхdecode_instruction
- декодирование инструкцийexecute
- выполнение инструкций (вычисления в АЛУ, вычисления флагов по результату сравнения в branch comparator)memory_access
- доступ к памяти - для инструкцийwrite_back
- запись результирующего значения (из памяти или АЛУ в регистр). На этом же этапе в инструкциях переходов переписывается значение pc'a
Модель памяти процессора:
- Память разделена на память команд и память данных.
- Машинное слово -- 32 бита, знаковое. Линейное адресное пространство.
Процессор в модели содержит 4 регистра общего назначения
Для того, чтобы загружать значения непосредственно в DataPath существует функциональный элемент - Immediately Generator.
Инструкции представляют собой 32-битные машинные слова в следующем формате
rd
- register destination - регистр, куда будет записано значение после выполнения инструкцииrs1
иrs2
- register source 1,2 - регистры, значения которых будут использоваться для вычисления результата операцииimm
* - immediate - непосредственное значениеopcode
- номер инструкции
31 30 29 28 27 26 25 5 4 0 Bits
+-----------------------------------------------------------+
| rd | rs1 | rs2 | | opcode | Register type
+-----------------------------------------------------------+
| rd | rs1 | imm[22:21] | imm[20:0] | opcode | Immediate type
+-----------------------------------------------------------+
| imm[22:21] | rs1 | rs2 | imm[20:0] | opcode | Branch type
+-----------------------------------------------------------+
| imm | opcode | Jump type
+-----------------------------------------------------------+
* imm - имеет переменный размер, соответствующая типу инструкции часть извлекается из инструкции в immediate generator
Совпадают с поддерживаемым командами
Инструкция | Тип инструкции | |
---|---|---|
ADD | Register | rs1 + rs2 -> rd |
SUB | Register | rs1 - rs2 -> rd |
MUL | Register | rs1 * rs2 -> rd |
DIV | Register | rs1 / rs2 -> rd |
REM | Register | rs1 % rs2 -> rd |
ADDI | Immediate | rs1 + imm -> rd |
SUBI | Immediate | rs1 + imm -> rd |
MULI | Immediate | rs1 + imm -> rd |
DIVI | Immediate | rs1 + imm -> rd |
REMI | Immediate | rs1 + imm -> rd |
BEQ | Branch | rs1 == rs2 ? imm -> pc |
BNE | Branch | rs1 != rs2 ? imm -> pc |
BLT | Branch | rs1 < rs2 ? imm -> pc |
BGT | Branch | rs1 > rs2 ? imm -> pc |
BNL | Branch | rs1 >= rs2 ? imm -> pc |
BNG | Branch | rs1 <= rs2 ? imm -> pc |
LW | Register | dmem [rs2] -> rd |
LWI | Immediate | dmem [imm] -> rd |
SW | Register | rs1 -> dmem [rs2] |
SWI | Immediate | rs1 -> dmem [imm] |
JMP | JUMP | imm -> pc |
HALT |
Программы так же представлены в виде JSON
- Машинный код сериализуется в список JSON.
- Один элемент списка, одна инструкция (так как в risc размер инструкций фиксированный).
- Индекс списка - адрес инструкции. Используется для команд перехода.
Пример:
[
{
"opcode": "ADD",
"args": [
"arg1",
"arg2",
"arg3"
]
}
]
где:
opcode
-- строка с кодом операции;args
-- список аргументов (может отсутствовать (только в случае HALT));
Реализовано в модуле machine.py
Реализован в классе ControlUnit
.
- Hardwired (реализовано полностью на python).
- Моделирование на уровне тактов.
- Трансляция инструкции в последовательность (5 тактов) сигналов:
tick_by_tick
.
Особенности работы модели:
- Для журнала состояний процессора используется стандартный модуль logging.
- Количество инструкций для моделирования ограничено hardcoded константой.
- Остановка моделирования осуществляется при помощи исключений:
EOFError
-- если нет данных для чтения из порта ввода-вывода;StopIteration
-- если выполнена инструкцияhalt
.
- Управление симуляцией реализовано в функции
simulate
.
алг. | LoC | code байт | code инстр. | инстр. | такт. |
---|---|---|---|---|---|
cat | 46 | 15 | 188 | 240 | 1201 |
hello | 25 | 8 | 92 | 69 | 346 |
prob5 | 242 | 89 | 496 | 3778 | 18891 |
где:
- алг. -- название алгоритма (hello, cat, или как в варианте)
- LoC -- кол-во строк кода в реализации алгоритма
- code байт -- кол-во байт в машинном коде (если бинарное представление)
- code инстр. -- кол-во инструкций в машинном коде
- инстр. -- кол-во инструкций, выполненных при работе алгоритма
- такт. -- кол-во тактов, которое заняла работа алгоритма
- hello world - выводит
Hello, world!
в stdin. - cat - программа
cat
, повторяем ввод на выводе. - prob5 - problem 5
Интеграционные тесты реализованы тут: integration_test
CI:
lab3:
stage: test
image:
name: python-tools
entrypoint: [""]
script:
- python3-coverage run -m pytest --verbose
- find . -type f -name "*.py" | xargs -t python3-coverage report
- find . -type f -name "*.py" | xargs -t pycodestyle --ignore=E501,W291
- find . -type f -name "*.py" | xargs -t pylint
где:
python3-coverage
-- формирование отчёта об уровне покрытия исходного кода.pytest
-- утилита для запуска тестов.pycodestyle
-- утилита для проверки форматирования кода.E501
(длина строк)pylint
-- утилита для проверки качества кода. Некоторые правила отключены в отдельных модулях с целью упрощения кода.- Docker image
python-tools
включает в себя все перечисленные утилиты. Его конфигурация: Dockerfile.
Пример использования и журнал работы процессора на примере prob5
:
> python3 translator.py programs/prob5.json programs/prob5.bin
source LoC: 242 code instr: 112 bytes: 452
> ./machine.py programs/prob5.bin programs/input.txt
Текст вывода можно посмотреть тут