Эмулятор RISC-V процессора и кэша

Данная работа была выполнена в рамках курса «Архитектура ЭВМ». Ниже представлен отчёт по её выполнению и общая архитектура эмулятора.

Инструментарий

$ gcc --version
gcc (GCC) 14.1.1 20240507

-std=c99

Описание:

Перевод C в asm

Изначально, я хотел кросс-компилировать C в asm при помощи gcc, но я решил что интереснее будет перевести код руками.

Я никак не оптимизировал код (например, не выносил умножение на pa[x] из цикла for(k)).

Используемые регистры никак логически не разделены и не сгруппированы, потому что я конвертировал имена в ABI-формат уже после того, как написал код.

В целом, самый интересный момент, который можно отметить - арифметика указателей. Важно следить за размером типа и домножать сдвиг на соответствующее значение.

К коду на ассемблере приложены... "своеобразные" комментарии, которые я оставлял во время написания, чтобы ориентироваться в коде и не запутаться.

Расчёт параметров (`config.h`)

Параметр	Значение	Формула	Описание
`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		Длина смещения адреса в кэш линии.

IR

Для внутреннего представления ассемблерных инструкций используется 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          ) \

// ...

Данные в таблице взяты из спецификации¹, стр 554-557.

При помощи этого макроса сгенерированы:

enum со всеми инструкциями
lookup таблицы instr->opcode, instr->nargs, instr->args, instr->funct3, instr->funct7
Функция parse_instr, возвращающая enum instr по соответствующей строке-идентификатору инструкции.

Двоичное представление

Для удобства представлений инструкций в бинарном формате используются битовые поля. В файле instructions.h, для всех вариантов кодирования инструкций объявлена соответствующая структура instr_*. Также, для конвертации между представлением в виде структуры и в виде числа без использования хаков с кастами, используется union instr_generic.

Референс варинтов кодирования: спецификация¹, стр 24.

Трансляция asm в bin

Трансляция проходит в два этапа:

Конвертация asm в IR. (parser.h)
Конвертация IR в bin. (core.h)

Трансляция asm->IR происходит в функции parse_skkv_asm, и не особо интересена с точки зрения реализации. ABI-названия регистров взяты из RISC-V Assembly Programmer's Manual². Парсинг инстурукций происходит при помощи описаной ранее функции parse_instr. Данные о типе и количестве аргументов также берутся из описаных ранее lookup таблиц.

Из-за использования lookup таблиц, транцсляция IR->bin так же является тривиальной, за исключением нескольких случаев:

В инструкциях slli, srli, srai, 3 аргумент обрезается до 5 бит.
В инструкции srai, необходимо установить 10-й бит immediate.
fence имеет особый формат хранения аргументов в immediate.
fence.tso, pause, ecall, ebreak заданы константами.

Модель памяти (`memory.h`)

Кэш реализован "честно", то есть, запись и чтение в кэш и в память ведётся раздельно, и при вытеснении / записи линий, данные переносятся из одного места в другое, а не лежат в одном. В данной работе было бы достаточно просто это симулировать, но мне захотелость сделать честную эмуляцию.

Память представлена в виде структуры memory. Для доступа к ней используются "высокоуровневые" функции mem_readX и mem_writeX. Они также отвечают за обновление счётчика общих вызовов и счётчиков попаданий в кэш. В свою очередь эти функции вызывают cache_read и cache_write, которые вызывают внутренние функции для работы с кэшем (о них ниже).

Для удобного разбиения адреса на части используется union _cache_addr и битовые поля.

`_cache_access(...)`

Возвращает:

Указатель на кэш линию, в которой находится запрошенный адрес.
Был ли блок памяти, в котором находится адрес, закэширован.

Обновляет "время" доступа к кэш линии.

Ищет соответствующую адресу кэш линию, сравнивая тэги в наборе. В случае, если в кэше нету запрошенного адреса, при помощи функции _cache_find_victim_way(...) находит линию, которая будет вытеснена, записывает данные из неё в основную память (если линия была валидной), и копирует данные из памяти в кэш линию. Обновляет тэг кэш линии.

`_cache_find_victim_way(...)`

В зависимости от политики, выбирает из набора кэш линию, которая будет вытеснена:

Для LRU: ищет кэш линию с самым старым "временем" доступа.

Для bit pLRU: ищет первую линию с MRU битом = 0.

`_cache_update_time(...)`

Обновляет время доступа к кэш линии:

Для LRU: Увеличивает внутренний счётчик на 1, устанавливает время доступа равным внутреннему счётчику.

Для bit pLRU: Устанавливает MRU бит. В случае, если для всех кэш линий в наборе MRU биты = 1, обнуляет все биты, кроме только что установленного.

Эмуляция (`machine.h`)

Состояние эмулятора представлено структурой machine. В ней находятся регистры, память, и указатель на текущую инструкцию.

Начальное состояние создается при помощи функции machine_new(...), которая:

Обнуляет регистры эмулятора
Обнуляет статистику кэша
Устанавливает указатель на текущую инструкцию = 0
Устанавливает все кэш линии в невалидное состояние

Инструкции выполняются при помощи функции machine_process_ir. Она принимает инструкцию в IR-формате, и эмулирует её выполнение³⁴.

Так как в данной реализации, после каждой операции pc сдвигается на 4 вперед, для инструкций, которые должны смещать pc на определённый offset, мы искусственно уменьшаем его на 4. Это верно для инструкций auipc, jal* и b*.

Для реализации функций sign extend, был взят код из легендарной статьи Bit Twiddling Hacks⁵.

Для удобного выполнения signed/unigned операций, были сделаны два макроса S(a, op, b) и U(a, op, b), которые перед выполнением операции op кастят оба операнда к типам int32_t и uint32_t соответственно.

mrsobakin/riscv

Эмулятор RISC-V процессора и кэша

Инструментарий

Описание:

Перевод C в asm

Расчёт параметров (`config.h`)

IR

Инструкции

Двоичное представление

Трансляция asm в bin

Модель памяти (`memory.h`)

`_cache_access(...)`

`_cache_find_victim_way(...)`

`_cache_update_time(...)`

Эмуляция (`machine.h`)

Источники

mrsobakin/riscv

Эмулятор RISC-V процессора и кэша

Инструментарий

Описание:

Перевод C в asm

Расчёт параметров (config.h)

IR

Инструкции

Двоичное представление

Трансляция asm в bin

Модель памяти (memory.h)

_cache_access(...)

_cache_find_victim_way(...)

_cache_update_time(...)

Эмуляция (machine.h)

Источники

Footnotes

Расчёт параметров (`config.h`)

Модель памяти (`memory.h`)

`_cache_access(...)`

`_cache_find_victim_way(...)`

`_cache_update_time(...)`

Эмуляция (`machine.h`)