Данная работа была выполнена в рамках курса «Архитектура ЭВМ». Ниже представлен отчёт по её выполнению и общая архитектура эмулятора.
$ gcc --version
gcc (GCC) 14.1.1 20240507
-std=c99
Изначально, я хотел кросс-компилировать C в asm при помощи gcc, но я решил что интереснее будет перевести код руками.
Я никак не оптимизировал код (например, не выносил умножение на pa[x]
из цикла for(k)
).
Используемые регистры никак логически не разделены и не сгруппированы, потому что я конвертировал имена в ABI-формат уже после того, как написал код.
В целом, самый интересный момент, который можно отметить - арифметика указателей. Важно следить за размером типа и домножать сдвиг на соответствующее значение.
К коду на ассемблере приложены... "своеобразные" комментарии, которые я оставлял во время написания, чтобы ориентироваться в коде и не запутаться.
Параметр | Значение | Формула | Описание |
---|---|---|---|
MEM_SIZE |
512 * 1024 | Размер всей памяти. | |
CACHE_SIZE |
2 * 1024 | Размер кэша. | |
CACHE_LINE_SIZE |
32 | 2**CACHE_OFFSET_LEN |
Размер кэш линии в байтах. |
CACHE_LINE_COUNT |
64 | CACHE_SIZE / CACHE_LINE_SIZE |
Количество кэш линий. Количество линий равно размеру кэша / размер линии |
CACHE_WAY |
4 | CACHE_LINE_COUNT / CACHE_SETS |
Количество кэш линий в каждом наборе. |
CACHE_SETS |
16 | 2**CACHE_INDEX_LEN |
Количество кэш наборов. |
ADDR_LEN |
19 | log2(MEM_SIZE) |
Длина адреса. |
CACHE_TAG_LEN |
10 | ADDR_LEN - CACHE_INDEX_LEN - CACHE_OFFSET_LEN |
Длина тэга кэша в адресе. Так как кэш должен уметь хранить любой адрес, размер тэга равен битам, "оставшимся" после выбора набора и байта в линии. |
CACHE_INDEX_LEN |
4 | Длина индекса набора кэша в адресе. | |
CACHE_OFFSET_LEN |
5 | Длина смещения адреса в кэш линии. |
Для внутреннего представления ассемблерных инструкций используется intermediate representation (struct intermediate
). В этой структуре находятся 4 поля:
- Инструкция (
enum instr
) - Аргумент #1 (
uint32_t
) - Аргумент #2 (
uint32_t
) - Аргумент #3 (
uint32_t
)
Аргументы расположены в том же порядке, в котором они расположены при записи инструкции в ассемблере.
Все инструкции и их параметры объявлены в файле instructions.h
.
Для того, чтобы расположить все константы в одном месте, и чтобы избежать повторения кода и ошибок, возникающих из-за невнимательности, были использованы (мои любимые) макросы и генерация кода. Все инструкции и их константы записаны в одном макросе в виде таблицы FOREACH_INSTR
, принимающем как параметр произвольный макрос, и раскрывающем его для каждой инструкции:
#define FOREACH_INSTR(M) \
/* n, args str ident opcode func3 func7 */ \
M( 2, "rn ", "lui", LUI, 0b0110111, 0, 0 ) \
M( 2, "rn ", "auipc", AUIPC, 0b0010111, 0, 0 ) \
M( 2, "rn ", "jal", JAL, 0b1101111, 0, 0 ) \
// ...
Данные в таблице взяты из спецификации1, стр 554-557.
При помощи этого макроса сгенерированы:
- enum со всеми инструкциями
- lookup таблицы
instr->opcode
,instr->nargs
,instr->args
,instr->funct3
,instr->funct7
- Функция
parse_instr
, возвращающаяenum instr
по соответствующей строке-идентификатору инструкции.
Для удобства представлений инструкций в бинарном формате используются битовые поля. В файле instructions.h
, для всех вариантов кодирования инструкций объявлена соответствующая структура instr_*
. Также, для конвертации между представлением в виде структуры и в виде числа без использования хаков с кастами, используется union instr_generic
.
Референс варинтов кодирования: спецификация1, стр 24.
Трансляция проходит в два этапа:
- Конвертация asm в IR. (
parser.h
) - Конвертация IR в bin. (
core.h
)
Трансляция asm->IR происходит в функции parse_skkv_asm
, и не особо интересена с точки зрения реализации. ABI-названия регистров взяты из RISC-V Assembly Programmer's Manual2. Парсинг инстурукций происходит при помощи описаной ранее функции parse_instr
. Данные о типе и количестве аргументов также берутся из описаных ранее lookup таблиц.
Из-за использования lookup таблиц, транцсляция IR->bin так же является тривиальной, за исключением нескольких случаев:
- В инструкциях
slli
,srli
,srai
, 3 аргумент обрезается до 5 бит. - В инструкции
srai
, необходимо установить 10-й бит immediate. fence
имеет особый формат хранения аргументов в immediate.fence.tso
,pause
,ecall
,ebreak
заданы константами.
Кэш реализован "честно", то есть, запись и чтение в кэш и в память ведётся раздельно, и при вытеснении / записи линий, данные переносятся из одного места в другое, а не лежат в одном. В данной работе было бы достаточно просто это симулировать, но мне захотелость сделать честную эмуляцию.
Память представлена в виде структуры memory
. Для доступа к ней используются "высокоуровневые" функции mem_readX
и mem_writeX
. Они также отвечают за обновление счётчика общих вызовов и счётчиков попаданий в кэш. В свою очередь эти функции вызывают cache_read
и cache_write
, которые вызывают внутренние функции для работы с кэшем (о них ниже).
Для удобного разбиения адреса на части используется union _cache_addr
и битовые поля.
Возвращает:
- Указатель на кэш линию, в которой находится запрошенный адрес.
- Был ли блок памяти, в котором находится адрес, закэширован.
Обновляет "время" доступа к кэш линии.
Ищет соответствующую адресу кэш линию, сравнивая тэги в наборе. В случае, если в кэше нету запрошенного адреса, при помощи функции _cache_find_victim_way(...)
находит линию, которая будет вытеснена, записывает данные из неё в основную память (если линия была валидной), и копирует данные из памяти в кэш линию. Обновляет тэг кэш линии.
В зависимости от политики, выбирает из набора кэш линию, которая будет вытеснена:
Для LRU: ищет кэш линию с самым старым "временем" доступа.
Для bit pLRU: ищет первую линию с MRU битом = 0.
Обновляет время доступа к кэш линии:
Для LRU: Увеличивает внутренний счётчик на 1, устанавливает время доступа равным внутреннему счётчику.
Для bit pLRU: Устанавливает MRU бит. В случае, если для всех кэш линий в наборе MRU биты = 1, обнуляет все биты, кроме только что установленного.
Состояние эмулятора представлено структурой machine
. В ней находятся регистры, память, и указатель на текущую инструкцию.
Начальное состояние создается при помощи функции machine_new(...)
, которая:
- Обнуляет регистры эмулятора
- Обнуляет статистику кэша
- Устанавливает указатель на текущую инструкцию = 0
- Устанавливает все кэш линии в невалидное состояние
Инструкции выполняются при помощи функции machine_process_ir
. Она принимает инструкцию в IR-формате, и эмулирует её выполнение34.
Так как в данной реализации, после каждой операции pc
сдвигается на 4 вперед, для инструкций, которые должны смещать pc
на определённый offset, мы искусственно уменьшаем его на 4. Это верно для инструкций auipc
, jal*
и b*
.
Для реализации функций sign extend, был взят код из легендарной статьи Bit Twiddling Hacks5.
Для удобного выполнения signed/unigned операций, были сделаны два макроса S(a, op, b)
и U(a, op, b)
, которые перед выполнением операции op
кастят оба операнда к типам int32_t
и uint32_t
соответственно.