FIFO для самых маленьких (вместе с вопросами на интервью)

«Напишите на доске код на верилоге для 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 — это блок для временного хранение информации, в который можно запихивать данные слева и получать их справа:

Альтернативные имена для сигналов:

  1. Сигнал D в некоторых реализациях называют write_data, Q — read_data.

  2. Сигналы Push/Pop иногда называют write/read. Но тут нужно быть внимательным. Есть FIFO, которые Xilinx называет «стандартными», в которых данные приходят после запроса read. Но при проектировании ASIC чаще используются FIFO, в которых следующие данные уже присутствуют на шине, когда Empty=0, и установка сигнала Pop/Read в единицу вызовет удаление текущего значения с головы FIFO. После чего там окажется следующее значение и FIFO станет пустым.

  3. Сигналы Empty/Full иногда называют Can_read/can_write.

А чем FIFO отличается от сдвигового регистра (shift register), спросите вы? Два отличия:

  1. В сдвиговом регистре глубины D данное/трансфер проходит от начала до конца ровно за D сдвигов, то есть минимум за D тактов. В FIFO же этот путь зависит от количества элементов в FIFO. То есть если FIFO пустое, то записанный трансфер будет доступен для чтения уже в следущем такте (для FIFO на D-триггерах или SRAM-based с байпасом). Но если FIFO глубиной D почти полное (наполненность равна D-1), то путь займет минимуму D тактов.

  2. В сдвиговом регистре мы перемещаем данные, а в 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, которую держет в руках девушка Наташа, вам подарят бесплатно, если вы будете делать упражнения:

Читайте так же:

  • Стартовали продажи первых умных часов Amazfit специально для детейСтартовали продажи первых умных часов Amazfit специально для детей Компания Huami, известный контрактный производитель умных браслетов Xiaomi Mi Band. А также носимых устройств под собственными брендами Amazfit и Zepp. Начала продажи своих первых умных часов. Созданных специально для детей.  Устройство под сложным названием Amazfit Happya […]
  • Официальное руководство Open SLAED — Освоить систему сможет каждыйОфициальное руководство Open SLAED — Освоить систему сможет каждый За пять лет существования продукта и бренда SLAED CMS мы существенно продвинулись в технической стороне наших продуктов. Что постепенно привело к существенному повышению интереса к семейству CMS от SLAED. Настало время сделать несколько шагов в сторону повышения уровня информационного […]
  • Приглашаем на конференцию QA Meeting PointПриглашаем на конференцию QA Meeting Point QA Meeting Point — бесплатная онлайн-конференция DINS для всех, кто интересуется тестированием ПО. Наша цель — объединить специалистов по всей стране, чтобы на одной площадке обсудить общие проблемы, найти для них решения, обрести единомышленников. Конференция пройдет 1 декабря 2021 […]
  • Веб-интерфейс ovpn-admin для управления пользователями OpenVPN обновился до версии 1.7Веб-интерфейс ovpn-admin для управления пользователями OpenVPN обновился до версии 1.7 ovpn-admin — простой веб-интерфейс для управления сертификатами и маршрутами для пользователей OpenVPN. Утилита изначально была разработана для внутренних проектов «Фланта». Этой весной мы решили, что ovpn-admin будет полезен не только нам, и выложили его как Open Source-проект на […]