Проектирование надежного кольцевого буфера FIFO на VHDL в блочной ОЗУ

Кольцевые буферы — популярная конструкция для создания очередей в последовательных языках программирования, но их также можно реализовать в аппаратуре. В этой статье мы создадим кольцевой буфер на VHDL для реализации FIFO в блочной ОЗУ.

При реализации FIFO возникает множество проектных решений. Какой интерфейс вам нужен? Ограничены ли вы ресурсами? Должен ли он быть устойчивым к перечитыванию и перезаписи? Допустима ли задержка? Это лишь некоторые вопросы, которые встают перед инженером при создании FIFO.

Существует множество бесплатных реализаций FIFO в сети, а также генераторы FIFO, такие как Xilinx LogiCORE. Тем не менее, многие инженеры предпочитают реализовывать свои собственные FIFO. Даже если они все выполняют одни и те же базовые задачи очереди и извлечения, в деталях они могут кардинально отличаться.

Принцип работы кольцевого буфера

Кольцевой буфер — это реализация FIFO, использующая непрерывную память для хранения буферизованных данных с минимальным перемещением данных. Новые элементы остаются в одном и том же месте памяти от момента записи до чтения и удаления из FIFO.

Для отслеживания положения и количества элементов в FIFO используются два счетчика. Эти счетчики указывают на смещение от начала памяти, где хранятся данные. В VHDL это будет индекс ячейки массива. В дальнейшем мы будем называть эти счетчики указателями.

Эти два указателя — голова (head) и хвост (tail). Голова всегда указывает на ячейку памяти, которая будет содержать следующие записываемые данные, а хвост ссылается на следующий элемент, который будет прочитан из FIFO. Существуют и другие варианты, но мы будем использовать именно этот.

Пустое состояние

Если голова и хвост указывают на один и тот же элемент, это означает, что FIFO пуст. На изображении выше показан пример FIFO с восемью слотами. И голова, и хвост указывают на элемент 0, что указывает на пустоту FIFO. Это начальное состояние кольцевого буфера.

Обратите внимание, что FIFO все равно будет пустым, если оба указателя находятся на другом индексе, например, 3. При каждой записи указатель головы сдвигается на одну позицию вперед. Указатель хвоста увеличивается каждый раз, когда пользователь FIFO считывает элемент.

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

Голова опережает хвост

На изображении выше показан тот же кольцевой буфер после пяти записей. Указатель хвоста все еще на слоте 0, а указатель головы переместился на слот 5. Слоты, содержащие данные, выделены светло-голубым цветом. Указатель хвоста указывает на самый старый элемент, а голова — на следующий свободный слот.

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

Хвост опережает голову

Вычитание головы из хвоста работает только если голова опережает хвост. На изображении выше голова на индексе 2, а хвост — на индексе 5. Простое вычитание дает 2 - 5 = -3, что бессмысленно.

Решение — сместить голову на общее количество слотов в FIFO (в данном случае 8). Вычисление теперь дает (2 + 8) - 5 = 5, что является правильным ответом.

Хвост будет вечно преследовать голову — так работает кольцевой буфер. Половина времени хвост будет иметь больший индекс, чем голова. Данные хранятся между ними, как показано светло-голубым цветом на изображении выше.

Полное состояние

Полный кольцевой буфер будет иметь хвост, указывающий на индекс непосредственно за головой. Следствием этой схемы является то, что мы никогда не можем использовать все слоты для хранения данных — должен быть хотя бы один свободный слот. На изображении выше показана ситуация, когда кольцевой буфер полон. Открытый, но непригодный слот окрашен в желтый цвет.

Также можно использовать выделенный сигнал empty/full для указания того, что кольцевой буфер полон. Это позволило бы использовать все слоты памяти для хранения данных, но потребовало бы дополнительной логики в виде регистров и таблиц поиска (LUT). Поэтому мы будем использовать схему хранить один открытый для нашей реализации кольцевого буфера FIFO, так как это тратит только более дешевую блочную ОЗУ.

Реализация кольцевого буфера FIFO

То, как вы определяете интерфейсные сигналы к вашему FIFO и от него, ограничит количество возможных реализаций кольцевого буфера. В нашем примере мы будем использовать вариацию классического интерфейса с разрешениями на чтение/запись и флагами empty/full/valid.

На входной стороне будет шина write data, несущая данные для помещения в FIFO. Также будет сигнал write enable, который при установке заставит FIFO зафиксировать входные данные.

На выходной стороне будут сигналы read data и read valid, управляемые FIFO. Также будет сигнал read enable, управляемый нижестоящим пользователем FIFO.

Сигналы управления empty и full являются частью классического интерфейса FIFO, мы также их используем. Они управляются FIFO и их цель — сообщить состояние FIFO читателю и писателю.

Обратное давление (Back pressure)

Проблема ожидания, пока FIFO не станет пустым или полным, прежде чем предпринять действие, заключается в том, что интерфейсная логика не успеет отреагировать. Последовательная логика работает на основе такт к такту, фронты нарастающего тактового сигнала эффективно разделяют события в вашем проекте на временные шаги.

Одно из решений — включить сигналы almost empty и almost full, которые предшествуют исходным сигналам на один тактовый цикл. Это дает внешней логике время отреагировать, даже при непрерывном чтении или записи.

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

Сущность (Entity)

На изображении ниже показана сущность нашего кольцевого буфера FIFO. Помимо входных и выходных сигналов в порту, у нее есть две обобщенные константы. Обобщенная константа RAM_WIDTH определяет количество бит во входных и выходных словах, количество бит, которое будет содержать каждый слот памяти.

Обобщенная константа RAM_DEPTH определяет количество слотов, зарезервированных для кольцевого буфера. Поскольку один слот зарезервирован для указания того, что кольцевой буфер полен, емкость FIFO будет RAM_DEPTH - 1. Константа RAM_DEPTH должна соответствовать глубине ОЗУ на целевом ПЛИС. Неиспользуемая ОЗУ внутри примитива блочной ОЗУ будет потрачена зря, ее нельзя разделить с другой логикой в ПЛИС.

 entity ring_buffer is generic ( RAM_WIDTH : natural; RAM_DEPTH : natural ); port ( clk : in std_logic; rst : in std_logic; -- Write port wr_en : in std_logic; wr_data : in std_logic_vector(RAM_WIDTH - 1 downto 0); -- Read port rd_en : in std_logic; rd_valid : out std_logic; rd_data : out std_logic_vector(RAM_WIDTH - 1 downto 0); -- Flags empty : out std_logic; empty_next : out std_logic; full : out std_logic; full_next : out std_logic; -- The number of elements in the FIFO fill_count : out integer range RAM_DEPTH - 1 downto 0 ); end ring_buffer; 

Помимо тактового сигнала и сброса, объявление порта включает классические порты чтения и записи с данными и разрешениями. Они используются вышестоящими и нижестоящими модулями для помещения новых данных в FIFO и извлечения самого старого элемента из него.

Сигнал rd_valid устанавливается FIFO, когда порт rd_data содержит валидные данные. Это событие задерживается на один тактовый цикл после импульса на сигнале rd_en. Мы подробнее обсудим, почему это должно быть так, в конце статьи.

Затем идут флаги empty/full, устанавливаемые FIFO. Сигнал empty_next будет установлен, когда осталось 1 или 0 элементов, в то время как empty активен только когда в FIFO 0 элементов. Аналогично, сигнал full_next укажет, что есть место для 1 или 0 дополнительных элементов, в то время как full устанавливается только когда FIFO не может принять еще один элемент данных.

Наконец, есть выход fill_count. Это целое число, отражающее количество элементов, в данный момент хранящихся в FIFO. Я включил этот выходной сигнал просто потому, что мы используем его внутри модуля. Вывод его через сущность практически бесплатен, и пользователь может оставить этот сигнал не подключенным при инстанцировании этого модуля.

Область объявлений

В области объявлений VHDL-файла мы объявим пользовательский тип, подтип, ряд сигналов и процедуру для внутреннего использования в модуле кольцевого буфера.

 type ram_type is array (0 to RAM_DEPTH - 1) of std_logic_vector(wr_data'range); signal ram : ram_type; subtype index_type is integer range ram_type'range; signal head : index_type; signal tail : index_type; signal empty_i : std_logic; signal full_i : std_logic; signal fill_count_i : integer range RAM_DEPTH - 1 downto 0; -- Increment and wrap procedure incr(signal index : inout index_type) is begin if index = index_type'high then index <= index_type'low; else index <= index + 1; end if; end procedure; 

Сначала мы объявляем новый тип для моделирования нашей ОЗУ. Тип ram_type — это массив векторов, размер которого задается обобщенными входами. Новый тип используется на следующей строке для объявления сигнала ram, который будет хранить данные в кольцевом буфере.

В следующем блоке кода мы объявляем index_type, подтип integer. Его диапазон будет косвенно управляться обобщенной константой RAM_DEPTH. Ниже объявления подтипа мы используем индексный тип для объявления двух новых сигналов — указателей головы и хвоста.

Затем следует блок объявлений сигналов, которые являются внутренними копиями сигналов сущности. У них те же базовые имена, что и у сигналов сущности, но с суффиксом _i, чтобы указать, что они для внутреннего использования. Мы используем этот подход, потому что считается плохим стилем использовать режим inout для сигналов сущности, хотя это дало бы тот же эффект.

Наконец, мы объявляем процедуру incr, которая принимает сигнал index_type в качестве параметра. Эта подпрограмма будет использоваться для увеличения указателей головы и хвоста и их возврата к 0, когда они достигают наивысшего значения. Голова и хвост — подтипы integer, которые обычно не поддерживают поведение переноса. Мы используем процедуру для обхода этой проблемы.

Параллельные операторы (Concurrent statements)

В начале архитектуры мы объявляем наши параллельные операторы. Я предпочитаю собирать эти однострочные присваивания сигналов перед обычными процессами, потому что их легко упустить. Параллельный оператор — это на самом деле форма процесса, о параллельных операторах можно прочитать больше здесь:

Как создать параллельный оператор в VHDL

 -- Copy internal signals to output empty <= empty_i; full <= full_i; fill_count <= fill_count_i; -- Set the flags empty_i <= '1' when fill_count_i = 0 else '0'; empty_next <= '1' when fill_count_i <= 1 else '0'; full_i <= '1' when fill_count_i >= RAM_DEPTH - 1 else '0'; full_next <= '1' when fill_count_i >= RAM_DEPTH - 2 else '0'; 

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

Второй и последний блок параллельных операторов — это место, где мы присваиваем выходные флаги, сигнализирующие о полном/пустом состоянии кольцевого буфера. Мы основываем вычисления на обобщенной константе RAM_DEPTH и сигнале fill_count. Глубина ОЗУ — это константа, которая не будет меняться. Поэтому флаги будут меняться только в результате обновления счетчика заполнения.

Обновление указателя головы

Основная функция указателя головы — увеличиваться всякий раз, когда сигнал разрешения записи установлен извне этого модуля. Мы делаем это, передавая сигнал head в вышеупомянутую процедуру incr.

 PROC_HEAD : process(clk) begin if rising_edge(clk) then if rst = '1' then head <= 0; else if wr_en = '1' and full_i = '0' then incr(head); end if; end if; end if; end process; 

Наш код содержит дополнительное условие and full_i = '0' для защиты от перезаписи. Эта логика может быть опущена, если вы уверены, что источник данных никогда не попытается записать в FIFO, пока он полон. Без этой защиты перезапись приведет к тому, что кольцевой буфер снова станет пустым.

Если указатель головы увеличивается, пока кольцевой буфер полон, голова будет указывать на тот же элемент, что и хвост. Таким образом, модуль «забудет» содержащиеся данные, и заполнение FIFO покажется пустым.

Оценивая сигнал full_i перед увеличением указателя головы, он забудет только перезаписанное значение. Я считаю это решение более элегантным. Но в любом случае, если перезаписи когда-либо происходят, это указывает на неисправность вне этого модуля.

Обновление указателя хвоста

Указатель хвоста увеличивается подобным образом, как и указатель головы, но в качестве триггера используется вход read_en. Как и в случае с перезаписями, мы защищаемся от перечитываний, включая and empty_i = '0' в булевом выражении.

 PROC_TAIL : process(clk) begin if rising_edge(clk) then if rst = '1' then tail <= 0; rd_valid <= '0'; else rd_valid <= '0'; if rd_en = '1' and empty_i = '0' then incr(tail); rd_valid <= '1'; end if; end if; end if; end process; 

Дополнительно мы генерируем импульс сигнала rd_valid при каждом валидном чтении. Данные чтения всегда валидны на тактовом цикле после установки rd_en, если FIFO не был пуст. С этой знанием, в этом сигнале на самом деле нет необходимости, но мы включим его для удобства. Сигнал rd_valid будет оптимизирован при синтезе, если он останется не подключенным при инстанцировании модуля.

Вывод блочной ОЗУ

Чтобы заставить инструмент синтеза вывести блочную ОЗУ, мы должны объявить порты чтения и записи в синхронном процессе без сброса. Мы будем читать и писать в ОЗУ на каждом тактовом цикле, а сигналы управления будут управлять использованием этих данных.

 PROC_RAM : process(clk) begin if rising_edge(clk) then ram(head) <= wr_data; rd_data <= ram(tail); end if; end process; 

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

Обновление счетчика заполнения

Сигнал fill_count используется для генерации сигналов full и empty, которые в свою очередь используются для предотвращения перезаписи и перечитывания FIFO. Счетчик заполнения обновляется комбинационным процессом, чувствительным к указателям головы и хвоста, но эти сигналы обновляются только по фронту нарастающего тактового сигнала. Поэтому счетчик заполнения также изменится сразу после фронта тактового сигнала.

 PROC_COUNT : process(head, tail) begin if head < tail then fill_count_i <= head - tail + RAM_DEPTH; else fill_count_i <= head - tail; end if; end process; 

Счетчик заполнения вычисляется просто путем вычитания хвоста из головы. Если индекс хвоста больше головы, мы должны добавить значение константы RAM_DEPTH, чтобы получить правильное количество элементов, в данный момент находящихся в кольцевом буфере.

Полный VHDL-код кольцевого буфера FIFO

 library ieee; use ieee.std_logic_1164.all; entity ring_buffer is generic ( RAM_WIDTH : natural; RAM_DEPTH : natural ); port ( clk : in std_logic; rst : in std_logic; -- Write port wr_en : in std_logic; wr_data : in std_logic_vector(RAM_WIDTH - 1 downto 0); -- Read port rd_en : in std_logic; rd_valid : out std_logic; rd_data : out std_logic_vector(RAM_WIDTH - 1 downto 0); -- Flags empty : out std_logic; empty_next : out std_logic; full : out std_logic; full_next : out std_logic; -- The number of elements in the FIFO fill_count : out integer range RAM_DEPTH - 1 downto 0 ); end ring_buffer; architecture rtl of ring_buffer is type ram_type is array (0 to RAM_DEPTH - 1) of std_logic_vector(wr_data'range); signal ram : ram_type; subtype index_type is integer range ram_type'range; signal head : index_type; signal tail : index_type; signal empty_i : std_logic; signal full_i : std_logic; signal fill_count_i : integer range RAM_DEPTH - 1 downto 0; -- Increment and wrap procedure incr(signal index : inout index_type) is begin if index = index_type'high then index <= index_type'low; else index <= index + 1; end if; end procedure; begin -- Copy internal signals to output empty <= empty_i; full <= full_i; fill_count <= fill_count_i; -- Set the flags empty_i <= '1' when fill_count_i = 0 else '0'; empty_next <= '1' when fill_count_i <= 1 else '0'; full_i <= '1' when fill_count_i >= RAM_DEPTH - 1 else '0'; full_next <= '1' when fill_count_i >= RAM_DEPTH - 2 else '0'; -- Update the head pointer in write PROC_HEAD : process(clk) begin if rising_edge(clk) then if rst = '1' then head <= 0; else if wr_en = '1' and full_i = '0' then incr(head); end if; end if; end if; end process; -- Update the tail pointer on read and pulse valid PROC_TAIL : process(clk) begin if rising_edge(clk) then if rst = '1' then tail <= 0; rd_valid <= '0'; else rd_valid <= '0'; if rd_en = '1' and empty_i = '0' then incr(tail); rd_valid <= '1'; end if; end if; end if; end process; -- Write to and read from the RAM PROC_RAM : process(clk) begin if rising_edge(clk) then ram(head) <= wr_data; rd_data <= ram(tail); end if; end process; -- Update the fill count PROC_COUNT : process(head, tail) begin if head < tail then fill_count_i <= head - tail + RAM_DEPTH; else fill_count_i <= head - tail; end if; end process; end architecture; 

Код выше показывает полный код для кольцевого буфера FIFO. Вы можете заполнить форму ниже, чтобы мгновенно получить файлы проекта ModelSim и тестбенч на почту.

Тестбенч

FIFO инстанцируется в простом тестбенче для демонстрации его работы. Вы можете скачать исходный код тестбенча вместе с проектом ModelSim, используя форму ниже.

Обобщенные входы установлены в следующие значения:

• RAM_WIDTH: 16
• RAM_DEPTH: 256

Тестбенч сначала сбрасывает FIFO. Когда сброс освобождается, тестбенч записывает последовательные значения (1-255) в FIFO, пока он не наполнится. Наконец, FIFO опорожняется перед завершением теста.

Мы можем увидеть волновую форму для полного запуска тестбенча на изображении ниже. Сигнал fill_count отображается как аналоговое значение на волновой форме для лучшей иллюстрации уровня заполнения FIFO.

Голова, хвост и счетчик заполнения равны 0 в начале симуляции. В точке, где сигнал full устанавливается, голова имеет значение 255, и так же сигнал fill_count. Счетчик заполнения достигает только 255, даже у нас глубина ОЗУ 256. Это потому, что мы используем метод хранить один открытый для различения полного и пустого, как мы обсуждали ранее в этой статье.

В точке поворота, где мы прекращаем запись в FIFO и начинаем чтение из него, значение головы замораживается, а хвост и счетчик заполнения начинают уменьшаться. Наконец, в конце симуляции, когда FIFO пуст, и голова, и хвост имеют значение 255, а счетчик заполнения равен 0.

Этот тестбенч не следует считать адекватным ни для чего, кроме демонстрационных целей. У него нет поведения самопроверки или логики для верификации правильности выходных данных FIFO.

Мы будем использовать этот модуль в следующей статье, когда погрузимся в тему констрейнд рандом верификации. Это другая стратегия тестирования по сравнению с более распространенными направленными тестами. Кратко, тестбенч будет выполнять случайные взаимодействия с DUT (устройством под тестом), а поведение DUT должно быть проверено отдельным процессом тестбенча. Наконец, когда произойдет определенное количество предопределенных событий, тест завершается.

Нажмите здесь, чтобы прочитать следующую статью:
Констрейнд рандом верификация

Синтез в Vivado

Я синтезировал кольцевой буфер в Xilinx Vivado, потому что это самый популярный инструмент реализации ПЛИС. Однако он должен работать на всех архитектурах ПЛИС, имеющих двухпортовые блочные ОЗУ.

Нам нужно присвоить некоторые значения обобщенным входам, чтобы иметь возможность реализовать кольцевой буфер как отдельный модуль. Это делается в Vivado через меню Settings → General → Generics/Parameters, как показано на изображении ниже.

Значение для RAM_WIDTH установлено в 16, как и в симуляции. Но я установил RAM_DEPTH в 2048, потому что это максимальная глубина примитива RAMB36E1 в архитектуре Xilinx Zynq, которую я выбрал. Мы могли бы выбрать более низкое значение, но все равно использовалось бы то же количество блочных ОЗУ. Более высокое значение привело бы к использованию более чем одной блочной ОЗУ.

На изображении ниже показано использование ресурсов после реализации, согласно отчету Vivado. Наш кольцевой буфер действительно потребляет одну блочную ОЗУ и горсть LUT и триггеров.

Отказ от сигнала valid

Вы можете спросить себя, действительно ли необходима задержка в один тактовый цикл между сигналами rd_en и rd_valid. В конце концов, данные уже присутствуют на rd_data, когда мы устанавливаем rd_en. Не можем ли мы просто использовать это значение и позволить кольцевому буферу перейти к следующему элементу на следующем тактовом цикле при чтении из FIFO?

Строго говоря, нам не нужен сигнал valid. Я включил этот сигнал просто для удобства. Критически важная часть в том, что мы должны подождать до тактового цикла после установки сигнала rd_en, иначе ОЗУ не успеет отреагировать.

Блочная ОЗУ в ПЛИС — это полностью синхронные компоненты, им нужен фронт тактового сигнала как для чтения, так и для записи данных. Такты чтения и записи не обязаны приходить из одного источника, но должны быть фронты тактового сигнала. Кроме того, между выходом ОЗУ и следующим регистром (триггерами) не может быть логики. Это потому, что регистр, используемый для тактирования выхода ОЗУ, находится внутри примитива блочной ОЗУ.

На изображении выше показана временная диаграмма того, как значение распространяется от входа wr_data в нашем кольцевом буфере, через ОЗУ и наконец появляется на выходе rd_data. Поскольку каждый сигнал забирается по фронту нарастающего тактового сигнала, требуется три тактовых цикла от момента, когда мы начинаем управлять портом записи, прежде чем он появится на порту чтения. И еще один тактовый цикл проходит перед тем, как принимающий модуль сможет использовать эти данные.

Уменьшение задержки

Существуют способы смягчить эту проблему, но это идет ценой дополнительных ресурсов, используемых в ПЛИС. Давайте попробуем эксперимент, чтобы убрать один тактовый цикл задержки от порта чтения нашего кольцевого буфера. В фрагменте кода ниже мы изменили выход rd_data из синхронного процесса на комбинационный процесс, чувствительный к сигналам ram и tail.

 PROC_READ : process(ram, tail) begin rd_data <= ram(tail); end process; 

К сожалению, этот код не может быть отображен на блочную ОЗУ, потому что между выходом ОЗУ и первым нижестоящим регистром на сигнале rd_data может быть комбинационная логика.

На изображении ниже показано использование ресурсов, согласно отчету Vivado. Блочная ОЗУ была заменена на LUTRAM; форму распределенной ОЗУ, реализованной в LUT. Использование LUT взлетело с 37 до 947. Таблицы поиска и триггеры дороже, чем блочная ОЗУ, именно поэтому у нас и есть блочная ОЗУ.

Существует много способов реализовать кольцевой буфер FIFO в блочной ОЗУ. Вы можете сэкономить лишний тактовый цикл, используя другой дизайн, но это будет стоить в виде дополнительной поддерживающей логики. Для большинства приложений кольцевой буфер, представленный в этой статье, будет достаточен.

Обновление:
Как создать кольцевой буфер FIFO в блочной ОЗУ с использованием рукопожатия AXI ready/valid

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

Нажмите здесь, чтобы прочитать следующую статью:
Констрейнд рандом верификация