Jump to content

    
Sign in to follow this  
des00

быстрая RTL queue-FIFO, список.

Recommended Posts

Всем доброго.

Есть у меня пара долгоиграющих задач, к которым возвращаюсь поломать голову. Но пока без решения. Может кто сталкивался и поможет советом. 

Задача 1. Сделать аппаратное queue-FIFO, а именно аппаратный аналог SVешного queue [$]. Это FIFO, но с возможностью индексируемого прохода и изменения порядка очереди. Про insert методы не говорю. но delete и read-modify-write мне бы хватило. С RMW более менее понятно: обычная память с индексной адресацией, относительно головы FIFO, но вот как реализовать аппаратно delete не совсем понятно.

Метод, когда к каждой записи добавляется указатель на следующую валидную запись, как-то не очень нравиться. Также как  и метод с флагами, когда слово маркируется флагом валидности. Сам метод вроде простой, но он приведет к фрагментации памяти и нарушени временного следования новых записей. Перетряхивать постоянно содержимое всего FIFO тоже не нравится, как и приделать к записи метку времени. 

Задача 2. Сделать аппаратный список с возможностью быстрого клонирования. Т.е. это должен быть динамически растущий массив(с ограничением максимального размера), который при необходимости можно удалить, клонировать, отрезать хвост. Вот сам вопрос клонирования, как мне видится, решается только в лоб: поэлементным копированием и полным проходом по активным записям списка. А создание зеркала списка и подмена индекса активного списка, не нравиться резким ростом ресурса (это для списочного декодирования, когда нужно вернуться по списку назад, размножить список на несколько копий или прибить плохие списки, поверх них залить хорошие и перезапустить процедуру декодирования). 

Во всех случаях, хочется чего то простого и быстрого, типа как FIFO), на блочной памяти. 

Спасибо.

Share this post


Link to post
Share on other sites

Приветствую!

6 hours ago, des00 said:

Есть у меня пара долгоиграющих задач,

Тут думаю надо  начать с уточнения  режимов работы,  интерфейсов и то какие именно операции должны быть в приоритете. Так как от этого будет завесить как в RTL это реализовать.  

 

 

Удачи! Rob.

Share this post


Link to post
Share on other sites
43 minutes ago, RobFPGA said:

Тут думаю надо  начать с уточнения  режимов работы,  интерфейсов и то какие именно операции должны быть в приоритете. 

по queue, нужны методы: size, push_back, pop_front, indexed read/write, delete(index). по списку главная функция deep_copy, остальное более менее понятно как сделать)

 

Share this post


Link to post
Share on other sites
5 hours ago, des00 said:

по queue, нужны методы: size, push_back, pop_front, indexed read/write, delete(index). по списку главная функция deep_copy, остальное более менее понятно как сделать)

Я скорее имел ввиду  распределение операций (и их приоритеты) по портам. Например для queue если  для push/pop все вроде понятно то для delete есть ряд вопросов - на каком интерфейсе нужно ее реализовывать, со стороны push или pop? Или это должен быть отдельный интерфейс? В  симе  эти операции атомарны,  а вот в RTL нужно думать о блокировках для разных портов.

Share this post


Link to post
Share on other sites
On 1/1/2022 at 12:19 AM, RobFPGA said:

Я скорее имел ввиду  распределение операций (и их приоритеты) по портам. Например для queue если  для push/pop все вроде понятно то для delete есть ряд вопросов - на каком интерфейсе нужно ее реализовывать, со стороны push или pop? Или это должен быть отдельный интерфейс? В  симе  эти операции атомарны,  а вот в RTL нужно думать о блокировках для разных портов.

про очереди, мне нужно FWPT FIFO, запись в которое всегда последовательна. Приемник данных, при непустом FIFO, анализирует содержимое части записи головы FIFO, назовем его индекс. Если этот индекс соответствует занятому ресурсу(логическому блоку), то приемник не делает pop, а идет от головы к хвосту в поиске записи содержащей индекс свободного ресурса. Когда находит, читает нужную запись, забирает ее из FIFO и отдает. При этом очередность записей должна сохраниться. После удаления прочитанной записи, цикл начинается по новой, до опустошения FIFO. Да, можно поставить количество FIFO равное количеству ресурсов, со случайной занятостью и разделить записи по входу FIFO, но их слишком много и решение получается дорогое (в BRAM). Есть решение на двух классических FIFO: одно на запись, второе кольцевой буфер в котором, в порядке поступления, крутятся записи для занятых, в момент чтения из основного FIFO, ресурсов. Чтение всегда начинается с кольцевого буфера (если он не пуст), потом переходит к основному FIFO. В этом решении мне не нравиться именно кольцевой буфер. Но может быть другого решения и нет. 

Share this post


Link to post
Share on other sites
34 minutes ago, Opex said:

Можно сразу сдвигать запись при поиске. Читаем, не подходит - пишем на место следующей, и т. д.

А следующей это какой? В хвост очереди? но тогда очередность (время возникновения) событий поломается. 

Рассматривал такое решение:  читаем записи, если не подходит, запись остается на месте, иначе "стираем" запись, переписывая все оставшиеся записи начиная с адреса удаленной. Но тут есть несколько минусов. 

1. Использование TDP RAM (ну это не столько минус, сколько особенность).

2. При проходе памяти, если было удаление записи рядом с головой, потребуется пройти всю память до конца. Если в памяти например 100 записей, удаляется запись №5, то нужно будет 95 операций Read-Write. 

3. Не совсем ясно как будут разруливаться конфликты доступа между двумя записями. Сторона записи пишет в хвост, сторона чтения в этот момент времени обновляет тот же хвост. Если только поставить арбитр доступа и заблокировать сторону записи на момент обновления хвоста стороной чтения. 

Share this post


Link to post
Share on other sites
On 1/2/2022 at 8:26 AM, des00 said:

про очереди, мне нужно FWPT FIFO, запись в которое всегда последовательна. Приемник данных, при непустом FIFO, анализирует содержимое части записи головы FIFO, назовем его индекс. Если этот индекс соответствует занятому ресурсу(логическому блоку), то приемник не делает pop, а идет от головы к хвосту в поиске записи содержащей индекс свободного ресурса. Когда находит, читает нужную запись, забирает ее из FIFO и отдает. При этом очередность записей должна сохраниться. После удаления прочитанной записи, цикл начинается по новой, до опустошения FIFO.

Я пока не могу до конца понять  требуемый функционал.   Вот вы пишете приемник (порт чтения ?) видит на выходе непустого FIFO (указатель на голову?) очередное слово. Часть этого слова содержит некий индекс по которому в FIFO ищутся проходом по памяти другие слова. Найденные слова  должны  удалятся из FIFO.
А что делается со словом в голове из которого  взяли индекс для поиска?   
А что  делать если по индексу ничего не найдено?

Share this post


Link to post
Share on other sites
44 minutes ago, des00 said:

А следующей это какой? В хвост очереди? но тогда очередность (время возникновения) событий поломается.

Читаем первый элемент, если он не подходит, читаем второй, записываем на его место первый. Если второй не подходит, читаем третий, записываем на его место второй. Либо дойдем до элемента, который прочитаем, и не будем записывать, то есть удалим, или просто сдвинем все элементы на один адрес.

Share this post


Link to post
Share on other sites
1 hour ago, RobFPGA said:

Я пока не могу до конца понять  требуемый функционал.   Вот вы пишете приемник (порт чтения ?) видит на выходе непустого FIFO (указатель на голову?) очередное слово. Часть этого слова содержит некий индекс по которому в FIFO ищутся проходом по памяти другие слова. Найденные слова  должны  удалятся из FIFO.
А что делается со словом в голове из которого  взяли индекс для поиска?   
А что  делать если по индексу ничего не найдено?

похоже я плохо объяснил( индекс это просто метка назначения данных. 

попробую объяснить по другому. Есть положим 32 блока приемника данных, работающие асинхронно друг относительно друга. Скорость обработки информации может варьироваться, ну скажем от 1кб/с до 1Мб/с, готовность к приему данных тоже варьируется и в общем случае недетерминированна. Есть источник данных, который выдает указатели на данные для приемников. Данные для конкретного приемника, надо забрать по указателю,  провести математическую обработку и отдать в тот приемник, который готов к приему данных.  Скорость генерации данных источником, положим 100Мб/с(вопросы flow control решаются до него). Индекс, про который писал это просто адрес приемника данных "пришитый" к указателю, чтобы знать кому предназначается пакет.

Т.е. берем первое слово из FIFO, смотрим занят ли приемник с этим индексом. Если он свободен, берем указатель, читаем данные, математика, шлем в приемник. Если занят, то ищем слово с индексом свободного приемника, берем указатель, читаем данные, математика, пакет ушел в приемник, указатель стерт из FIFO, берем самое старое слово и по новой.

PS. Поставить 32 блока математики и 32 FIFO, тривиально и дает колоссальный перерасход ресурсов (видно что один блок математики, может обслужить все каналы, т.к. переваривает 100Мб/с, а надо всего 32Мб/с). Один блок и 32 FIFO уже лучше, но уйдет много памяти. А вот один блок и одну очередь было бы самое то. 

1 hour ago, Opex said:

Читаем первый элемент, если он не подходит, читаем второй, записываем на его место первый. Если второй не подходит, читаем третий, записываем на его место второй. Либо дойдем до элемента, который прочитаем, и не будем записывать, то есть удалим, или просто сдвинем все элементы на один адрес.

аа, т.е. мы, с использованием кеширования первой записи, подчищаем голову FIFO на 1 слово. Что-то в этом есть, спасибо за идею, надо подумать) 

Share this post


Link to post
Share on other sites
13 minutes ago, des00 said:

Есть положим 32 блока приемника данных, работающие асинхронно друг относительно друга. Скорость обработки информации может варьироваться, ну скажем от 1кб/с до 1Мб/с

А если сгруппировать приемники по группам - в зависимости от скорости их работы.

Сделать каждой группе по FIFO и сразу в них подавать данные (предварительная сортировка со стороны источника).

А блок матобработки - один  - обрабатывает данные из того FIFO, где свободен приемник. Возможно - добавить каждому приемнику на вход кэш/мелкое FIFO.

 

Share this post


Link to post
Share on other sites
1 minute ago, Yuri124 said:

А если сгруппировать приемники по группам - в зависимости от скорости их работы.

Нет, там скорость работы может меняться на лету в широких пределах.

Quote

Сделать каждой группе по FIFO и сразу в них подавать данные (предварительная сортировка со стороны источника).

А блок матобработки - один  - обрабатывает данные из того FIFO, где свободен приемник. Возможно - добавить каждому приемнику на вход кэш/мелкое FIFO.

ну это тоже самое решение с FIFO под каждый приемник, просто их требуется меньше, т.к. есть группа. 

Share this post


Link to post
Share on other sites
3 hours ago, des00 said:

Один блок и 32 FIFO уже лучше, но уйдет много памяти. А вот один блок и одну очередь было бы самое то. 

Зато при одном мат. модуле и 32-х отдельных FIFO только для индексов данных структура блока будет проще и время выборки константное. А если нужны глубокие FIFO можно делать их виртуальными, на внешней памяти.  Да еще и арбитрировать  загрузку приемников проще при разном числе индексов в FIFO-шках и нескольких свободных приемниках. 

 
Предложенная @Opexсхеме работает но время поиска зависит от глубины FIFO и есть проблемка -  что будет если поиск не удался и в FIFO сейчас нет индекса свободного приемника?      

Share this post


Link to post
Share on other sites
1 hour ago, RobFPGA said:

Зато при одном мат. модуле и 32-х отдельных FIFO только для индексов данных структура блока будет проще и время выборки константное. А если нужны глубокие FIFO можно делать их виртуальными, на внешней памяти.  Да еще и арбитрировать  загрузку приемников проще при разном числе индексов в FIFO-шках и нескольких свободных приемниках. 

Да в плис напряженка с памятью, внешней памяти тоже нет, та что есть используется. С точки зрения плюшек разных очередей соглашусь, но 32 это для примера, в перспективе до 64 может увеличиться. Вот и хочется на елку залезть и кое что не ободрать. 

1 hour ago, RobFPGA said:

 
Предложенная @Opexсхеме работает но время поиска зависит от глубины FIFO и есть проблемка -  что будет если поиск не удался и в FIFO сейчас нет индекса свободного приемника?      

по идее надо начать поиск с начала.

Share this post


Link to post
Share on other sites
15 minutes ago, des00 said:

по идее надо начать поиск с начала.

И не  только  -  ведь вы уже переписали несовпадающие (с текущим свободным индексом) элементы и последний из них "висит" в воздухе 

 

А для уменьшения времени выборки можно  попробовать развить эту схему  добавив  на выходе общего FIFO маленький  "кэш" - массив  на число приемников  в который выбирается первый  из элементов  с нужным индексом.     

 

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this