У разных электронных компаний вопросы на интервью немного отличаются. В одной интервьюер на скрининге (первом интервью) спросит кандидата на RTL позицию про конечный автомат, в другой про арбитр, кэш или конвейер, в третьей про упорядочение неупорядоченных транзакций. Но на большом интервью вопрос про очередь FIFO появится практически всегда - не первым/вторым, но третьим.
Это может быть элементарный вопрос "напишите на доске (физической, ха-ха, без доступа к интернету и ChatGPT) код для FIFO на D-триггерах". Или это может быть обсуждение микроархитектуры какого-нибудь извращенного FIFO, например FIFO с отменой вталкиваний, или с возможностью втолкнуть и вытолкнуть переменное количество кусков данных за такт, или с конвейером и кредитным счетчиком, или работающее на памяти с высокой латентностью, или асинхронное FIFO из статьи Клиффа Каммингса про пересечение тактового домена.
Эта заметка является сиквелом заметки "FIFO для самых маленьких", а также приквелом занятия в Школе синтеза цифровых схем в ближайшую субботу. Главное нововведение - все примеры и упражнения теперь делаются не только в симуляторе, но и на плате ПЛИС.
Новости Школы Синтеза и об авторах занятия
К Школе Синтеза присоединился двенадцатый участник - Томский Государственный Университет. На карте 11 кружочков, но в Москве две площадки - ВШЭ МИЭМ и МИРЭА:
В субботу сначала преподаватели зеленоградского МИЭТ Александр Силантьев и Евгений Примаков расскажут про внутреннюю структур ячеек ПЛИС, с ручным синтезом дизайна из них, а потом пройдет часть про FIFO. Занятие будет как всегда транслироваться на ютюбе с обсуждением в телеграме.
Занятие по FIFO проведет Владимир Ефимов, новый преподаватель Школы. Материалы готовили Рафаэль Ильясов и Андрей Зыков из казанского Иннополиса (анимации работы FIFO), преподаватель Самарского Университета Илья Кудрявцев (обзорная лекция по FIFO в прошлом году) и ваш покорный слуга (примеры кода). Мы также посматривали на слайды декана Черниговского Политехнического Университета Сергея Иванца, который делал презентацию про FIFO год назад.
Подготовка: Git и клонирование
Раньше примеры для школы скачивались в виде zip-файлов, но теперь мы решили приучать будущих разработчиков к системе управления версиями git. На Линуксе она либо стоит изначально, либо устанавливается с помощью менеджера пакетов.
Под Linux основанном на Debian (Ubuntu, Lubuntu, Astra Linux, Green Linux), а также под Linux ALT и Simply Linux, установка git делается с помощью:
sudo apt-get install gitПод РедОС и Rosa Linux - git вроде уже стоит, но если нет, его можно поставить таким же образом, только вместо "apt-get" использовать "yum" и "dnf" соответственно.
Под Windows git можно скачать, после чего во время установки поставить вместе с ним разные линуксные утилиты, которые нам пригодятся для запуска скриптов на баше:
Теперь вы можете клонировать репозиторий с примерами:
git clone https://gitflic.ru/project/yuri-panchul/valid-ready-etc.gitЕсли в процессе работы что-то пойдет не так, и вы заподозрите, что файлы в репозитории неправильные, вы можете клонировать более старую версию с тегом:
git clone -b v0.3-alpha https://gitflic.ru/project/yuri-panchul/valid-ready-etc.gitНедостаток клонирования с тегом: в то время как после обычного клонирования последней версии вы можете обновить файлы для следущих занятий с помощью простого "git pull", в версии с тегом вам нужно будет или клонировать новое дерево в новое место, или делать какие-то пляски с бубном, которые я не пробовал.
Важно!!! После скачивания вы обнаружите, что ни одно из упражнений не работает. Это так и задумывалось. Чтобы научиться писанию кода на верилоге, нужно не только читать, но и писать. Примеры заработают, когда вы их допишете - в некоторых достачно дописать три строчки, в других - страницу. Места, которые нужно дописывать, обозначены комментарием "// TODO".
Анимации и демонстрации
Вот как FIFO выглядит с точки зрения пользователя, то есть проектировщика, который вставляет FIFO в свой блок:
Это же можно увидеть на FPGA плате с помощью упражнения valid-ready-etc/boards/01_flip_flop_fifo/08_fifo_with_better_debug_1 . В видео Владимир Ефимов часто употребляет термин "буфер" как синоним "очереди FIFO". В общем случае это не синонимы, но вы предупреждены:
Важно понимать, что очередь FIFO - это не сдвиговый регистр. Чтобы объяснить эту разницу, среди упражнений есть и пример с сдвиговым регистром valid-ready-etc/boards/01_flip_flop_fifo/07_shift_register_to_compare . Анимация:
и на плате:
Другая пара анимации и демо на плате показывает, как FIFO реализовано внутри - с помощью указателей для записи и для чтения. В FIFO, в отличие от сдвигового регистра, перемещаются указатели, а не данные:
а теперь это же на плате в примере valid-ready-etc/boards/01_flip_flop_fifo/09_fifo_with_better_debug_2 :
Однако все три примера выше не только сознательно недописаны в публичном дистрибутиве, но еще и реализованы только для платы Terasic DE10-Lite. В то время как большинство участников Школы используют платы Omdazz или RzRd (Omdazz и RzRd отличаются друг от друга только порядком подсоединения ножек FPGA к светодиодам на плате). Для Omdazz мы будеи использовать в качестве базового пример valid-ready-etc/omdazz/01_flip_flop_fifo/01_flip_flop_fifo_with_counter_and_slow_clock , в котором на семисегментный индикатор выводятся, слева направо:
Бегущий счетчик, числа из которого будут запихиваться в FIFO.
Положение указателя записи, write pointer.
Точка у положения указателя записи, которая означает, что FIFO наполнено.
Положение указателя чтения, read pointer.
Точка у положения указателя чтения, которая означает, что FIFO пусто.
Значение верхушки FIFO, которое будет вытолкнуто следующим pop-ом.
Аналогичное упражнение на плате DE10-Lite выглядит похоже:
Медленный тактовый сигнал (clock) или сигнал разрешения (enable)?
Вы не могли не заметить, что как счетчик на входе FIFO, так и само FIFO работает отнюдь не на частоте 50 мегагерц (которую генерирует кварцевый генератор на плате), а скорее на частоте 1 герц. Как мы это сделали? PLL (если вы знаете что это такое) снизить частоту с 50 мегагерц до 1 герца не может.Поэтому мы действовали методом хоббистов - делили тактовый сигнал счетчиком - но с некоторым профессиональным улучшением. А именно: мы пропустили поделенный сигнал через специальный альтеровский примитив под названием global (в Xilinx его аналог называется BUFG), чтобы Quartus понял, что этот сигнал является тактовым, и пустил его по специальным соединениями для тактовых сигналов (clock tree). Без такого улучшения схему может глючить, я наблюдал такой эффект со схемой процессора.
Если вы не поняли, что написано в предыдущем абзаце, не волнуйтесь - это может вам объяснить Владимир Ефимов на занятии. А если не объяснит, то это неважно - я никогда не видел такой метод получения тактового сигнала в промышленных дизайнах, это трюк чисто для демо. Просто примите, что в FIFO для игры с ним на плате используется тактовый сигнал с частотой 1-2 герца, то бишь 1-2 биения в секунду. В коде это выглядит так:
module slow_clk_gen
# (
parameter w = 24
)
(
input clk,
input rst,
output slow_clk_raw
);
wire [w - 1:0] cnt;
counter # (w) i_counter (.cnt (cnt), .*);
// Note! You have to pass this clock though
// "global" primitive in Intel FPGA
// or BUFG primitive in Xilinx Vivado
assign slow_clk_raw = cnt [w - 1];
endmodule
module fpga_top
(
input clk,
. . . . . . . . .
wire slow_clk_raw, slow_clk;
slow_clk_gen # (26) i_slow_clk_gen (.slow_clk_raw (slow_clk_raw), .*);
// "global" is Intel FPGA-specific primitive to route
// a signal coming from data into clock tree
global i_global (.in (slow_clk_raw), .out (slow_clk));
. . . . . . . . .
flip_flop_fifo_with_counter
# (
.width (fifo_width),
.depth (fifo_depth)
)
i_fifo (.clk (slow_clk), .*);А можно сделать то же самое демо с FIFO, но без трюка с счетчиком и global? Если в промышленном дизайне проектировщик хочет замедлить получение данных, то корректный способ это сделать - это генерация сигнала разрешения, enable. В нашем случае это пульс на 1 такт 50-мегагерцового тактового сигнала, раз в секунду. Мы реализовали такое решение в valid-ready-etc/boards/omdazz/01_flip_flop_fifo/06_flip_flop_fifo_with_counter_and_clock_enable . Однако для демо оно неудобно, так как требует изменение внутренностей самого FIFO - добавления "if (enable)" внутри всех "always @ (posedge clk".
Философское отступление и тандем из FIFO
При обучении хардверному дизайну полезно знать, что для ученика может быть контринтуитивным. Это собственно и есть места, для которых нужен преподаватель, все остальное ученик выучит по книгам или догадается.
Например, по интуиции из программирования ученик может твердо подразумевать, что для чтения из очереди FIFO ему нужно сначала послать запрос (сделать сигнал pop=1), а потом получить ответ (прочитанное данное в следующем такте).
На самом деле для построения самого широко используемого FIFO на D-триггерах ментальная картина должна быть другой: данное к моменту pop на верхушке FIFO уже лежит и сигнал pop означает "я данное увидел, можешь о нем забыть, и пока я его обрабатываю, подгони на верхушку следующее данное".
У FIFO построенного таким образом есть очень полезное свойство: если поставить два таких FIFO друг за другом и просто соединить их проводами, то они будут функционировать как одно FIFO , без потери пропускной способности. В дизайне же "pop запрос-ответ"возникают всякие головные боли с написанием связывающей (glue) логики и с пропускной способностью.
Мы проиллюстрировали этот тезис упражнением valid-ready-etc/boards/omdazz/01_flip_flop_fifo/04_two_ff_fifos_back_to_back
FIFO с глубиной, равной степени двойки, и его обобщение
Для FIFO с глубиной, равной степени двойки, можно не проверять указатели при их увеличении на 1. Для этого случая также есть простая схема для определения состояний empty и full без счетчика.
valid-ready-etc/boards/omdazz/01_flip_flop_fifo/02_ff_fifo_pow2_depth
valid-ready-etc/boards/de10_lite/01_flip_flop_fifo/02_ff_fifo_pow2_depth
Почему-то во время интервью многие студенты на вопрос "напишите FIFO" пишут именно такое. А на вопрос "а это будет работать, если глубина FIFO - не степень двойки?" - задумываются. Кто виноват? Преподаватели? Случайно нагугленные тьюториалы где разбирается только такой частный случай?
Оправдание "мы просто хотели съэкономить логику за счет лишних D-триггеров" - не катит, так как для FIFO в пару тысяч D-триггеров потери от увеличения FIFO с глубины скажем 35 до глубины 64 при ширине скажем 50 бит - будет около полутора тысяч D-триггеров на ровном месте. Это плохо, так как D-триггеры - это не только место на кристалле, но и динамическое энергопотребление.
Особенно если у вас таких FIFO в дизайне сотни или тысячи. Потом у телефонов будут быстро садиться батарейки, а чипы для магистральных роутеров будут требовать специального жидкостного охлаждения.
(Упражнения по расчету необходимых размеров FIFO будут в Школе на одном из следующих занятий - для этого например используются данные о латентностях конвейеров и блоков статической памяти)
С другой стороны, можно обобщить идею из FIFO с глубиной степени двойки для оптимизации empty/full и для FIFO не с глубиной степени двойки, что мы и сделаем в следующем упражнении:
valid-ready-etc/boards/de10_lite/01_flip_flop_fifo/03_flip_flop_fifo_empty_full_optimized
valid-ready-etc/boards/omdazz/01_flip_flop_fifo/03_flip_flop_fifo_empty_full_optimized
Комбинационная логика после регистров - можно ли ее убрать?
В коде тестового окружения упражнений по FIFO вы могли заметить задержку #1. Она необходимо потому, что у нашего FIFO не все выводы выходят из регистров - после них есть еще немного комбинационной логики, в частности для вычисления признаков empty/full.
Но эти сигналы можно сделать и выходящими из регистров. Этому посвящено упражнение, которое Владимир Ефимов хочет предложить в качестве домашнего задания после субботнего занятия - valid-ready-etc/boards/01_flip_flop_fifo/05_ff_fifo_with_reg_empty_full
Вопрос по FIFO не для джунов, а для миддлов
Я же предлагаю в качестве домашнего задания следующий вопрос: напишите FIFO, в которое в одном такте можно было бы втолкнуть или один, или два куска данных, и вытолкнуть или один, или два куска данных. Причем данные образуют одну цепочку, это не два независимых канала. В обобщенном виде заголовок такого модуля должен выглядеть так:
module multi_push_multi_pop_fifo
# (
parameter w = 13, // fifo width
d = 19, // fifo_depth
n = 2, // max number of pushes or pops
nw = $clog2 (n + 1)
)
(
input clk,
input rst,
input [nw - 1:0] push,
input [n - 1:0][w - 1:0] push_data,
input [nw - 1:0] pop,
output [n - 1:0][w - 1:0] pop_data,
output [nw - 1:0] can_push, // how many items can I push
output [nw - 1:0] can_pop
);
// TODO: Implement the whole example
// with testbench and FPGA demo
endmoduleЕсли вы напишете функционально корректное красивое решение для N > 2 с полной верификацией, разумными результатами static timing analysis, разумным расходованием D-триггеров и демо на FPGA плате, то мне (и наверное не только мне) было бы интересно помотреть на ваше резюме. Но и для N = 2 тоже присылайте, я покритикую.
Как можно еще потренироваться
Как я уже упоминал, часть упражнений сделана только для платы Omdazz/RzRd, а другая - только для платы Terasic DE10-Lite. Для тех или иных студентов может быть хорошим упражнением перенести все упражнения на все платы, причем не только эти две, но еще и на:
ZEOWAA - я в свое время отправил ящик таких плат в казанский Иннополис, а пару месяцев назад я еще и нашел десяток таких плат у себя в гараже. Оказалось, что я заказал их еще в 2019 году, они пришли по почте в мое отсутствие и я о них забыл. Хотя эти платы больше не выпускаются, но я собираюсь использовать этот ящик для своих будущих семинаров, так как сами по себе платы достаточные.
PisWords-06 - я оставил несколько таких плат в Бишкекском университете АУЦА. Они, как и Zeowaa, больше не выпускаются, но те, что есть можно применять.
Tang Primer 20K - новая модная плата с китайским ПЛИС GoWin.
Digilent Nexys A7 - FPGA от Xilinx. Используется многими мировыми университетами, у меня тоже есть.
Digilent Basys3 - более дешевая плата от Xilinx, чем Nexys A7.
Приложение. Описание занятия в субботу
Весенний семестр: от базовых знаний - к профессиональным умениям
28 января ПЛИС изнутри и очереди FIFO
На этом занятии мы рассмотрим две темы, каждая по полтора-два часа.
Сначала мы изучим, как устроена микросхема ПЛИС внутри. Мы рассмотрим ее ячейки, которые состоят из элементов LUT (LookUp Table), D-триггеров и мультиплексоров; изучим, как эти ячейки соединяются и конфигурируются. Зачем мы изучим структуру блочной памяти и выполним упражнение по синтезу схемы “вручную”, используя макросы для ПЛИС Intel FPGA.
Вторая тема нашего занятия - это реализация очередей FIFO (First In First Out), ключевых блоков проектирования. Многие схемы в промышленности представляют из себя смесь из конвейеров для арифметических вычислений, соединенных очередями FIFO. Мы рассмотрим реализацию FIFO на D-триггерах и выполним упражнения на локальные оптимизации: FIFO с глубиной степени двойки и построение логики для empty/full без счетчика.
Одновременно с реализацией очереди FIFO в RTL мы изучим, как моделировать FIFO с помощью структуры данных “очередь” в SystemVerilog (queue[$]) и как использовать такую модель для создания динамического тестового окружения (dynamic testbench).
Мы также продемонстрируем работу FIFO на плате ПЛИС, где вы сможете вталкивать в FIFO и выталкивать из него числа кнопками. Для демонстрации мы покажем, как искусственно замедлять тактовый сигнал до частоты 1 герц, или контролировать операции одногерцовым сигналом разрешения. Мы будем отображать головной и хвостовой элементы FIFO, а также статусы “полное” и “пустое”, на семисегментном индикаторе.
Перед этим занятием может быть полезно пересмотреть обзорную лекцию Ильи Кудрявцева про FIFO с занятия 19 ноября 2022. На этом и следующих занятиях мы будем неоднократно возвращаться к темам, затронутым в лекции, но перенесем фокус с теории на практику.
В качестве домашнего задания вы получите вопрос с реального интервью: реализовать FIFO, которое позволяет запись в него или одного, или двух элементов за один такт, так же как и чтение или одного или двух элементов.
Решение не должно заставлять пользователя FIFO думать, какое данное уже записано, а какое нет. FIFO должно сообщать, есть ли в нем место для одного или двух элементов и потом принимать эти данные. FIFO также не должно расходовать D-триггеры на незаписанную информацию, если в течение многих тактов пишется только один элемент. Если в течение двух тактов писалось по одному элементу, FIFO должно позволить прочитать их сразу за один такт. Также если два элемента были записаны сразу, FIFO должно позволить их читать по одному. Если было записано два, а потом один, FIFO должно позволять читать их любым способом - три чтения по одному, или прочитать два а потом один, или прочитать один, а потом два.
Мы ждем от вас реализацию такого FIFO как в симуляции, так и на FPGA плате. Можете ли вы обобщить эту задачу на чтение и запись от 1 до N элементов за такт?
Больше информации - на сайте Школы Синтеза Цифровых Схем
Ждем вас на школе и онлайн!
Комментарии (33)
gchebanov
27.01.2023 18:35input [nw - 1:0][w - 1:0] push_data, output [nw - 1:0][w - 1:0] pop_data,должно быть так, забавно что для n=2 это не одно и то же.
input [n - 1:0][w - 1:0] push_data, output [n - 1:0][w - 1:0] pop_data,
YuriPanchul Автор
27.01.2023 19:12+1Ой! Точно! Спасибо за исправление
Craybird
28.01.2023 20:28а всё ли в порядке с разрядностью тут?
input [nw - 1:0] push, ... ... input [nw - 1:0] pop,при n=2 получается, что nw=1, а push и pop становятся однобитными
YuriPanchul Автор
28.01.2023 20:31Ой, совсем в затуманеном состоянии головы задачу писал.
Надо было написать nw = $clog2 (n + 1)
Спасибо!
datacompboy
27.01.2023 18:53Вот вы прямо заинтересовали меня...
VHDL
》Hi, Gapty! Could you, please, write me an example of FIFO queue on a VHDL or Verilog using D-triggers?
》Sure! Here's an example of a FIFO queue implemented in VHDL using D-triggers:
-- FIFO queue using D-triggers library IEEE; use IEEE.STD_LOGIC_1164.ALL; entity fifo_queue is generic ( data_width : integer := 8; -- width of data depth : integer := 16 -- depth of queue ); port ( clk : in std_logic; -- clock input reset : in std_logic; -- reset input enq_data : in std_logic_vector(data_width-1 downto 0); -- data to be enqueued enq_en : in std_logic; -- enable for enqueue operation deq_en : in std_logic; -- enable for dequeue operation empty : out std_logic; -- output indicating if queue is empty full : out std_logic; -- output indicating if queue is full deq_data : out std_logic_vector(data_width-1 downto 0) -- dequeued data ); end fifo_queue; architecture rtl of fifo_queue is type memory_type is array (0 to depth-1) of std_logic_vector(data_width-1 downto 0); signal memory : memory_type; signal read_ptr, write_ptr : integer range 0 to depth-1; signal enq_full, deq_empty : std_logic; begin -- D-triggers for read and write pointers read_ptr_proc : process(clk, reset) begin if reset = '1' then read_ptr <= 0; elsif rising_edge(clk) then if deq_en = '1' and not deq_empty then read_ptr <= read_ptr + 1; end if; end if; end process; write_ptr_proc : process(clk, reset) begin if reset = '1' then write_ptr <= 0; elsif rising_edge(clk) then if enq_en = '1' and not enq_full then write_ptr <= write_ptr + 1; end if; end if; end process; -- D-triggers for full and empty signals enq_full_proc : process(clk, reset, write_ptr, read_ptr) begin if reset = '1' then enq_full <= '0'; elsif rising_edge(clk) then enq_full <= '0'; if write_ptr = read_ptr - 1 then enq_full <= '1'; end if; end if; end process; deq_empty_proc : process(clk, reset, write_ptr, read_ptr) begin if reset = '1' then deq_empty <= '0'; elsif rising_edge(clk) then deq_empty <= '0'; if write_ptr = read_ptr then deq_empty <= '1'; end if; end if; end process; -- memory block for FIFO queue memory_proc : process(clk, reset) begin if reset = '1' then for i in 0 to depth-1 loop memory(i) <= (others => '0'); end loop; elsif rising_edge(clk) then if enq_en = '1' and not enq_full then memory(write_ptr) <= enq_data; end if; if deq_en = '1' and not deq_empty then deq_data <= memory(read_ptr); end if; end if; end process; -- output signals empty <= deq_empty; full <= enq_full; end rtl;Verilog
》Wow! How does that look in Verilog?
》Here is an example of a FIFO queue in Verilog using D-triggers:
module FIFO_queue #(parameter depth = 8, width = 8) ( input wire clk, input wire reset, input wire enq_en, input wire [width-1:0] enq_data, output reg [width-1:0] deq_data, output wire deq_empty, output wire enq_full, input wire deq_en ); reg [log2(depth):0] read_ptr, write_ptr; reg [width-1:0] memory[0:depth-1]; reg deq_empty_reg, enq_full_reg; // D-triggers for full and empty signals always @(posedge clk or posedge reset) begin if(reset) begin deq_empty_reg <= 1'b0; end else if (write_ptr == read_ptr) begin deq_empty_reg <= 1'b1; end else begin deq_empty_reg <= 1'b0; end end always @(posedge clk or posedge reset) begin if(reset) begin enq_full_reg <= 1'b0; end else if (write_ptr + 1'b1 == read_ptr) begin enq_full_reg <= 1'b1; end else begin enq_full_reg <= 1'b0; end end // D-triggers for read and write pointers always @(posedge clk or posedge reset) begin if(reset) begin read_ptr <= 0; write_ptr <= 0; end else if (deq_en && !deq_empty_reg) begin read_ptr <= read_ptr + 1'b1; end else if (enq_en && !enq_full_reg) begin write_ptr <= write_ptr + 1'b1; end end // memory block for FIFO queue always @(posedge clk or posedge reset) begin if(reset) begin for(int i = 0; i < depth; i++) begin memory[i] <= 0; end end else if (enq_en && !enq_full_reg) begin memory[write_ptr] <= enq_data; end else if (deq_en && !deq_empty_reg) begin deq_data <= memory[read_ptr]; end end assign deq_empty = deq_empty_reg; assign enq_full = enq_full_reg; endmodule》In this example, the queue has a depth and data width specified by the
depthandwidthparameters respectively. It uses D-triggers to update the read and write pointers, as well as the full and empty signals, on the rising edge of the clock. The memory block updates the queue's memory array based on the current state of the read and write pointers and theenqЛучше меня списала :)
YuriPanchul Автор
27.01.2023 19:20+1Это плохая реализация. В ней используется не "pop" в смысле моей реализации, а "
eq_en", из-за чего больше гемороя при написании glue logic и c пропускной способностью. Такими реализациями набит интернет, но это как правило недавние студенты или профессора, которые слабо связаны с индустрией. В библиотеках внутри компаний написано как у меня, а не вот так. Это именно то, о чем я написал в явной форме:Философское отступление и тандем из FIFO
При обучении хардверному дизайну полезно знать, что для ученика может быть контринтуитивным. Это собственно и есть места, для которых нужен преподаватель, все остальное ученик выучит по книгам или догадается.
Например, по интуиции из программирования ученик может твердо подразумевать, что для чтения из очереди FIFO ему нужно сначала послать запрос (сделать сигнал pop=1), а потом получить ответ (прочитанное данное в следующем такте).
На самом деле для построения самого широко используемого FIFO на D-триггерах ментальная картина должна быть другой: данное к моменту pop на верхушке FIFO уже лежит и сигнал pop означает "я данное увидел, можешь о нем забыть, и пока я его обрабатываю, подгони на верхушку следующее данное".
У FIFO построенного таким образом есть очень полезное свойство: если поставить два таких FIFO друг за другом и просто соединить их проводами, то они будут функционировать как одно FIFO , без потери пропускной способности. В дизайне же "pop запрос-ответ"возникают всякие головные боли с написанием связывающей (glue) логики и с пропускной способностью.
Мы проиллюстрировали этот тезис упражнением valid-ready-etc/boards/omdazz/01_flip_flop_fifo/04_two_ff_fifos_back_to_back
datacompboy
27.01.2023 19:28+1Такими реализациями набит интернет, но это как правило недавние студенты или профессора, которые слабо связаны с индустрией.
Именно! О чем я и сказал -- списала из интернета, но лучше, чем сделал бы я за 2 минуты :)
Надеюсь, правильные реализации со временем тоже будут слямзены и впитаны в следующей версии.
Можно попросить high-throughput реализацию, и посмотреть, будет ли разница...
YuriPanchul Автор
27.01.2023 20:03Да, я сам думаю сделать какое-то наглядное демо для сравнения двух fifo
YuriPanchul Автор
27.01.2023 20:19+1ChatGPT несомненно создает проблемы для интервьирования, так как теперь нужно иметь в виду что на простые вопросы при онлайн-интервью кандидат может ответить с помощью ChatGPT (и в моей практике это вероятно уже произошло месяц назад).
Увы, основная идея интервью - с помощью простых задачек проверить может ли кандидат решать сложные - требует переосмысления и противодействий ChatGPT.
datacompboy
27.01.2023 22:33+1Требует По-моему просто задавать уточняющие вопросы. Если кандидат в состоянии модифицировать код под изменение условий - все ок.
Dufl
28.01.2023 02:50+1Здравствуйте, Юрий.
pop в смысле вашей реализации выглядит эквивалентным cигналу s_tready интерфейса axi-stream, can_push - эквивалентным сигналу s_tvalid. Не планируете ли вы перейти на обозначения axi-stream интерфейса для улучшения совместимости со сторонним кодом?YuriPanchul Автор
28.01.2023 03:06-1Я согласен, что есть эквивалентность:
downstream_valid = ~ empty
upstream_ready = ~ full
pop = downstream_ready & ~ empty
push = upstream_valid & ~ full
Но я не согласен переводить все интерфейсы fifo на AXI-Stream в примерах. Это просто не принято в электронной индустрии для FIFO внутри блоков.
AXI-Stream и вообще все AXI, AHB, APB итд - это внешние интерфейсы крупных блоков. Внутри блоков сигналы для FIFO так не называются. Если после этих курсов человек прийдет на интервью в какую-нибудь NVidia, AMD или Apple и на вопрос написать FIFO начнет писать сигналы tvalid/tready c префиксами, то ему конечно улыбнутся с пониманием "ну хорошо, если вам так нравится" но могут посчитать человеком со странностями.
Также внутри компаний многие интерфейсы внутри блоков не valid/ready, а credit-based (valid или send/free), а у некоторых и внешние.
Dufl
28.01.2023 21:16Я имел в виду полную функциональную эквивалентность и совместимость между сигналами вашего интерфейса и сигналами axi-stream интерфейса:
// input stream
push_data = s_tdata
push = s_tvalid
can_push = s_tready
//output stream
pop_data = m_tdata
can_pop = m_tvalid
pop = m_treadyFIFO, реализованную с вашим интерфейсом, можно поставить в цепочку axi-stream модулей без дополнительных переходников. Однако при подключении придется держать в голове маппинг сигналов вашего и axi-stream интерфейсов. Выглядит так, что переименование сигналов в axi-stream style добавит удобства при интеграции c axi-stream модулями, при этом имеет околонулевую стоимость реализации.
Про интерфейсы согласен только отчасти: APB, AHB и AXI-4 действительно являются громоздкими, и использование их на уровне модулей FIFO приведет к неоправданным тратам ресурсов на протокольную логику. Однако AXI-stream на порядок проще в имплементации, особенно в минимальной комплектации (data,valid,ready).
YuriPanchul Автор
28.01.2023 21:56Я вас полностью понял и собственно то же самое и написал. Вынужден просто повторить ответ чуть другими словами: вы почти правы, но:
pop у меня - это не совсем ready в AXI Stream. ready в AXI Stream может появляться перед valid. А в моей реализации FIFO (которая обычна для крупных электронных компаний) ситуация, когда на положительном фронте clock-а состояние сигналов pop=1 и can_pop=0 является не валидной (ошибка дизайна). В то время как в стандарте AXI Stream ready=1 и valid=0 - это обычная, штатная ситуация. AXI Stream позволяет все комбинации: valid=0/ready=0, 1/0, 0/1 и 1/1. А pop/can_pop у меня допускает только 1/1, 0/1 и 0/0, без 1/0.
Конечно можно поставить внутреннюю проверку, дополнительный and gate и делать pop только если can_pop=1, а иначе его игнорировать, и такая опция есть во многих библиотеках примитивов fifo (защищенная запись/чтение), но по умолчанию это не делают и оставляют проверку внешней логике (хотя это зависит от конкретной компании и инженерной группы).-
Такое переименование сигналов не принято. Потому что код многих продуктов - роутерных чипов, GPU итд использует внутренние библиотеки примитивов, которые старше не только AXI Stream, но иногда и всех шин AMBA вообще.
old_bear
29.01.2023 14:22+1А потом неожиданно выясняется, что FIFO приличной глубины на FF-ах в FPGA - это дорого и надо использовать BRAM. А ещё желательно чтобы это на 500+ МГц работало, так что надо два, а то и все три такта pipeline-а от read enable до появления данных на выходе этого самого BRAM. И тут приходит осознание, что almost full от следующего получателя с порогом >= длине pipeline-а, который формирует valid и данные текущего отправителя, это самое простое решение с минимальной вероятностью накосячить. Пусть и без волшебных побочных эффектов в виде возможности multi push/pop.
Впрочем, это у меня профдеформация от проектов где надо в FPGA достигнуть очередного "вышеплотнее,сильнееэкономичнее, быстрее" используя те ресурсы, которые есть.
Я бы наверное и не влез с этим комментарием в калашный ряд ASIC-дизайна, но не далее как на этой неделе я потратил немало времени на участие в увлекательном поиске косяка в диапазоне от приложения на host-е до собственно i/o моего ядра в PCIe FPGA ускорителе. И нашёл это косяк в итоге как раз в логике которая обслуживала это "самое широко используемое FIFO" с пред-чтением (простите за терминологию каменного века) находящееся по дороге. Ошибка то была не моя, но пришлось откроить на её поиски время от собственно дизайна очередной мега-нужной фичи перед очередным супер-hard deadline-ом.
Я это всё к тому, что в зависимости от области применения примеры, которыми набит интернет, могут быть менее геморройными, чем ваш вариант. И наверное об этом стоит сделать небольшую ремарку.
P.S. Ну вот, поныл и вроде полегчало. :DYuriPanchul Автор
29.01.2023 19:19Я прекрасно понимаю, о чем вы говорите. Действительно, для FIFO на FPGA стоит рассматривать BRAM, который инстанциируется только если делать registered read_data как выше. Точно так же как в ASIC для FIFO более чем пара тысяч DFF стоит использовать SRAM.
В типичном блоке в ASIC имеется смесь из FIFO на DFF и FIFO на SRAM. При этом в FIFO на SRAM требуется другой подход, чем в моем примере выше, потому что у SRAM используемых в ASIC-ах как правило латентность 2-3 или 4. При этом они конвейерные. Да, все так.
Именно такие FIFO будут рассматриваться в Школе на занятии через 2 недели.
И действительно, для них есть решение в виде almost_full. Все как вы написали "almost full от следующего получателя с порогом >= длине pipeline-а".
Вот только я не согласен, что это самое лучшее решение. Самое лучшее решение - это с кредитным счетчиком, который уменьшается на 1, когда мы вталкиваем данное в конвейер, и увеличивается на 1, когда мы делаем pop из FIFO. Тем самым нам не нужно постоянно держать пуское место в FIFO, равное длине конвейера, даже если конвейер пустой. Мы можем вталкивать, когда сумма количества данных идущих через конвейере и количества данных уже в FIFO меньше чем глубина FIFO:
Вот описание занятия 11 февраля, на котором будет про FIFO на конвейерной памяти с латентностью N:
11 февраля Внешняя память. Контроллеры памяти. Подключение SDRAM памяти к процессорному ядру. FIFO с хранением данных в памяти.
В первой части занятия мы рассмотрим интерфейс микросхем внешней памяти SDRAM и реализацию контроллера такой памяти для подключения ее к процессорному ядру.
Во второй части мы рассмотрим реализацию FIFO на памяти с ненулевой латентностью. Этот материал относится не только к внешней SDRAM, но и блокам SRAM памяти, встроенным в микросхемы ASIC. SRAM для FIFO внутри ASIC применяются когда нужно хранить более чем несколько тысяч бит, так как FIFO c сотнями тысяч или миллионами D-триггеров тратило бы слишком много электроэнергии.
Мы рассмотрим различные типы встроенных SRAM: однопортовую, двухпортовую и псевдо-двухпортовую память. Затем мы реализуем FIFO, которое использует псевдо-двухпортовую память, но с точки зрения интерфейса выглядит как FIFO на D-триггерах. Совместимость по интерфейсу необходима, чтобы проектировщик мог в заменить одно FIFO на другое в своем блоке даже на поздней стадии проекта. Ценой за такую совместимость является усложнение микроархитектуры такого FIFO.
Кроме этого, мы покажем, какие изменения следует внести в реализацию FIFO на регистровом массиве, чтобы синтез от Intel FPGA Quartus или Xilinx Vivado превратило его в блочную память, BRAM, специальную память внутри ПЛИС.
В качестве домашнего задания вы получите реализовать FIFO на однопортовой памяти (с помощью так называемой схемы пин-понга). Можно ли достичь на ней той же пропускной способности, что и у FIFO c псевдо-двух-портовой памятью? Это тоже вопрос с интервью.
gchebanov
27.01.2023 18:58Если делать домашнее задание с cross clock domain, то фокус с кодом грея перестаёт работать, как только появляется инкремент больше чем на 1, появляется изменение кода с флипом больше одного бита, и если читающая сторона увидит состояние где есть только один из двух, (соответствующий инкременту на 3, или декременту на 1, для стандартного кода). Пока придумал как с этим бороться либо задорого при больших N, либо ростом латентности.
@YuriPanchul Есть решение получше?
YuriPanchul Автор
27.01.2023 19:25Clock domain crossing будет разбираться на отдельном занятии, в этом занятии тактовый сигнал везде один. Вы про какое домашнее задание говорите? Про 2_push_2_pop fifo?
gchebanov
27.01.2023 19:28Ага.
YuriPanchul Автор
27.01.2023 20:10У домашнего задания есть три известные мне реализации. Но я пока не думал, как скрестить multi-push fifo и cdc.
gchebanov
27.01.2023 20:32+1Ну без cdc как угодно можно, это не интересно. Хотя когда я первый раз сам такое писал ухитрился налажать.
dimas846
Слишком много рекламы на видео.
YuriPanchul Автор
На видео есть реклама? В смысле реклама от Rutube? Ну с этим ничего не могу поделать
AKudinov
Разместить видео на YouTube, например? ;-)
YuriPanchul Автор
Я могу конечно, но 1) на YouTube тоже есть реклама если у кого-нибудь не платный аккаунт и 2) в этот раз решил попробовать так.
Есть еще ссылки на vimeo:
итд:
https://vimeo.com/792847639/f9d74fd6cc
https://vimeo.com/793034048/484d77dd04
https://vimeo.com/792841439/b3dd85085e
https://vimeo.com/792828997/a38f553683
atd
Если смотреть из РФ (или с российским прокси), то рекламы не будет
YuriPanchul Автор
Это всегда так были или только недавно?
AKudinov
Примерно с весны 2022 года так.
KeisN13
Мальчик: покупает подписку, чтобы убрать рекламу на Youtube
Мужчина: релоцируется в РФ
Извините, не смог удержаться xD
YuriPanchul Автор
Да уж! :-) Перезалил на YouTube
punzik
Надо пожаловаться в рутуб. Автовоспроизведение рекламы - это если не баг, то серьёзный косяк.
1dNDN
Это еще хорошо, что тест по рекламе не заставили проходить. Они могут
Ivanii
Чтоб не видеть рекламы на Рутубе нужно использовать uBlock Origin и не использовать Яндекс браузер. У меня основной Яндекс браузер по этому сразу несу Рутубные ссылки в Хром.