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

[ilkz]

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

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

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

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

[ilkz]

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

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

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

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

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