...

воскресенье, 28 июля 2019 г.

[Из песочницы] Имплементация кэша на 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;

Let's block ads! (Why?)

Комментариев нет:

Отправить комментарий