Имплементация кэша на Verilog

В данной статье разбор простейшей реализации RAM на языке Verilog.

Перед тем, как перейти к разбору кода, рекомендуется изучить базовый синтаксис языка Verilog.

Здесь вы можете найти обучающие материалы.

RAM


Шаг 1: объявление модуля с соответствующими входными/выходными сигналами


module ram (
	input [word_size - 1:0] data,
	input [word_size - 1:0] addr,	
	input wr,	
	input clk,	
	
	output response,
	output [word_size - 1:0] out
);		

parameter word_size = 32;

  • data — данные для записи.
  • addr — адрес к участку памяти в RAM.
  • wr — статус (считывание/запись).
  • clk — clock cycle системы.
  • response — готовность RAM (1 — если RAM обработал запрос на считывание/запись, 0 — в противном случае).
  • out — данные, считанные из RAM.

Данная реализация интегрировалась в FPGA Altera Max 10, которая имеет 32 разрядную архитектуру, в связи с чем размер для данных и адреса(word_size) 32 бита.

Шаг 2: объявление регистров внутри модуля


Объявление массива для хранения данных:

parameter size = 1<<32;
reg [word_size-1:0] ram [size-1:0];

Также нам понадобится хранить предыдущие входные параметры с целью отслеживания их изменений в always блоке:

reg [word_size-1:0] data_reg;	
reg [word_size-1:0] addr_reg;
reg wr_reg;

И последние два регистра для обновления выходных сигналов после вычислений в always блоке:

reg [word_size-1:0] out_reg;
reg response_reg;

Инициализируем регистры:

initial
begin	
	response_reg = 1;
	data_reg = 0;
	addr_reg = 0;
	wr_reg = 0;
end

Шаг 3: реализация логики always блока


always @(negedge clk)
begin		
	if ((data != data_reg) || (addr%size != addr_reg)|| (wr != wr_reg))
	begin
		response_reg = 0;
		data_reg = data;
		addr_reg = addr%size;
		wr_reg = wr;
	end
	else
	begin
		if (response_reg == 0)
		begin
			if (wr)
				ram[addr] = data;
			else
				out_reg = ram[addr];
				
			response_reg = 1;
		end
	end
end

Always блок срабатывает на negedje, т.е. в момент перехода clock-а с 1 на 0. Это сделано для правильной синхронизации RAM-а c кэшем. Иначе возможны случаи, когда RAM не успевает сбросить статус готовности с 1 на 0 и на следующем clock-е кэш решает, что RAM благополучно обработал его запрос, что в корне неверно.

Логика алгоритма always блока такова: если данные обновлены, сбрасываем статус готовности на 0 и записываем/считываем данные, если запись/считывание выполнены, обновляем статус готовности на 1.

В конце добавляем следующий участок кода:

assign out = out_reg;
assign response = response_reg;

Тип выходных сигналов нашего модуля — wire. Единственный способ изменения сигналов данного типа — долгосрочное присваивание, являющееся запрещённым внутри always блока. По этой причине в always блоке используются регистры, которые в дальнейшем присваиваются выходным сигналам.

Direct mapping cache


Direct mapping cache — один из наиболее простых видов кэша. В данной реализации кэш состоит из n элементов, а RAM условно делится на блоки по n, тогда i-ому элементу в кэше соответствуют все такие k-ые элементы в RAM, удовлетворяющие условию i = k % n.

На приведённом ниже рисунке изображён кэш размером 4 и RAM размером 16.



Каждый элемент кэша содержит следующую информацию:

  • бит валидности — является ли информация в кэше актуальной.
  • тэг — номер блока в RAM, где находится этот элемент.
  • данные — информация, которую мы записываем/считываем.

При запросе на считывание кэш делит входной адрес на две части — тэг и индекс. При этом размер индекса — это log(n), где n — это размер кэша.

Шаг 1: объявление модуля с соответствующими входными/выходными сигналами


module direct_mapping_cache 
(	
	input [word_size-1:0] data,	
	input [word_size-1:0] addr,
	input wr,	
	input clk,	
	
	output response,	
	output is_missrate,	
	output [word_size-1:0] out
);	
	parameter word_size = 32;

Объявление модуля кэша идентично RAM-у, за исключением нового выходного сигнала is_missrate. Этот выходной сигнал хранит информацию о том, был ли последний запрос на считывание missrate-ом.

Шаг 2: объявление регистров и RAM-а


Перед тем, как объявить регистры, определим размеры кэша и индекса:

parameter size = 64;
parameter index_size = 6;

Далее, объявляем массив, в котором и будут храниться данные, которые мы записываем и считываем:

reg [word_size-1:0] data_array [size-1:0];

Также нам нужно хранить биты валидности и тэги для каждого элемента в кэше:

reg validity_array [size-1:0];		
reg [word_size-index_size-1:0] tag_array [size-1:0];
reg [index_size-1:0] index_array [size-1:0];

Регистры, в которые будет разбит входной адрес:

reg [word_size-index_size-1:0] tag;
reg [index_size-1:0] index;

Регистры, хранящие в себе входные значения на предыдущим clock-е(для отслеживания изменений входных данных):

reg [word_size-1:0] data_reg;
reg [word_size-1:0] addr_reg;
reg wr_reg;

Регистры для обновления выходных сигналов после вычислений в always блоке:

reg response_reg;
reg is_missrate_reg;
reg [word_size-1:0] out_reg;

Входные значения для RAM:

reg [word_size-1:0] ram_data;
reg [word_size-1:0] ram_addr;
reg ram_wr;

Выходные значения для RAM:

wire ram_response;
wire [word_size-1:0] ram_out;

Объявление модуля RAM и подключение входных и выходных сигналов:

ram ram(
	.data(ram_data),
	.addr(ram_addr),			
	.wr(ram_wr),
	.clk(clk),			
	.response(ram_response),
	.out(ram_out));

Инициализация регистров:

initial
integer i
initial
begin		
	data_reg = 0;
	addr_reg = 0;
	wr_reg = 0;
	for (i = 0; i < size; i=i+1)
	begin
		data_array[i] = 0;
		tag_array[i] = 0;
		validity_array[i] = 0;			
	end
end

Шаг 3: реализация логики always блока


Начнём с того, что на каждый clock у нас есть два состояния — входные данные изменены, либо не изменены. Исходя из этого мы имеем следующее условие:

always @(posedge clk)
begin
	if (data_reg != data || addr_reg != addr || wr_reg != wr)
	begin
	end				
		//Блок 1: входные данные изменены
	else
	begin
		//Блок 2: входные данные не изменены
	end
end

Блок 1. В случае, если входные данные изменены, первым делом мы сбрасываем статус готовности на 0:

response_reg = 0;

Далее мы обновляем регистры, хранившие входные значения предыдущего clock-а:

data_reg = data;
addr_reg = addr;
wr_reg = wr;

Разбиваем входной адрес на тэг и индекс:

tag = addr >> index_size;
index = addr;

Для вычисления тэга используется побитовый сдвиг вправо, для индекса достаточно просто присвоить, т.к. лишние разряды адреса не учитываются.

Следующий шаг — выбор между записью и считыванием:

if (wr)
begin
	// запись
	data_array[index] = data;
	tag_array[index] = tag;			
	validity_array[index] = 1;

	ram_data = data;
	ram_addr = addr;
	ram_wr = wr;
end
else
begin
	// считывание
	if ((validity_array[index]) && (tag == tag_array[index]))
	begin
		// найден в кэше
		is_missrate_reg = 0;

		out_reg = data_array[index];
		response_reg = 1;
	end
	else
	begin
		// не найден в кэше
		is_missrate_reg = 1;

		ram_data = data;
		ram_addr = addr;
		ram_wr = wr;			
	end
end

В случае записи первоначально мы изменяем данные в кэше, затем обновляем входные данные для RAM-а. В случае считывания мы проверяем наличие данного элемента в кэше и, если он есть, записываем его в out_reg, в противном случае обращаемся в RAM.

Блок 2. Если данные не были изменены с момента выполнения предыдущего clock-а, то мы имеем следующий код:

if ((ram_response) && (!response_reg))
begin
	if (wr == 0)
	begin
		validity_array [index] = 1;
		data_array [index] = ram_out;
		tag_array[index] = tag;
		out_reg = ram_out;
	end
	response_reg = 1;
end

Здесь мы ждём окончания выполнения обращения в RAM(в случае если обращения не было, ram_response равен 1), обновляем данные, если была команда на считывание и устанавливаем готовность кэша на 1.

И последнее, обновляем выходные значения:

assign out = out_reg;
assign is_missrate = is_missrate_reg;
assign response = response_reg;

Комментарии 12

    +4
    Везде блокирующие присвоения… negedge clk (уже молчу про отсутствие сброса), не, надо бы ещё поработать над кодом.

    ЗЫ. И да:
    >> Данная реализация интегрировалась в FPGA Altera Max 10, которая имеет 32 разрядную архитектуру, в связи с чем размер для данных и адреса(word_size) 32 бита.
    Эм, как это ПЛИС может иметь 32-разрядную архитектуру?
      0
      Возможные конфигурации блоков памяти (из PDF про блоки памяти M9K на Макс 10):
      8192 × 1
      4096 × 2
      2048 × 4
      1024 × 8
      1024 × 9
      512 × 16
      512 × 18
      256 × 32
      256 × 36

      Но даже если вы попросите 48-бит или 64-ре то компилятор за вас объединит несколько в один блок.
      Для старта очень полезно смотреть что же там нагородил компилятор в Technology Map и тогда будет например четко видно в чем разница в использовании блокирующего и не блокирующего присваивания в блоке always с posedge.
        0
        Меня тоже это сначала смутило, однако, статическая ячейка памяти содержит 2 инвертора и 2 ключа. Ни защелок, ни триггеров там не наблюдается. Более того, память со случайным доступом не инициализируют. Мы либо записали туда полезные данные, либо сами дураки, что полезли читать из незаписанной ячейки.
        0

        Здравствуйте, а Вы тестировали то, что Вы написали? Хотелось бы увидеть общий код написанного Вами кэша помимо его отдельных частей, разбросанных по статье.

          0
          После инициализации регистров через блок Initial дальше читать не стал…
            0
            Если код для ПЛИС, то почему нет?
              +1
              Потому что Initial не синтезируемая конструкция. В железе это не работает, пригодно только для моделирования. Немного уточню, не синтезируется присвоение начальных значений регистрам через Initial, а вот так сделать можно:

              initial
              begin
              $readmemb(«ram.txt», ram);
              end
                0
                Чем ПЛИС не железо? На ПЛИС работает. Автор же код не для ASIC делает.
                Да и не в ASIC даже дело. Раз уж речь про «железо» так память и кеш никто не синтезирует сейчас из верилог.
                  +1
                  Конструкция initial reg_name = 1 при синтезе в ПЛИС или ASIC даст вам после подачи питания reg_name = 0, так как синтезатору класть что вы там через initial хотите присвоить регистру. И открою вам великую тайну, все процессоры, и любые другие ASIC/SoC именно на Verilog/VHDL/SystemVerilog сейчас и синтезируют.
                    0
                    После подачи питания на ПЛИС, там нет reg_name, он появится потом, когда будет загружена конфигурация. После загрузки конфигурации, он появится и будет = 1.
                    Что касается второй части Вашего комментария, Вы хотели сказать моделируют, а синтезируют — компиляторы и роутеры :) И да, синтезировать целый процессор можно, но он никогда не будет работать с той частотой к которой мы привыкли.
                      +1
                      Само собой после загрузки конфигурации. А вот 1 он будет равен далеко не всегда, не все компиляторы поддерживают инициализацию через Initial, и не все модели ПЛИС. Иными словами, такой код не является универсальным и хорошо переносимым. А второй частью своего комментария я хотел сказать, что описание любого современного процессора или SoC, в любом случае, делается на HDL, в не зависимости от того, собираетесь ли вы его реализовывать на ПЛИС, ASIC или БМК.
            0
            Шаг 2: объявление регистров внутри модуля

            Это не регистры! Это тип данных reg, переменные этого типа должны стоять с левой стороны процедурных присваиваний. В SystemVerilog этот тип называется logic именно ради избегания подобной путаницы.
            долгосрочное присваивание

            В русскоязычной литературе используется термин «непрерывное присваивание»

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое