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