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

"Напишите на доске код на верилоге для 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 иногда называют put/get и иногда write/read. Но тут нужно быть внимательным. Есть FIFO, которые Xilinx называет "стандартными", в которых данные приходят после запроса read. Но при проектировании ASIC чаще используются FIFO, в которых следующие данные уже присутствуют на шине, когда Empty=0, и установка сигнала Pop/Read в единицу вызовет удаление текущего значения с головы FIFO. После чего там окажется следующее значение и FIFO станет пустым.
Сигналы Empty/Full иногда называют Can_read/can_write.

Функционально FIFO - это просто массив с двумя указателями, которые также называют адресами и иногда индексами. write/put_pointer и read/get_pointer. Работает это так (gif отсюда):

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