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

[ilkz]

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

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

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

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

[des00]

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

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

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

- количество плиток на поиск пускай не более 1500 для 3-го Сыклона (обсуждаемо)

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

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

[Alex77]

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

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

[des00]

Мои извинения...
А это что ???

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

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

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

[Dr.Alex]

Тут нужно следить за "головой и хвостом".

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