"Напишите на доске код на верилоге для FIFO" - это популярный вопрос во время интервью в компании типа Apple и AMD, причем у него есть вариации для всех уровней инженеров, так как существуют десятки типа реализаций FIFO: на D-триггерах, встроенной SRAM памяти или на массиве D-защелок; с одном или двумя тактовыми сигналами; с одним, двумя или N вталкиваниями / выталкиваниями в одном такте; с разделяемой несколькими FIFO общей памятью; с парой указателей для записи/чтения и с хранением элементов в виде связанного списка; FIFO позволяющее undo; FIFO позволяющие потери данных; всякая экзотика типа FIFO шириной ноль итд.
Если человек не в теме или не понял вопроса, он может начать "запускаем GUI от Xilinx, вносим параметры и инстанциируем сгенерированный код". Это вызывает реакцию, как если бы школьная учительница геометрии спросила "найдите гипотенузу" и школьник бы ткнул пальцем в гипотенузу и с улыбкой ответил "вот она!"
Если у человека в резюме есть десять лет опыта, он спросит "какое именно FIFO" ему показать из списка выше. Но если человек только что пришел с вводного курса, то он должен как минимум знать то что написано ниже. То есть уметь написать самое простое FIFO на D-триггерах и с одним тактовым сигналом, уметь его использовать с окружающей логикой и разпознать случаи, в которых его нужно применять.
Без этого умения вы не знаете Verilog и не умеете проектировать на уровне регистровых передач. К сожалению, FIFO нет в книге Харрис & Харрис ("Цифровая схемотехника и архитектура компьютера: RISC-V"), и это ее недостаток. В реальной жизни любой компании которая проектирует CPU, GPU, сетевые чипы и нейроускорители, во многих блоках есть десятки FIFO.
[Тут может быть возражение, что в любой крупной компании, в которой вы будете работаеть, уже будет внутрення библиотека всех видов FIFO и вам в 90% случаев не нужно будет его писать. Но я не буду на это возражение отвечать.]
Небольшое отступление
Эту заметку я написал прежде всего для участников Сколковской Школы Синтеза Цифровых Схем, в качестве приквела к занятию "Стандартные блоки и приемы проектирования для ASIC и FPGA: очереди FIFO и кредитные счетчики". Это занятие проведет в субботу 22 января 2022 инженер-разработчик ПЛИС Дмитрий Смехов.
Дмитрий уже писал про FIFO на Хабре. Его заметка наглядно описывает, как работает пара из указателей для чтения и записи. Поэтому я очень рекомендую ее прочитать перед началом занятий, особенно часть начиная со слов "Определение пустого и полного FIFO" и до слов "Это означает, что FIFO полное и записывать дальше нельзя, что бы не испортить уже записанные данные".
При этом заметка Дмитрия посвящена FIFO с двумя тактовыми сигналами и памятью, причем глубиной степени двойки. Про FIFO с двумя тактовыми сигналами на школе будет отдельное занятие, по мотивам статей Клифа Каммингса (1, 2). Также при проектировании ASIC помимо FIFO c хранением данных в памяти часто используются FIFO на основе регистрового файла из D-триггеров, код для которых я написал в примере ниже.
Кроме этого статья Дмитрия недостаточно артикулирует зачем FIFO нужно вообще. Я попробую дать на пальцах некое первоначальное понимание для тех, кто видит FIFO впервые. А также дам три задачки, которые было бы хорошо решить участникам перед занятием, так как Дмитрий будет на нем говорить больше о кредитных счетчиках, чем о FIFO.
Что такое FIFO?
Итак: в базовом виде очередь FIFO - это блок для временного хранение информации, в который можно запихивать данные слева и получать их справа:
Альтернативные имена для сигналов:
Сигнал D в некоторых реализациях называют write_data, Q - read_data.
Сигналы Push/Pop иногда называют write/read. Но тут нужно быть внимательным. Есть FIFO, которые Xilinx называет "стандартными", в которых данные приходят после запроса read. Но при проектировании ASIC чаще используются FIFO, в которых следующие данные уже присутствуют на шине, когда Empty=0, и установка сигнала Pop/Read в единицу вызовет удаление текущего значения с головы FIFO. После чего там окажется следующее значение и FIFO станет пустым.
Сигналы Empty/Full иногда называют Can_read/can_write.
А чем FIFO отличается от сдвигового регистра (shift register), спросите вы? Два отличия:
В сдвиговом регистре глубины D данное/трансфер проходит от начала до конца ровно за D сдвигов, то есть минимум за D тактов. В FIFO же этот путь зависит от количества элементов в FIFO. То есть если FIFO пустое, то записанный трансфер будет доступен для чтения уже в следущем такте (для FIFO на D-триггерах или SRAM-based с байпасом). Но если FIFO глубиной D почти полное (наполненность равна D-1), то путь займет минимуму D тактов.
В сдвиговом регистре мы перемещаем данные, а в FIFO - указатели. Это экономит динамическое энергопотребление чипа, которое зависит от движения данных по D-триггерам. Чем меньше движения, особенно для широких шин, тем лучше.
Ниже мы рассмотрим примеры базового FIFO, RTL код для которого вместе с моделью и тестовым окружением я выложил на GitHub. Обратите внимание, что я намеренно выложил код незаконченным - участники школы в порядке упражнения должны сами заполнить места, которые обозначены TODO.
Зачем нужно FIFO?
FIFO позволяет расцепить отправлятеля и получателя данных по времени. Например представим, что у нас есть два процессора, которые работают совершенно параллельно и даже могут иметь разные адресные пространства. Представим, что им нужно передать данные так, чтобы данные не размножились и не потерялись, а также чтобы один процессор не ждал другого а просто занимался своей активностью и читал или писал когда ему удобно.
Для этого можно сделать, чтобы при записи в ячейку с определенным адресом одним процессором происходила запись в FIFO, а при чтении с определеного адреса другим процессором происходило чтение из FIFO:
А что будет, спросите вы, если CPU2 будет пробовать читать из пустого FIFO, или CPU1 будет пробовать писать в заполненное FIFO? Вот тогда процессор CPU1 будет останавливаться на инструкции store и ждать, а процессор CPU2 будет останавливаться на инструкции LOAD и ждать. Такая опция называется gated storage, она реализована в некоторых встроенных процессорах, например MIPS interAptiv.
Другое применение: выравнивание результатов параллельных блоков по времени. Допустим вы хотите получить от двух блоков два потока чисел и сложить их попарно. При этом блоки посылают числа в разное время, а блок, получающий результаты, может не готов принять сумму. Нет проблем, строим вот такую конструкцию, которая складывает числа попарно, даже если они шлются в разное время. Код для этой конструкции тоже на гитхабе и тоже намеренно незаконченный:
Еще применение. Если вы носите некие данные вместе (например координаты точек и их цвета) и хотите отправить поток этих данных на обработку, но обрабатывать собираетесь только часть данных (например пересчитывать координаты, но не трогать цвета), то вы можете отправить необрабатываемые данные в находящееся сбоку FIFO, где они будут лежать и ждать соотвествующие им обрабатываемые данные:
FIFO также широко используют, чтобы принять результаты вычисление после конвейера, в комбинации с кредитными счетчиками. Эта схема мало описана в учебниках, но применяется сплошь и рядом в промышленности, описана в статьях и патентах. Альтернатива такой схеме - это вводить сложные остановки конвейера, что чревато багами и проблемами с таймингом. Комбинация "конвейер + FIFO + кредитный счетчик" гораздо лучше, о ней расскажет Дмитрий Смехов на Школе Синтеза:
Пример 1
Перейдем к примерам. p020_generic_flip_flop_fifo.v содержит намеренно незаконченную реализацию простого FIFO на D-триггерах, с регистровым файлом data, парой из указателей wr_ptr/rd_ptr и использованием счетчика для генерации флагов empty и full.
always @ (posedge clk)
if (rst)
wr_ptr <= '0;
else if (push)
wr_ptr <= wr_ptr == max_ptr ? '0 : wr_ptr + 1'b1;
// TODO: Add logic for rd_ptr
always @ (posedge clk)
if (push)
data [wr_ptr] <= write_data;
assign read_data = data [rd_ptr];
always @ (posedge clk)
if (rst)
cnt <= '0;
else if (push & ~ pop)
cnt <= cnt + 1'b1;
else if (pop & ~ push)
cnt <= cnt - 1'b1;
assign empty = ~| cnt;
// TODO: Add logic for full output
Результат работы синтезируемого модуля generic_flip_flop_fifo_rtl сравнивается с результатом несинтезируемой модели fifo_model , которая написана с использованием очереди (SystemVerilog queue).
logic [width - 1:0] queue [$];
Тонкий момент: так как в RTL-реализации имеется комбинационная логика после D-триггеров на выходе (это вполне допустимо), то при моделировании в тестовом окружении приходится идти на специальные ухищрения:
@ (posedge clk);
# 1 // This delay is necessary because of combinational logic after ff
Вопрос на понимание 1: Каковы преимущества и каковы недостатки оставлять такой хвост из комбинационной логики после D-триггеров в данном примере
assign read_data = data [rd_ptr];
assign empty = ~| cnt;
Вопрос на понимание 2: Перепишите пример, чтобы все выходы стали registered, то бишь шли от D-триггеров.
Для запуска примера можно использовать Icarus Verilog и GTKWaves. Как их установить, я описал в посте "Ни дня без строчки верилога — учим язык решением большого количества простых задач". Если вы поправите пример правильно, то вы увидите вот такие временные диаграммы:
и вот такой лог:
empty [ ]
push 63 [ 63 ]
push 12 [ 12 63 ]
[ 12 63 ]
...
push 4b pop fa full [ 4b 9b 8f 0b 84 ]
full [ 4b 9b 8f 0b 84 ]
pop 84 [ 4b 9b 8f 0b ]
Вопрос на понимание 3: Позволяет ли данная реализация писать в полное FIFO?
Пример 2
Упражнение p021_gen_dff_fifo_pow2_depth.v делает то же самое, что и предыдущее упражнение, но отличает состояние empty от full без использования счетчика. Это возможно за счет введения ограничения - FIFO второго примера может иметь только глубину степени двойки (1, 2, 4, 8, ... ). Это достигается с помощью введения дополнительного бита в указатели:
reg [extended_pointer_width - 1:0] ext_wr_ptr, ext_rd_ptr;
wire [pointer_width - 1:0] wr_ptr = ext_wr_ptr [pointer_width - 1:0];
wire [pointer_width - 1:0] rd_ptr = ext_rd_ptr [pointer_width - 1:0];
Замечу что FIFO первого примера может иметь глубину 3, 113 и вообще любую - в ASIC-х любят экономить D-триггеры. Точное вычисление размера требуемого FIFO (позволяет максимальную пропускную способность по требованиям, но ни элементом больше) - признак профессионализма. Впрочем даже для самых суровых профессионалов электронные компании часто оставляют небольшой запас, даже при защите с помощью кредитных счетчиков, так как стоимость ошибки в уже произведенном ASIC-е может быть астрономической.
Пример 3
Упражнение p022_three_fifos_around_adder.v - это та самая конструкция из трех FIFO и сумматора, которую мы уже обсудили выше.
В ней не хватает следующего кода, который нужно дописать для понимания:
// TODO: Complete all the assignments
// to finish the design of three_fifos_around_adder
/*
assign can_push_a = ...
assign can_push_b = ...
assign can_pop_sum = ...
assign pop_a = ...
assign pop_b = ...
assign push_sum = ...
assign write_data_sum = ...
*/
Если вы сделаете все правильно, то пример выдаст следующий лог:
3
4 a 0001 b 0100 <-- Сначала пары идут вместе и подряд (back-to-back)
5 a 0002 b 0200
6 a 0003 b 0300 sum 0101 <-- Первая пара сложена
7 a 0004 b 0400 sum 0202
8 a 0005 b 0500 sum 0303
9 a 0006 b 0600 sum 0404
10 a 0007 b 0700 sum 0505
11 a 0008 b 0800 sum 0606
12 a 0009 b 0900 sum 0707
13 a 000a b 0a00 sum 0808
14 a 000b sum 0909
15 a 000c sum 0a0a
16 a 000d
17 a 000e
18 a 000f
19 <-- Потом получатель перестает принимать результаты
Это называется backpressure
. . . .
27
28 b 0b00 <-- Потом заталкивание и получение происходит случайно
29
30 a 0010 b 0c00 sum 0b0b
31
32 a 0011
33 b 0d00
34 b 0e00
35 a 0012 b 0f00
36 a 0013
37 a 0014 b 1000
38 b 1100 sum 0c0c
На временных диаграммах вы тоже можете увидеть, что в тестовой последовательности, cначала пары идут вместе и подряд (back-to-back). Потом получатель перестает принимать результаты (это называется backpressure). Еще до этого иссякает источник чисел B:
Через некоторое время прием восстанавливается и потом заталкивание и получение происходит случайно:
Вопрос на понимание 4: Будет ли схема работать, если удалить выходное FIFO? А одно из входных?
Вопрос на понимание 5: Зачем может понадобиться на выходе FIFO глубины 2 (подсказка: skid buffer).
На этом мы введение (первые 5% материала) в FIFO заканчиваем и ждем вас на Сколковской Школе Синтеза Цифровых Схем. Школу поддерживает Ядро Микропроцессор / Syntacore - они готовят прорыв в российских RISC-V суперскалярных микропроцессорах, и Cadence Design Systems - их софтвером, согласно Джону Кули, пользуются в Apple для проектирования айфонов. Плату Omdazz, которую держет в руках девушка Наташа, вам подарят бесплатно, если вы будете делать упражнения: