Есть внешняя толстая sdram (несколько сотен мегабайт), в которую под завязку записываются пакеты (по несколько килобайт каждый) со всякими полями.
Требуется сделать поиск пакета по значению его поля (значение в процессе работы может меняться, т.е. пакеты живые), т.е. по сути - поиск по памяти (чем быстрее будет поиск, тем лучше).

Ограничения такие:
- все пакеты имеют фиксированную длину
- один пакет встречается в памяти один раз (дубликатов нет)
- за одну операцию поиска надо находить только один пакет (т.е. маска поиска не содержит звездочек)
- интенсивность поиска пускай будет 1 раз в 200 мс
- есть ниос, но его использовать наверное не хотелось бы, т.к. (имхо) он для этого медленен (переубедите если не прав)
- время поиска - чем меньше, тем лучше
- количество плиток на поиск пускай не более 1500 для 3-го Сыклона (обсуждаемо)

Даже не знаю с чего начать и куда копать. Посоветуйте как подобные задачи вообще решаются.

Сообщение отредактировал ilkz - Mar 25 2015, 09:39

из сдрам будет медленно и печально. Как вариант считать хеши по пакетам, делать CAM на элементах xilinx SRL16/RAMxD16/RAMxD64 для этих хешей с адресами пакетов. Затем поиск в 2 шага : 1. поиск хешей -> определение списка адресов 2. уточнение поиска из сдрам. На сыклоне, сделать большой CAM почти не реально, ресурса сожрет мама не горюй.

Еще совет, поищите в сети xapp201-204. На сайте xilinx их убрали почему то. Там на простых камах (типа CAM8x16) разбираются архитектуры КАМ и рассматриваются сильные и слабые стороны каждой архитектуры.


На пальцах : по сути КАМ это быстрый массив компараторов. Положим хотим быстро искать слово 32-бита. Итого нужно хранить само слово + логику сравнения. На сыклоне 64 плитки минимум. Итого 1024 плитки на 16 слов, остальное будет стыковая логика. Итого сможете сделать что-то вроде CAM16x32 (глубина 16, разрядность слова 32). Можно сделать на блочной памяти, но там память всего 13 бит по адресу (M9k), итого потребуется минимум 3 блока RAM, и это на одно вхождение слова, или 4 блока на 8 вхождений (память в режиме 1024х8). Т.е. 4 блока памяти на КАМ8х32 (глубина 8, разрядность слова 32).

ЗЫ. если ваше поле небольшое, то можно сделать CAM только для этого поля. Если больше 32-х бит, то лучше считать хеш.

Ага, идея понятна. Спасибо.

К сожалению, данных для поиска очень много (по моим оценкам - в районе 100.000 записей).

Размер ключа поиска пока не определен, но думаю будет что-то от 16 до 32 бит (это таймер, искать надо будет самый старый пакет с момента последнего обновления). А что если виртуально разбить память на блоки, и в ПЛИС сделать кэш, в котором хранить адреса самых старых пакетов в блоках. Тогда по идее можно быстро (небольшим САМ-мом) найти блок с самым старым пакетом, а уже в нем найти требуемый пакет недолгим последовательным перебором (я так понимаю, это какое-то подобие поиска по хэшам?).

Сообщение отредактировал ilkz - Mar 25 2015, 10:20

КАМ тут точно не применим, ресурс дикий.


Ну это уже вам решать, ИМХО нужно специально подготавливать данные, дробить на блоки и делать иерархический поиск. Посмотрите как в роутерах и свичах делается Tree Base search, может что почерпнете.

Похожую задачу решают, когда хотят сделать кэш.
То, что вы хотите, называется полностью ассоциативный кэш, который невозможен (просто потому что такой тормоз никому не нужен).
Поэтому делают наборно-ассоциативный кэш (ну помните, N-way set-associative).

Простая прикидка показывает что в вашем случае может прокатить простейший 1-way set-associative псевдокэш :-)))
Правильно ли я понимаю вводные::
- до 100 000 пакетов, до 10 КБ каждый, то есть всего 1ГБ памяти максимум
- каждый имеет уникальный номер, который таким образом можно сократить до 17 бит

Но ведь тогда достаточно положить каждый пакет по адресу, у которого старшие 17 бит это номер пакета :-))))))) И ничего не надо искать.

если коллизии хэшей допустимы, или есть возможность быстро проверить коллизия это или нет - то выгоднее будет делать на хешах.
если проверить коллизию займет времени столько же, сколько просто сравнивать всё брутфорсом - то тогда делать честный поиск с использованием деревьев, вероятно LC-Trie или его разновидности.

Как я понял пакеты имеют свойство обновляться и у них есть метка времени. Карусель меток как тогда делать?

Мои извинения...
А это что ???
http://www.xilinx.com/support/documentatio...tes/xapp201.pdf

Если под меткой вы подразумеваете то же что и я (по сути номер пакета, или время там), то всё это не важно.
Важно только то, что пакетов единовременно не более 100 000, и метки уникальны.

это оно, но я на него выходил как раз из гугла, поиск по сайту xilinx.com ничего не дал в свое время.



хмм, может туплю. Пусть у нас 128 пакетов, пишем с 0. записали 126, 127, затем счетчик обернулся и началась запись в 0, 1 и т.д. И вот стоит задача, найти самый старый пакет, после оборота адрес пакета уже не будет совпадать с меткой времени. Тут нужно следить за "головой и хвостом".

Интересную тему поднял оказывается ))

Постараюсь на все вопросы ответить:
1. Один пакет имеет размер около 2 КБ (плюс-минус).
2. Памяти на устройстве есть 128 МБ (можно расширить до 256, DDR2).
3. Прокачивать пакеты через эту систему надо будет как разово понемногу (с большим запасом - до 100.000 пакетов), так и, условно говоря, неделями непрерывно (т.е. память должна быть циклической).
4. Каждый пакет может отправиться несколько раз (и если пришло подтверждение приема либо исчерпано количество посылок, то пакет помечается как успешно доставленный, а на его место теперь можно класть новый).
5. Чтобы понимать где есть пустые пакеты, а где нет - система использует счетчик количества посылок (0 - пакет пустой, >0 - пакет еще живой).

Сейчас пока придумал такой алгоритм, который позволяет обойтись без дорогостоящего поиска:
1. К каждому пакету дополнительно пристегивается его начальный адрес в сдрам.
2. Получатель при подтверждении ретранслирует этот адрес обратно мне - по нему можно однозначно достать из памяти именно этот отправленный пакет.
3. Для записи новых пакетов в сдрам в плисине используется небольшое фифо, в которое складываются адреса свободных в данный момент пакетов.

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

Сообщение отредактировал ilkz - Mar 25 2015, 11:43

Да это мелочи, имхо к самой проблеме не имеет отношения.

задача получается - глубокую очередь правильно организовать, и WRED-планировщик для неё.
сложность здесь заключается в оперативности работы планировщика на длинной очереди.

сквозную нумерацию пакетов вводить - однозначно.

Сабж:
xapp202.pdf xapp202.zip
xapp203.pdf xapp203.zip
xapp204.pdf xapp204.zip
(для ZIP требуется авторизация)

xapp1151
и тут для альтеры - есть вложение с описанием