[maggot 0]

День добрый.

Подскажите, пожалуйста, как сейчас в Altera Quartus Prime создать ассоциативную память - CAM. В документах, что я нашел указывается Megafunction altcam, но все это относится к просто Quartus'у. В текущем Quartus Prime я не могу найти такой функции - подскажите, пожалуйста, где искать. Ну или где можно поискать примерный алгоритм реализации...

[andrew_b 14]

Ну или где можно поискать примерный алгоритм реализации...

https://www.xilinx.com/support/documentatio...tes/xapp204.pdf

Это для Xilinx, но алгоритм там описан.

[maggot 0]

andrew_b, спасибо за ссылку, буду знакомиться...

[Maverick_ 15]

вот например

ram_based_cam_tb_1_.v

ram_based_cam_1_.v

[krux 8]

чаще в цифровых проектах нужен не просто CAM, а TCAM, т.е. тот, в котором сразу можно сказать, было в него записано значение, или ещё нет.

и CAM, равно как и TCAM вменяемого (читай - пригодного для практической эксплуатации) размера очень плохо приспособлены для реализации в ПЛИС. Но тем не менее это возможно.

и вот тут существует подвох.

большинство реализаций - на RAM-блоках.

для честной реализации ассоциативной памяти 1:1, требуется RAM размером N адресов по N бит, где N - длина входного вектора CAM в битах.

Но это зачастую overkill даже для реальных ситуаций, и тогда для вычисления адреса RAM-блока используется "dirty hack" - вместо подачи на адресный вход RAM значения, пришедшего на вход CAM, туда подается hash() от входа CAM. Это приводит к коллизиям (т.е. попаданию разных входных векторов CAM в один и тот же адрес ячейки RAM), таким образом, становится нельзя говорить об ассоциативности 1:1, а приходится извращаться, чтобы получить результат, хоть как-то приемлемый для реальных работ.

 

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

 

если позволительно получать новый результат не каждый такт или два, а, скажем, с переменной задержкой в 3...8 тактов, и добавление/удаление производится не часто по сравнению с поиском, то наиболее оптимальным и эффективным вариантом для реализации в ПЛИС будет не CAM, а LC-Trie (бинарное дерево, сжатое по количеству уровней). Оно позволяет избегать коллизий, что называется, "по определению", при этом обеспечивает достаточно быстрый поиск. Единственная загвоздка с ним - это перерасчёт дерева при добавлении/удалении элементов, т.к. перерасчёт структуры дерева - это примерно 3*(N^2) тактов, где N- количество элементов в общей совокупности элементов, требуемых к запоминанию.

[maggot 0]

krux спасибо за развернутый ответ. Про CAM и TCAM я знаю, но хотел начать с САМ, как более простого варианта.

Рассчитывать хеш мне предложили сразу, но возможность коллизий я примерно оценил как высокую, и решил хеш не использовать. В итоге посмотрев теорию построения САМ, я его реализовал на BRAM. Архитектура мне позволяла выдавать данные не такт-в-такт, так что путем разбиения входного вектора на байты, с независимыми таблицами для каждого из них, я добился значительного снижения занимаемого объема RAM. В моем случае, например, если бы реализовывалась полная таблица САМ с вектором в 32 бита и таблицей на 256 правил, то необходимый объем был бы 256*2^32 - это под Тбит, видимо :-)

Разбив входной вектор на 4 байта расход памяти уменьшился до 4*256*2^8 - это всего 262144 бита, даже по меркам среднего кристалла капля в море.

Но понятно, что такой подход не реализуется при требовании выдавать результат на-гора за один такт.

Ну и в качестве бонуса, при специальной предварительной подготовке таблиц САМ появляется возможность реализовать поиск с маской - тот самый TCAM, не увеличивая расход памяти.

Так что свою задачу я решил, всем еще раз спасибо за участие :cheers: