В прошлой статье приделали конвейер и теперь можно запускать программы, расположенные в локальной памяти процессора. Но с одной лишь локальной памятью далеко не уедешь, у маленького ПЛИСа её жалких 50 кБ, поэтому надо делать небольшое локальное хранилище, синхронизируемое с внешней памятью, то есть кэш. Есть отладочная плата с SD RAM, в идеальном случае хорошо бы добавить её поддержку, но для начала внешнюю память будет изображать внутренняя. Дополнительным эффектом от добавления кэша оказалось увеличение доступной памяти, потому что для чтения параллельно с двух адресов создавалось два набора памяти, а теперь чтение за один такт делается только с одного адреса.
Ветка реализации проекта лежит на гитхабе.
Обзор существующих решений
Для начала посмотрим, что есть в теории и в других проектах. Википедия довольно подробно описывает принципы работы кэша. На Хабре есть обзорная статья по типам кэшей и есть статья про реализацию кэша с прямым отображением (DM или Direct Mapping). В DarkRiscV и VexRiscV также сделан кэш с прямым отображением. PicoRV обошёлся без кэша.
Размер блока
Вопрос о выборе типа кэша довольно нетривиален, надо держать в памяти, что в будущем ядер может стать больше одного. С одной стороны, кодирование адреса за счёт позиции элемента позволяет экономить память. То есть если на каждый 32-битный регистр для адреса заводить 32-битный регистр с данными, то расход получается х2 от размера данных, а если в данных сохранить сразу 256 бит и считать, что, например, 5-й байт имеет адрес = начальный адрес + 4, тогда расходы на хранение адреса сильно уменьшатся. С другой стороны, если доступ к памяти будет происходить не по порядку, то все эти 256 бит превратятся в бесполезную дополнительную нагрузку. Хотя надо отметить, что доступ по очереди встречается довольно часто, сохранение регистров в стеке или обработка строк, например.
FAM
Ответ на вопрос о последовательном доступе влияет не только на размер линии кэша, но также на выбор самой схемы кэша. DM кэш не обращает внимания на частоту использования данных, если две часто используемых переменных лежат по одному "адресу в кэше" (который в DM вычисляется как остаток от деления реального адреса на размер кэша), то они будут затирать друг друга. Если выбрать ассоциативный кэш (FAM или Fully Associative Cache), можно будет управлять временем удаления переменной из кэша и сделать хотя бы LRU(Least Recently Used), то есть закидывать только что использованное значение наверх, а снизу выбрасывать, соответственно, давно не используемое.
Скорость декодирования
Не знаю, как работают ключи в физической памяти (судя по упоминанию 2 транзисторов на ячейку, там аналоговый вентиль, подключенный к конденсатору), но с точки зрения электронщика можно предложить как минимум 3 варианта обращения к памяти.
- Подключение бита адреса к двум вентилям, чтобы активировался только один. С другой стороны у каждого входа ещё один такой же мультиплексор для следующего бита адреса и т.д. В итоге сигнал от регистра памяти проходит через address_length аналоговых вентилей.
- Массив однобитных проволочек, каждая из которых включается при обращении к соответствующему адресу, и эта проволочка подключает 32-битный регистр к общей шине.
- Такой же массив проволочек, но каждая проволочка перемножается на соответствующий ей 32-битный регистр и потом полученные значения через "ИЛИ" собираются в выходное значение.
В ПЛИС нет z-состояния, поэтому 3 вариант единственный подходит для реализации. Скорость декодирования получается равной log(address_length) + address_length: адрес параллельно сравнивается для разных ячеек, сравнение делается за log(address_length) и выдаёт сигнал на проволочку, потом полученное значение комбинируется обратно за log(cache_size=2^address_length)).
В ASIC скорее всего будет не лучше чем address_length.
Многопоточный доступ
Теперь пойдём дальше и подумаем, как работать с несколькими параллельными запросами. При запросе двух значений с разных линий сложно решить, какую линию поднять наверх. Можно было бы поднимать на первую и вторую позицию, но это увеличивает размер комбинаторики, поэтому в будущем для нескольких запросов будет несколько кэшей с не пересекающимися адресами. Допустим, если шин 4, то первый кэш будет хранить элементы с адресами, у которых остаток от деления на 4 равен 0, у второго остаток 1 и т.д. Это позволит выбирать параллельно несколько инструкций, лежащих одна за другой. Простой вариант сделать подобное поведение — это выбрать размер линии кэша равной размеру слова.
Разделение инструкций и данных
Если же говорить о разделении кэша инструкций и кэша данных, то здесь всё ещё очевиднее. Эти данные практически не пересекаются, поэтому нет смысла держать их в одном месте, а ещё если их разделить, то можно пробовать разные типы кэшей. Это может дать выгоду, так как поведение данных для инструкций и для данных ощутимо отличается, инструкции идут гораздо более последовательно, а данные могут записываться.
Уровни кэшей
Как только погружаешься в тему кэшей, всплывает TLB, MMU и другие интересные термины. Хотелось бы не создать проблем в будущем, если вдруг понадобится работа с виртуальными адресами, но вроде решается это легко. Просто говорим, что текущий кэш — это кэш первого уровня и работает с виртуальными адресами. Трансляцию виртуальных в физические адреса пусть делает кэш второго уровня, а пока у нас виртуальные и физические адреса не отличаются, можем не заморачиваться.
Без проброса памяти
Ещё один вопрос — что делать с ответом памяти. Первый вариант (он же самый простой и сделан в первом коммите) — спокойно получить ответ от памяти, положить куда надо, а на следующем такте выдать значение, которое уже точно есть в кэше. Плюс этого решения не только в простоте, но и в большей частоте на ПЛИС (42 МГц). Но в таком случае каждая команда до попадания в кэш будет тратить минимум 2 такта, тест с кэшем на 8 элементов и многотактовым умножением выдал всего лишь 1.56 CM/МГц.
2K performance run parameters for coremark.
CoreMark Size : 666
Total ticks : 6420
Total time (secs): 64
Iterations : 1
Compiler version : GCC12.2.0
CoreMark end 6841
Пробрасывание памяти
Чтобы избежать лагов, добавил проброс ответа памяти параллельно с ответом кэша. Частота в итоге просела до 33 МГц — хоть выход памяти и буферизован, но там пара шагов отбирают 5 наносекунд. Будем считать, что это особенности реализации конкретной ПЛИС, так что пока оставим как есть, потом можно будет ещё нарезать стадий конвейера. Так вот, частота просела, зато коремарки восстановлены, однотактовый вариант инструкций выдаёт примерно такую же производительность (3 CM/МГц), как и до добавления кэша.
2K performance run parameters for coremark.
CoreMark Size : 666
Total ticks : 3353
Total time (secs): 33
Iterations : 1
Compiler version : GCC12.2.0
CoreMark end 3623
У многотактового умножения падение производительности ещё меньше, потому что при одновременном обращении к памяти двух кэшей приоритет отдаётся инструкциям. То есть если надо прочитать данные в один регистр, а потом прочитать команду и выполнить операцию с другими регистрами, то сначала прочитается команда и будет выполняться несколько тактов, а во время её выполнения прочитаются данные для предыдущей команды.
Опциональное кэширование
Ещё один интересный эффект случился с тем, что в первой реализации проброса из-за бага значения сохранялись в кэш только в том случае, когда промахи не шли подряд, и это привело к ускорению работы. Смысл в том, что если оба кэша не пытаются прочитать данные из памяти одновременно, то и нет смысла сохранять их в кэш. То есть в кэш инструкций попадают инструкции, работающие с памятью, а в кэш данных не попадают значения из стека, которые пачкой читаются в регистры. Возможно это стоило бы сделать фичей, если только память и дальше будет успевать отвечать за один такт.
Реализация
Ладно, вводная часть о том, почему принимались конкретные решения, закончена, теперь пора писать код. Для начала определимся с интерфейсом модуля кэша.
module RiscVCacheCommon
#(parameter SIZE = 8)
(
input clock,
input reset,
output [31:0] memory_address, // обращение к памяти по заданному адресу
output memory_read, // запрос на чтение памяти
output memory_write, // запрос на запись в память
input [31:0] memory_in, // прочитанные из ОЗУ данные
output [31:0] memory_out, // записываемые в ОЗУ данные
input memory_ready, // запрос к памяти отработал
input [31:0] data_address, // обращение к кэшу по заданному адресу
input [1:0] data_width, // размер данных для записи
input data_read, // запрос на чтение данных из кэша
input data_write, // запрос на запись данных в кэш
input [31:0] data_in, // записываемые в кэш данные
output [31:0] data_out, // прочитанные из кэша данные
output data_ready // отработал ли запрос на обработку данных
);
Подключение ядра
Кэш для ядра почти прозрачный, дополнительно надо обработать только флаг ответа. Поскольку раньше ожидание по флагам уже было реализовано, дополнительные изменения в коде ядра будут небольшими. В интерфейс добавятся флажки готовности.
input instruction_ready,
input data_ready
Теперь можно рассчитывать, что готовность инструкции будет сбрасываться по сигналу reset, так что самим этот флаг можно не хранить.
wire stage1_empty = !instruction_ready; //стадия конвейера не получила инструкцию с предыдущего этапа
Можно на всякий случай обнулить инструкцию, чтобы ничего лишнего не запускалось.
wire [31:0] instruction = stage1_empty ? 0 : instruction_data;
Ещё одно изменение состоит в том, что раньше мы ожидали ответа памяти сразу на следующем такте, а теперь тактов может пройти несколько, и чтобы не ломать конвейер, хотелось бы кидать запрос по второму разу уже на следующей стадии. Тогда при положительном ответе памяти можно будет подать ей на обработку следующую порцию данных с предыдущего этапа без дополнительного ожидания в один такт. Для этого убираем прямое подключение первого этапа к выводам памяти и мультиплексируем на втором этапе, а также добавляем ожидание подтверждения от памяти.
// значения первого этапа
wire stage1_data_read = is_op_load && !stage1_pause;
wire stage1_data_write = is_op_store && !stage1_pause;
wire[31:0] stage1_data_out = reg_s2;
wire[31:0] stage1_data_address = (is_op_load || is_op_store) ? reg_s1 + immediate : 0;
wire[1:0] stage1_data_width = op_funct3[1:0]; //0-byte, 1-half, 2-word
// обработка второго этапа
reg [31:0] stage2_reg_s2; //повтор записи в память, если на первой стадии не сработало
wire stage2_wait; //ожидание ответа от памяти
always@(posedge clock or posedge reset)
begin
if (reset) begin
stage2_reg_s2 <= 0;
end
// пока ожидаем ответ, новые значения не принимаем
else if (!stage2_wait) begin
...
stage2_reg_s2 <= reg_s2;
...
end
end
// запись в register destination разрешаем только когда ожидание закончилось
wire stage2_write_ready = stage2_is_rd_changed && !stage2_empty && !stage2_wait;
// если не успели обработать память, просим подождать
wire stage2_memory_wait = (stage2_is_op_load || stage2_is_op_store) && !data_ready;
assign stage2_wait = stage2_memory_wait;
assign stage1_jam_up = stage2_wait;
// повторяем запрос к памяти при необходимости
assign data_read = stage2_memory_wait ? stage2_is_op_load : stage1_data_read;
assign data_write = stage2_memory_wait ? stage2_is_op_store : stage1_data_write;
assign data_out = stage2_memory_wait ? stage2_reg_s2 : stage1_data_out;
assign data_address = stage2_memory_wait ? stage2_addr : stage1_data_address;
assign data_width = stage2_memory_wait ? stage2_funct3[1:0] : stage1_data_width;
Код FAM кэша с LRU
Сначала кэш кажется лёгким, но после недели-двух, потраченных на отладку, становится понятно, что подходить к нему надо серьёзно. И полученное в результате знание было таким:
- кэш за один такт должен делать одно действие
- кэш можно рассматривать как процессор, умеющий делать две инструкции: чтение и запись (или ничего)
Контейнер данных
И так, для начала заводим ассоциативное хранилище.
reg [31:0] cache_value [0:SIZE-1]; // значения самой памяти
reg [31-2:0] cache_address [0:SIZE-1]; // виртуальные адреса
reg cache_filled [0:SIZE-1]; // значение есть в наличии
Теперь для каждой линии надо заполнить флаг совпадения адреса и флаг сдвига. Если адрес совпал, ячейка попадает наверх, а всё что выше неё сдвигается вниз.
Наружу хранилище выдаёт флаг попадания и значение из ячейки, в которую попали, а назад получает разрешение на обновление верхней ячейки и значение, которое в неё записать. Оно может отличаться от того что вернуло хранилище, так как у нас может быть запись. Писаться может часть байт, и в таком случае значение должно быть изменено, но даже если значение перезаписывается полностью, дубликат из кэша надо убрать.
reg cache_address_equal[0:SIZE-1]; // совпал входной адрес ячейки
reg cache_move_next [1:SIZE-1]; // надо ли читать данные сверху
reg cache_hit; // есть ли элемент с таким адресом
reg [31:0] cache_hit_value; // значение элемента по запрошенному адресу
wire cache_can_update; // можно ли записать элемент наверх
wire [31:0] cache_value_update; // какое значение вписать
Проброс нового значения
Чтобы упростить понимание и не заниматься ручным пробрасыванием, выход первого регистра хранилища мультиплексируем со значением, возвращённым памятью (или может быть изменённым).
integer i;
// пробрасываем ответ памяти на первую позицию
reg [31:0] temp_value [0:SIZE-1];
reg temp_filled [0:SIZE-1];
wire [31:0] cache_value_0;
wire cache_filled_0;
always@(*) begin
for(i = 0; i < SIZE; i = i + 1) begin
temp_value[i] = cache_value[i];
temp_filled[i] = cache_filled[i];
end
if (cache_can_update) begin
temp_value[0] = cache_value_0;
temp_filled[0] = cache_filled_0;
end
end
Адрес не мультиплексируем, потому что он сразу записывается в свою ячейку. Наверное, пришло время объяснить, откуда такие сложности. Дело в том, что если на нулевом такте подать адрес и посчитать флаги совпадения адреса у ячеек, то в случае промаха память всё равно ответит только на следующем такте. И поскольку на следующем такте результат запроса уже есть, то нет смысла затягивать с обработкой следующего запроса, а для этого опять надо сравнивать адреса, то есть шина адреса будет занята. Причём предполагается, что на первом месте лежит ответ, который прислала память, а значит у этого элемента должен быть соответствующий адрес (пришедший в прошлом запросе).
Шина адреса
В ассоциативном хранилище значения расположены не по порядку, поэтому декодировать адрес придётся вручную. Здесь в теории можно ускорить переносы, но конкретно для ПЛИС это не очень актуально.
always@(*) begin
cache_hit = 0;
cache_hit_value = 0;
for(i = 0; i < SIZE; i = i + 1) begin
cache_address_equal[i] = (cache_address[i] == data_address[31:2]) && temp_filled[i];
if (i > 0) begin
cache_move_next[i] = !cache_hit;
end
cache_hit = cache_hit | cache_address_equal[i];
cache_hit_value = cache_hit_value | (cache_address_equal[i] ? temp_value[i] : 0);
end
end
Освобождение места
Место на вершине хранилища освобождается сразу же, как только поступает запрос от процессора. Если в кэше было значение, значит на следующем такте впишем ответ, а если не было, всё равно придётся ждать ответ памяти. Это приводит к такому эффекту, что если запросить подряд несколько значений и все они будут в кэше, то первый элемент кэша во время этих нескольких тактов будет пустым, а значение подаваться из временного регистра.
wire cache_can_move = (data_read || data_write) && temp_filled[0];
wire cache_save_address = data_read || data_write;
always@(posedge clock) begin
if (cache_can_move) begin
for(i = 1; i < SIZE; i = i + 1) begin
if (cache_move_next[i]) begin
cache_value[i] <= temp_value[i-1];
cache_address[i] <= cache_address[i-1];
end
end
end
else if (cache_can_update) begin
// если сдвига нет, а предыдущий результат есть, пишем в начало
cache_value[0] <= temp_value[0];
end
if (cache_save_address) begin
cache_address[0] <= data_address[31:2];
end
if (reset) begin
for(i = 0; i < SIZE; i = i + 1) begin
cache_filled[i] <= 0;
end
end
else if (cache_can_move) begin
for(i = 1; i < SIZE; i = i + 1) begin
if (cache_move_next[i]) begin
cache_filled[i] <= temp_filled[i-1];
end
end
//даже если значение стояло на первом месте, переносим его в выходной регистр
cache_filled[0] <= 0;
end
else if (cache_can_update) begin
cache_filled[0] <= temp_filled[0];
end
end
Здесь использование temp_value помогает не запутаться, куда записать результат предыдущей операции, потому что если вызвана новая операция, то старое значение должно попасть на вторую позицию, так как происходит сдвиг кэша.
Обработка операций
Выше была обработка, относящаяся к конкретному типу хранилища — ассоциативному, дальше будет более общий код. И так, кэш получил на вход команду, какие у него могут быть варианты действий.
- Если команда чтения, то либо в кэше значение есть и можно послать его в выходной регистр, либо запросить у памяти и на следующем такте выдать его вместо выходного регистра. Оба варианта отработают за один такт, если только память не будет занята другими запросами.
- Если пришла команда записи, но значения нет в кэше, тогда делаем запрос в память и просим процессор повторить запрос, хотя при записи сразу 4 байт этот шаг можно пропустить.
- Если пришла команда записи и значение есть, тогда его можно модифицировать, записать в кэш и отправить в память. Здесь опять помогает не запутаться temp_value, так как ответ памяти на следующем такте хранится в её выходном регистре, но мы уже используем его как значение из кэша.
И так за один такт каждая команда делает одно действие. С общей логикой определились, теперь можно писать код.
Этап 0
Любая операция задаёт адрес.
assign memory_address = {data_address[31:2], 2'b0};
Операция записи иногда преобразуется в операцию чтения.
wire write_need_request; // нужно ли перед записью запросить данные из памяти
wire write_to_read = data_write && !cache_hit && write_need_request;
Теперь точно знаем, чтение будет или запись. Читаем память если значение нужно, но его нет в наличии.
assign memory_read = !cache_hit && data_read || write_to_read;
Пишем, когда есть значение для записи.
assign memory_write = data_write && !write_to_read;
assign memory_out = cache_value_update;
Список модифицируемых байтов собирается как и раньше из выхода процессора data_width, а потом входное значение смешивается со значением из кэша.
wire [1:0] address_tail = data_address[1:0];
wire [3:0] byte_enable = !data_write? 0 :
data_width == 0 ? 4'b0001 << address_tail :
data_width == 1 ? 4'b0011 << address_tail :
4'b1111;
wire [31:0] write_mask = {{8{byte_enable[3]}}, {8{byte_enable[2]}}, {8{byte_enable[1]}}, {8{byte_enable[0]}}};
wire [31:0] aligned_data_in = data_in << address_tail * 8;
assign cache_value_update = (cache_hit_value & ~write_mask) | (aligned_data_in & write_mask);
assign write_need_request = (byte_enable != 4'b1111);
На этом обработка 0-го этапа завершена. Если бы не частичная запись, обошлось бы вообще в 5 строк.
Этап 1
На следующем этапе надо посмотреть, кто что ответил, и переслать ответ процессору. Ориентироваться на текущие значения при этом нельзя, иначе получится зацикливание логики и симуляция зависнет. Запоминаем, с какими значениями работали при запросе операции.
reg stage1_is_read;
reg stage1_is_write;
reg stage1_hit;
reg [31:0] stage1_hit_value;
reg [1:0] stage1_address_tail;
always@(posedge clock) begin
stage1_is_read <= reset ? 0 : data_read;
stage1_is_write <= reset ? 0 : data_write;
stage1_hit <= reset ? 0 : (cache_hit || data_write && !write_need_request);
stage1_hit_value <= cache_value_update;
stage1_address_tail <= address_tail;
end
С чтением всё понятно — есть значение, значит операция отработала. С записью примерно так же — было значение и послали запрос в память, который отработал — значит операция отработала.
wire stage1_read_ready = stage1_is_read && (memory_ready || stage1_hit);
wire stage1_write_ready = stage1_is_write && memory_ready && stage1_hit;
assign data_ready = stage1_read_ready || stage1_write_ready;
Выходное значение берётся в первую очередь из выходного регистра кэша, потому что память может ответить ready и на запись, то есть не вернув значение. К тому же из кэша значение возвращается уже модифицированным операцией записи.
wire [31:0] stage1_out_value = stage1_hit ? stage1_hit_value : memory_in;
assign data_out = stage1_read_ready ? (stage1_out_value >> stage1_address_tail * 8) : 32'hz;
И теперь делаем то, ради чего затевалась более сложная схема — пробрасываем это же значение назад в мультиплексор первого элемента кэша.
assign cache_value_0 = stage1_out_value;
assign cache_filled_0 = stage1_hit || memory_ready;
assign cache_can_update = stage1_is_read || stage1_is_write;
Изначально обновление кэша и наличие его первого значения казались синонимами, но потом оказалось, что без правильной логики кэш зависнет. Поэтому обновляем кэш сразу как только операция попробует совершиться, то есть на следующем такте, а выставляем флаг заполненности только тогда, когда она завершится успешно.
Шина
Теперь, когда кэш готов, его надо подключить к процессору и памяти. А поскольку кэшей 2, то надо выбрать, у кого из них приоритет выше. Приводить код целиком не буду, потому что там сплошные подключения, можно посмотреть в репозитории.
Основной код выглядит так.
// инструкции читаем в первую очередь
// мультиплексируем входы памяти
wire instruction_need = instruction_memory_read;
assign memory_address = instruction_need ? instruction_memory_address : data_memory_address;
assign memory_read = instruction_need ? instruction_memory_read : data_memory_read;
assign memory_write = instruction_need ? 0 : data_memory_write;
assign memory_out = data_memory_out;
// ответ на следующем такте, так что запоминаем, кому отвечать
reg stage1_instruction_need;
always@(posedge clock) begin
stage1_instruction_need <= reset ? 0 : instruction_need;
end
assign instruction_memory_ready = stage1_instruction_need && memory_ready;
assign data_memory_ready = !stage1_instruction_need && memory_ready;
То есть запросы от кэша инструкций имеют приоритет. Сейчас такой порядок выглядит предпочтительным, хотя возможно при появлении нескольких ядер это изменится. Пока память локальная, для записи можно завести ещё один адрес и писать туда без ожидания, всё равно порт записи выделяется отдельно от порта чтения.
В результате получается такая архитектура процессора. Выбор между памятью и периферией делается в коде SoC в зависимости от адреса.
Тесты
Наконец все ошибки отловлены, можно посмотреть на результаты трудов.
Так, например, выглядит вывод уже отформатированной строки на экран. Запрос к памяти делается каждый 4-й раз, когда байты в предыдущем слове закончатся. Почти все инструкции выполняются за 1 такт, потому что весь код попал в кэш.
2a80: 00e6a223 sw a4,4(a3) # 40000004
2a84: 0017c703 lbu a4,1(a5)
2a88: 00078513 mv a0,a5
2a8c: 00178793 addi a5,a5,1
2a90: fe0718e3 bnez a4,2a80 <ee_printf+0x80>
Ещё один пример — копирование одной строки в другую. Здесь запись тоже делается в память, поэтому запросы к памяти делаются 2 раза на 4 байта, а поскольку строки могут быть не выровнены на границу слова, эти запросы могут происходить на разных тактах.
2a48: 02500713 li a4,37
2a4c: 06e78263 beq a5,a4,2ab0 <ee_printf+0xb0>
2a50: 00f50023 sb a5,0(a0)
2a54: 00134783 lbu a5,1(t1)
2a58: 00150513 addi a0,a0,1
2a5c: 00130313 addi t1,t1,1
2a60: fe0794e3 bnez a5,2a48 <ee_printf+0x48>
А здесь можно убедиться, что кэш инструкций работает как надо, первые 7 адресов команд в цикле двигаются вниз, и в самом низу лежит команда, которая вызвалась последней перед началом цикла.
Это всё лучшие примеры, обычно никто никуда не попадает, потому что с 8 элементов толку не много. Но падения числа инструкций за такт почти нет, потому что не то чтобы память использовалась часто, и в основном проброс помогает.
Компиляция на ПЛИС
Напоследок посмотрим, что об этом думает Quartus.
Ну ладно, место на периферию и на другие эксперименты ещё осталось. Для кэша инструкций можно попробовать использовать DM + встроенные банки M9k, правда тогда на 4 ядра улетит 8 килобайт, потому что больше 32 бит в ширину из него почти не выдавишь, зато попаданий сразу станет много.