CAM-память на ПЛИС, Ассоциативная память, как лучше сделать? Опции

[ilkz]

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

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

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

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

[ilkz]

из сдрам будет медленно и печально.

На пальцах : по сути КАМ это быстрый массив компараторов. Положим хотим быстро искать слово 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

[des00]

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

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

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

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