Fifo буфер что это такое
Используем черную магию для создания быстрого кольцевого буфера
Вчера я заглянул на страницу Википедии, посвященную кольцевому буферу (circular buffer), и был заинтригован предполагаемой техникой оптимизации, с которой до этого не был знаком:
В рамках реализации кольцевого буфера нам необходимо обработать случай, когда сообщение попадает на «разрыв» в очереди и должно быть перенесено (wrap around). Очевидная реализация записи в кольцевой буфер может полагаться на побайтовую запись и выглядеть примерно так:
Тот факт, что для индексации в массиве необходима операция деления, затрудняет (если не исключает) векторизацию этой функции и, следовательно, делает ее неоправданно медленной. Хотя есть и другие оптимизации, которые мы можем здесь применить, методика из Википедии, предложенная выше, превосходит аппаратно-независимые подходы в силу того факта, что блок управления памятью может справиться с львиной долей логики циклического переноса за нас. Я был так воодушевлен этой идеей, что не стал проводить никаких дополнительных исследований и реализовал ее, основываясь только на кратком описании, приведенном выше.
В следующих двух разделах рассматривается конструкция кольцевого буфера и логика работы виртуальной памяти соответственно. Если вы не нуждаетесь в освежении этой информации, можете смело пропустить их.
Кольцевой буфер
Учитывая это, мы можем написать простые методы чтения ( get ) и записи ( put ), используя побайтовый доступ:
Обратите внимание, что этот метод put идентичен приведенной ранее варианту, за исключением того, что мы теперь проверяем, что свободного места достаточно прежде чем пытаться писать. Я также намеренно пренебрег логикой синхронизации (которая была бы абсолютно необходима для любого реального применения кольцевого буфера).
А вот пример использования этого кольцевого буфера:
Наш код прост и отлично работает. Но почему бы не усложнить его немного?
Встречайте таблицу страниц
На заре персональных компьютеров компьютеры могли одновременно запускать только одну программу. Какую бы программу мы ни запустили, она будет иметь полный прямой доступ к физической памяти. Оказывается, если мы хотим запустить несколько программ вместе, они будут бороться за то, какие области этой памяти они хотят использовать. Решением этого конфликта является виртуальная память, благодаря которой каждая программа считает, что она контролирует всю память, но на самом деле операционная система решает, кто какую память получает.
Таблица страниц для некоторой программы А может выглядеть следующим:
Номер виртуальной страницы
Базовые принципы построения FIFO.
Очередь FIFO (First In, First Out) представляет собой циклический буфер, где будут храниться помещаемые в очередь данные. Есть два указателя: указатель на «голову» очереди ( head ) и указатель на «хвост» очереди ( tail ).
Обычно глубина FIFO и разрядность указателей являются числами степени двойки. Например, если разрядность указателей head и tail – это 8, то глубина FIFO будет 256 элементов.
Цикличность буфера обеспечивается автоматически. При последовательном увеличении значения указателя однажды возникнает перенос, а сам указатель при этом обнуляется (после указателя 255 его следующее значение будет 0).
Теперь, когда мы знаем, что есть два указателя, легко определить всякие информационные сигналы:
Возможно, последнее утверждение нуждается в пояснении. Например, глубина FIFO 256 элементов. Мы запишем в него 255 элементов, но читать из FIFO пока не будем. Тогда «голова»=255, а «хвост»=0. Сейчас FIFO полное. Если в него записать еще один элемент, то значение «головы» станет 0 (возникает перенос) и получится, что и «голова» и «хвост» становятся одинаковыми и равными нулю. Все, FIFO опять стало пустым? Конечно, это ошибка логики.
Нельзя допускать запись в полное FIFO и чтение/выборку элемента из пустого FIFO.
Все вышеописанное прекрасно, но что делать, если запись и чтение происходят с использованием разных тактовых частот, если FIFO асинхронное? Мы не можем на прямую сравнивать или делать какие-то арифметические операции с указателями «голова» и «хвост», так как в этом случае они храняться в разных клоковых доменах (clock domains).
Просто пересинхронизировать группу (8-ми битные счетчики указателей голова и хвост) сигналов в другой домен не есть хороший вариант, как было уже ранее показано в другой статье. Главная проблема здесь – не все биты шины могут перейти в другой клоковый домен одновременно, а значит двоичное число на шине может быть искажено.
Код Грея — специальная система счисления, в которой два соседних значения различаются только в одном разряде.
Вот пример трехбитных кодов Грея. Слева в таблице значения обычного двоичного счетчика, а справа значения из счетчика Грея.
Методика использования кодов Грея может быть следующая. Значение счетчика указателя, например, головы FIFO перекодируется в код Грея и пересекает клоковый домен с помощью группы синхронизаторов (каждый – это два последовательных триггера). При этом, как мы знаем, не все биты могут быть зафиксированы верно: в новом клоковом домене в некоторых битах зафиксируются новые значения числа на шине, а в некоторых – старые значения. Однако, для кода Грея изменения в соседних числах счетчика происходят только в одном бите, значит только в одном бите и может произойти коллизия. Только один изменяющийся сейчас бит может быть принят не верно. В этом случае принимающий домен просто считает предыдущее число на шине, а верное, следующее число он считает на следующем такте своей частоты. Такая ошибка даже и ошибкой не считается, ведь она не приводит к аварии FIFO.
Принятый код Грея может быть перекодирован обратно в обычную двоичную систему счисления и тут уже мы имеем верное значение обоих указателей в одном клоковом домене. Теперь можно их сравнивать, вычислять число элементов в FIFO и так далее.
В принципе, FIFO может изначально держать указатели «головы» и «хвоста» в кодах Грея.
Вообще использование кодов Грея в асинхронных FIFO очень распространено, так как действительно позволяет решить проблему пересечения клокового домена для потока данных.
UDB. Что же это такое? Часть 3. Datapath FIFO
Продолжаем делать перевод фирменной документации фирмы Cypress на блоки UDB. Тем более, что всё очень удачно совпадает. Для продолжения практической статьи по UDB понадобится использование FIFO, а в теоретической части мы подобрались как раз к их описанию. Поэтому начинаем изучать их во всех деталях.
Общее содержание цикла «UDB. Что же это такое?»
Часть 1. Введение. PLD.
Часть 2. Datapath.
Часть 3. Datapath FIFO. (Текущая статья)
Часть 4. Datapath ALU.
Часть 5. Datapath. Полезные мелочи.
Часть 6. Модуль управления и статуса.
Часть 7. Модуль управления тактированием и сбросом
Часть 8. Адресация UDB
21.3.2.2 Datapath FIFO
Режимы и конфигурации FIFO
Каждый буфер FIFO имеет несколько доступных режимов работы и конфигураций:
Таблица 21-2. Режимы и конфигурации FIFO.
| Режим | Описание |
|---|---|
| Input/Output (Входной/выходной буфер) | В режиме входного буфера CPU или DMA записывают данные в FIFO, а Datapath считывает их. В режиме выходного буфера данные попадают в FIFO из Datapath, а считывает их оттуда CPU или DMA. |
| Single Buffer (Одиночный буфер) | FIFO работает как одиночный буфер без статуса. Записанные в FIFO данные сразу доступны для чтения и могут быть перезаписаны в любое время. |
| Level/Edge (Уровень/перепад) | Параметр, отвечающий за загрузку FIFO из Datapath, может инициироваться по уровню или по перепаду. |
| Normal/Fast (Нормальный/быстрый) | Параметр, отвечающий за загрузку FIFO из источника Datapath: тактируется она с частотой выбранного для Datapath тактового источника (normal) или с частотой шины (fast). Это позволяет выполнять захват с наивысшей частотой в системе (частота шины), независимо от тактовой частоты Datapath. |
| Software Capture (Программный захват) | Когда включен этот режим, а FIFO находится в режиме выходного буфера, чтение CPU или DMA связанного аккумулятора (A0 для F0, A1 для F1), инициализирует синхронную передачу значения аккумулятора в FIFO. Захваченное значение сразу доступно для чтения из FIFO. Если активирована поддержка связывания в цепочки, операция проследует по цепочке до блока MS, чтобы Datapath мог выполнить атомарное считывание многобайтовых значений. |
| Asynch (Асинхронный) | Когда тактовые частоты Datapach и системной шины не синхронизированы, сигналы статуса FIFO могут быть проброшены на остальную часть Datapath либо напрямую, тактируясь от тактовой частоты Datapath, либо с двойной синхронизацией, в режиме Asynch. |
| Independent Clock Polarity (Независимая тактовая полярность) | Каждый FIFO имеет управляющий бит для инвертирования полярности тактового сигнала FIFO по отношению к тактированию Datapath. |
На рисунке 21-7 показаны возможные варианты конфигурации пары FIFO, в зависимости от выбранных для каждого из них режимов Input/Output. Если один FIFO находится во входном режиме, а другой в выходном, получаем конфигурацию RX/TX. Типичный пример, где нужна такая конфигурация, контроллер шины SPI. В конфигурации Dual Capture (оба FIFO настроены на выход) обеспечивается независимый захват пары A0 и A1 или два независимых захвата регистров A0 или A1. Наконец, в режиме Dual Buffer (оба на вход) возможно использование для загрузки или сравнения как регистровой пары, так и двух независимых регистров.
Рисунок 21-7. Конфигурации FIFO.
На рисунке 21-8 подробно показаны источники и приемники для FIFO.
Рисунок 21-8. Источники и приемники FIFO.
Когда FIFO работает в режиме входного буфера, источником является системная шина, а приемниками – регистры Dx и Ax. При работе в режиме выходного буфера, источниками являются регистры Ax и ALU, а приемником – системная шина. Выбор мультиплексора задан статически в регистре конфигурации UDB CFG15, как показано в таблице для F0_INSEL[1:0] или F1_INSEL[1:0]:
Таблица 21-3. Набор мультиплексоров FIFO в регистре конфигурации UDB.
| Fx_INSEL[1:0] | Описание |
|---|---|
| 00 | Режим входного буфера: системная шина записывает в FIFO, а приемником FIFO является Ax или Dx. |
| 01 | Режим выходного буфера: источником FIFO является А0, а приемником FIFO – системная шина. |
| 10 | Режим выходного буфера: источником FIFO является A1, а приемником FIFO – системная шина. |
| 11 | Режим выходного буфера: источником FIFO является выход ALU, а приемником FIFO – системная шина. |
Статус FIFO
Каждый FIFO вырабатывает два сигнала статуса, «bus» и «block», которые передаются на трассировочные ресурсы UDB через выходной мультиплексор Datapath. Статус «bus» можно использовать для взведения прерывания или запроса DMA чтения/записи в FIFO. Состояние «block» в основном предназначается для передачи состояния FIFO на внутренние сущности UDB. назначение битов статуса зависят от сконфигурированного направления (Fx_INSEL[1:0]), и битов уровня FIFO. Биты уровня FIFO (Fx_LVL) устанавливаются в регистре Auxiliary Control в пространстве рабочих регистров. Варианты статусов показаны в следующей таблице:
Таблица 21-4. Варианты состояния FIFO.
| Fx_INSEL[1:0] | Fx_LVL | Состояние | Сигнал | Описание |
|---|---|---|---|---|
| Ввод | 0 | Не полон | Статус «Bus» | Взводится, когда в FIFO есть место хотя бы для одного байта. |
| Ввод | 1 | Опустошен как минимум наполовину | Статус «Bus» | Взводится, когда в FIFO есть место хотя бы для 2 байтов. |
| Ввод | Н/Д | Пуст | Статус «Block» | Взводится, когда в FIFO нет ни одного байта. Когда FIFO не пуст, Datapath может считывать байты. Когда FIFO пуст, Datapath может находиться в состоянии ожидания либо сгенерировать состояние опустошения. |
| Вывод | 0 | Не пуст | Статус «Bus» | Взводится, когда в FIFO доступен хотя бы 1 байт для чтения. |
| Вывод | 1 | Заполнен как минимум наполовину | Статус «Bus» | Взводится, когда в FIFO доступны хотя бы 2 байта для чтения. |
| Вывод | Н/Д | Полон | Статус «Block» | Взводится, когда FIFO полон. Когда FIFO не полон, Datapath может записывать байты в FIFO. Когда FIFO полон, Datapath может находиться в состоянии ожидания или сгенерировать условие переполнения. |
Иллюстрация работы FIFO
Рисунок 21-9 показывает типичную последовательность чтения и записи, а также генерации связанных с этими операциями статусов. На рисунке чтение и запись происходят в разное время, однако они могут выполняться и одновременно.
Рисунок 21-9 Работа приемников FIFO.
Быстрый режим FIFO (FIFO FAST)
Когда FIFO работает в режиме выходного буфера, операция загрузки FIFO обычно использует тактовую частоту выбранного Datapath для тактирования сигнала записи. Как показано на рисунке 21-10, при выборе быстрого режима FIFO (FIFO FAST) для этой конкретной операции можно выбрать частоту шины. При использовании совместно с режимом Level/Edge = Edge, эта операция позволяет уменьшить задержку передачи из аккумулятора в FIFO с периода тактовой частоты Datapath до периода тактовой частоты шины, так как у шины частота может быть гораздо выше. Это позволяет CPU или DMA считывать полученный результат FIFO с минимальной задержкой.
Как показано на рисунке 21-10, операция быстрой загрузки выполняется независимо от текущего тактирования Datapath, однако использование тактовой частоты шины может повысить энергопотребление.
Рисунок 21-10. Приемники быстрой конфигурации FIFO.
Режим записи в FIFO Edge/Level (по перепаду/по уровню)
Существуют два режима записи в FIFO из Datapath. В первом режиме данные синхронно передаются из аккумуляторов в FIFO. Управляющий сигнал этой записи (FX_LD) обычно формируется конечным автоматом или синхронизированным с тактированием Datapath условием. Запись в FIFO будет проводиться в любом цикле, в котором управляющий сигнал загрузки ввода равен ‘1’. Во втором режиме FIFO используется для захвата значений аккумулятора в ответ на положительный перепад сигнала FX_LD. В этом режиме формат сигнала сигнала является произвольным (однако его период должен быть равен как минимум одному циклу тактирования Datapath). Примером этого режима является захват значения аккумулятора при помощи входа внешней ножки в качестве триггера. Ограничением этого режима является то, что параметр входа должен возвращаться к значению ‘0’ как минимум за один цикл до обнаружения другого положительного перепада.
На рисунке 21-11 показана реализация режима обнаружения перепада на входе FX_LD. Режим обоих FIFO в UDB управляются одним и тем же битом, переключающим данную опцию. Обратите внимание, что обнаружение перепада тактируется с частотой, равной частоте выбранного FIFO.
Рисунок 21-11. Обнаружение перепада для внутренних приемников записи FIFO.
Режим программного захвата FIFO (Software Capture)
Распространенным и важным требованием является обеспечение возможности для CPU и DMA надежно считывать содержимое аккумулятора во время нормальной работы. Это делается при помощи программного захвата и включается при помощи бита конфигурации FIFO Cap. Этот бит применяется к обоим FIFO в UDB, но работает, только когда FIFO находится в режиме выходного буфера. При использовании программного захвата F0 должен считывать из A0, а F1 из A1.
Как показано на рисунке 21-12, чтение аккумулятора инициирует запись в FIFO из аккумулятора. Сигнал связывается в цепочку, чтобы чтение конкретного байта одновременно захватывало значения аккумуляторов всех UDB в цепочке. Это позволяет 8-битному процессору успешно считывать одновременно 16 битов или больше. Данные, возвращенные при чтении аккумулятора, должны игнорироваться, а захваченное значение может быть сразу доступно для чтения из FIFO.
Трассированный сигнал FX_LD, который генерирует загрузку FIFO, направляется на терм OR вместе с сигналом программного захвата. Когда одновременно используются аппаратный и программный захват, результат может быть непредсказуем. Как правило, эти функции должны быть взаимоисключающими, однако аппаратный и программный захват можно использовать одновременно, при следующих условиях:
Также рекомендуется очищать целевой FIFO в программном коде (регистр ACTL) до начала программного захвата. Благодаря этому указатели на чтение и запись FIFO будут установлены в известное состояние.
Рисунок 21-12. Конфигурация программного захвата.
Примечание переводчика:
Я долго не мог понять смысла этого раздела. Потом я долгое время был уверен, что раздел написан для PSoC3, восьмибитное ядро которого не может обращаться более, чем к байту. Но при создании восьмой части перевода, оказалось, что даже в PSoC5LP при всей 32-битности процессорного ядра ARM, доступ к рабочим регистрам UDB может вестись либо в воьмибитном, либо в шестнадцатибитном режиме. Больше, судя по документу, нет. Вот тут-то и пригодится описываемая функциональность.
Биты управления FIFO
В регистре Auxiliary Control, который может быть использован для управления FIFO во время нормальной работы, содержится 4 бита.
Биты FIFO0 CLR и FIFO1 CLR используются для сброса или очистки FIFO. Когда одному из этих битов присваивается значение ‘1’, связанный с ним FIFO сбрасывается. Бит должен быть восстановлен в исходное значение (‘0’), чтобы FIFO продолжил работу. Если значение бита останется равным единице, соответствующий FIFO будет отключен и будет работать как однобайтный буфер без статуса. Данные могут быть записаны в FIFO, данные сразу доступны для чтения и могут быть перезаписаны в любое время. Направление данных при помощи битов конфигурации FX INSEL[1:0] все еще можно задавать.
Биты FIFO0 LVL и FIFO1 LVL определяют уровень, при котором FIFO взведёт статусный бит «bus» (когда шина читает или пишет в FIFO). То есть, состояние статуса «bus» зависит от заданного направления, как показано в таблице ниже.
Таблица 21-5. Управляющие биты уровня FIFO
| FIFO LVL | Режим входного буфера (шина записывает в FIFO) | Режим выходного буфера (шина читает из FIFO) |
|---|---|---|
| 0 | Не полон Может быть записан как минимум 1 байт | Не пуст Может быть считан как минимум 1 байт |
| 1 | Опустошен как минимум наполовину Могут быть записаны как минимум 2 байта | Заполнен как минимум наполовину Могут быть считаны как минимум 2 байта |
Асинхронная работа FIFO
Рисунок 21-13 показывает принцип асинхронной работы FIFO. В качестве примера представим, что F0 работает в режиме входного буфера, а F1 в режиме выходного буфера, что является типичной конфигурацией TX и RX регистров.
Рисунок 21-13. Асинхронная работа FIFO.
На стороне TX конечный автомат Datapath использует флаг Empty, чтобы определить, есть ли доступные для получения байты. Значение Empty устанавливается синхронно с конечным автоматом Datapath, а очищается асинхронно из-за записи из шины. После очистки статус снова синхронизируется с конечным автоматом Datapath.
На стороне RX конечный автомат RX использует Full, чтобы определить есть ли свободное пространство для записи в FIFO. Значение Full устанавливается синхронно с конечным автоматом Datapath, а очищается асинхронно из-за чтения шиной. После очистки статус снова синхронизируется с конечным автоматом Datapath.
Один бит FIFO ASYNCH используется для включения этого метода синхронизации, после активации этот метод применяется к обоим FIFO.
Он применяется только к статусу Block, так как предполагается, что статус Bus естественным образом синхронизируется процессом прерывания.
Таблица 21-6. Параметры синхронизации статуса Block FIFO.
| ASYNC | ADD SYNC | Операция | Модель использования |
|---|---|---|---|
| 0 | 0 | Синхронно с тактированием шины | Изменения статуса записи/чтения CPU происходят на частоте шины. Можно использовать для минимальной задержки, если удается достичь частоты тактирования Datapatch, равного частоте шине. |
| 0 | 1 | Пересинхронизация с частоты шины на частоту Datapath. | Этот режим должен быть режимом работы по умолчанию. Когда CPU выполняет операции чтения/записи, изменение статуса будет пересинхронизировано с частотой, используемой в Datapath. Даёт возможность использовать полный период частоты Datapath для установки сигнала для логики UDB. |
| 1 | 0 | Зарезервировано | — |
| 1 | 1 | Двойная синхронизация частоты шины на частоту Datapath. | Когда тактовые импульсы для Datapath не только не синхронизированы с системными по частоте, но и вырабатываются отдельным независимым генератором, этот параметр может быть использован для двойной синхронизации операций чтения и записи CPU с тактированием Datapath. |
Переполнение FIFO при работе
Для безопасной реализации внутренних (Datapath) и внешних (CPU или DMA) операций чтения и записи следует использовать сигналы статуса FIFO. От условий опустошения и переполнения нет встроенной защиты. Если FIFO полон, а последующие операции записи выполняются (переполнение), новые данные перезаписывают начало FIFO (данные, который на данный момент выводятся, и являются следующими в очереди на чтение). Если FIFO пуст, а последующие операции чтения выполняются (опустошения или истощения), считываемое значение не определено. Указатели FIFO сохраняют точность вне зависимости от незаполнения и переполнения.
Инверсия тактирования FIFO
Каждый FIFO имеет бит управления Fx CK INV, который отвечает за полярность тактирования FIFO Относительно полярности тактирования Datapath. По умолчанию, FIFO работает с той же полярностью что и тактирование Datapath. Когда этот бит равен 1, FIFO работает с обратной полярностью относительно Datapath. Это обеспечивает поддержку протоколов, обменивающимися данными по обоим фронтам, например, SPI.
Динамическое управление FIFO
Обычно FIFO конфигурируются статически либо в режим входного буфера, либо в режим выходного буфера. В качестве альтернативы каждый FIFO можно настроить на работу в режиме, в котором направление контролируется динамически (под воздействием внешних сигналов). Один бит конфигурации на каждый FIFO (Fx DYN) отвечает за активацию этого режима. Рисунок 21-14 показывает конфигурации, доступные в динамическом режиме FIFO.
Рисунок 21-14. Динамический режим FIFO.
В режиме внутреннего доступа (Internal Access) Datapath может считывать и записывать в FIFO. В этой конфигурации, чтобы выбирать источник операций записи в FIFO, биты Fx INSEL должны иметь значение 1. Fx INSEL = 0 (источник шины CPU) в этом режиме некорректен, он может принимать только значения 1, 2 или 3 (A0, A1 или ALU). Стоит заметить, что чтение имеет доступ только к соответствующему аккумулятору, направление регистров данных в этом режиме недоступно.
В режиме внешнего доступа (External Access) CPU или DMA могут как считывать, так и записывать в FIFO.
Конфигурация динамически переключается между внешним и внутренним доступом при помощи проброса сигналов от Datapath. Для этого используются входные сигналы Datapath d0_load и d1_load. Стоит заметить, что в режиме динамического управления d0_load и d1_load недоступны для их нормального использования при загрузке регистров D0/D1 из F0/F1. Сигналы dx_load могут быть вызваны любым трассировочным сигналом, включая константы.
Рассмотрим пример, в котором, начиная с внешнего доступа (dx_load == 1), CPU или DMA могут записывать один или несколько байтов данных в FIFO. Затем, при переключении на внутренний доступ (dx_load == 0), Datapath может выполнять операции над данными. После этого, при переключении на внешний доступ, CPU или DMA могут считать результат вычислений.
Так как Fx INSEL всегда должен быть равен 01, 10 или 11 (A0, A1 или ALU), что соответствует «режиму выходного буфера» при нормальной работе, сигналы статуса FIFO имеют следующие определения (в зависимости от параметра Fx LVL):
Таблица 21-7. Статус FIFO.
| Сигнал статуса | Значение | Fx LVL = 0 | Fx LVL = 1 |
|---|---|---|---|
| fx_blk_stat | Статус записи | FIFO полон | FIFO полон |
| fx_bus_stat | Статус чтения | FIFO не полон | Заполнен как минимум наполовину |
Так как и Datapath и CPU могут записывать и считывать из FIFO, эти сигналы больше не считаются статусами «block» и «bus». Сигнал blk_stat используется для статуса записи, а сигнал bus_stat для статуса чтения
21.3.2.3 Статус FIFO
Существует четыре сигнала статуса FIFO, по два для каждого FIFO: fifo0_bus_stat, fifo0_blk_stat, fifo1_bus_stat и fifo1_blk_stat. Значение этих сигналов зависит от направления конкретного FIFO, которое определено статической конфигурацией. Статус FIFO подробно описан в разделе 21.3.2.2 Datapath FIFO.
В следующей части мы перейдем к разбору Арифметико-Логического Устройства (ALU).