[attaboy 0]

Добрый день,

Существуют ли IP-ядра CAM/TCAM для Xilinx? Все, что я нашел, это PG189/190 - CAM/TCAM для SDNet. При этом также не совсем понятно - SDNet - это часть стандартной установки Vivado или отдельный программный продукт?

[Alex77 4]

SdNet - в бытности был отдельным продуктом.

https://forums.xilinx.com/t5/Installation-and-Licensing/Download-link-for-latest-version-of-Xilinx-SDNet/td-p/980543

[des00 25]

берется за основу

https://www.xilinx.com/support/documentation/application_notes/xapp201.pdf

https://www.xilinx.com/support/documentation/application_notes/xapp1151_Param_CAM.pdf

за пару вечеров пишется свое ядро, обвязывается интерфейсами как в PG190 и вуаля)

ЗЫ. примеры под SRL16, в современных SRL32E, но метод тотже)

[krux 8]

оно конечно существует, но реализация на ПЛИС гораздо менее эффективная по площади и скорости, чем в ASIC, там используются специальные транзисторные структуры.

Для реализации максимально быстрого поиска в ПЛИС используют 2 стратегии

1) сделать индексом хэш-функцию, если вероятность коллизий почти нулевая, либо можно позволить себе хранить в индексе, следующем за коллизией, следующий результат с тем же хешем, общим количеством коллизий не более N штук

2) построить "троичное" дерево. по аналогии с Binary Tree, только возможны не 2 состояния, а 3. Например Level-Compressed Trie и искать индекс в дереве, а потом ответ извлекать из подготовленной проиндексированной памяти

[RobFPGA 33]

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

8 hours ago, krux said:

...

Для реализации максимально быстрого поиска в ПЛИС используют 2 стратегии

1) сделать индексом хэш-функцию, если вероятность коллизий почти нулевая, либо можно позволить себе хранить в индексе, следующем за коллизией, следующий результат с тем же хешем, общим количеством коллизий не более N штук

...

На  самом деле  вариантов построения хеш таблиц множество. В основном отличающихся  по методам  ускорения операций поиска/чтения/записи и оптимизации %-та использования памяти. 

В частности  CAM  из SDNet  реализуется  на базе структуры Cuckoo-hash которая обеспечивает конвейерный поиск в таблице за 1 такт  с эффективностью по памяти ~80%.  А вот добавление  в такую таблицу долгое.   

 

Удачи! Rob.