подскажите, плз, если кто сталкивался с проблемой замещения в кэш сооружённой в ПЛИС, как мудро реализовать псевдо-случайный алгоритм выбора строки на замещение (или может проще применить дисциплину LFU или LRU(?), кэш данных небольшой <= 32 позиции /можно сказать ассоциативный массив/)
спс

А можно подробнее про параметры вашего кеша ?
Насколько я знаю кеш по сути 2 массива : массив данных (строки кеша) + массив тегов.
Из вашего поста я вижу что у вас кеш с ассоциативностью в 32 ? Не многовато ли, логика тегов дорогое удовольствие ?

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

а алгоритм замещения ИМХО нужно выбирать исходя из задачи. например кеш на сдрам память, где читаем потоки данных, будет отличен от кеша для чтения команд.

1) полностью ассоциативный кэш на 16 - 32 позиции с тэгом на 25 бит и ассоциированным данным на 12 бит. используется исключительно для кэширования данных специфического (так что кэш не общего пользования, как например у МП) приложения с большой степению локализации данных, но так же и с большой степению зависимости по данным (собственно поэтому и ассоциативная память на вооружении).
2) по логики не так чтобы через чур дорогое удовольствие. по сути это паралельное сравнение. т.е. каждый тэг одновременно сравнивается с входящим ассоциируемым данным.
3) воистину в сторону CAM, но проблема здесь больше не в колличестве ресурсов а в быстродействие (между прочим у альтеры, кажется, Апексе КАМ встроенная и радотает на что-то порядка 5нс клоке). в ксайлинксах таких блоков к сожалению нет, но можно реализовать КАМ на встроенной памяти а по выданному из КАМ адресу искать ассоциированное данное в обычной встроенной памяти (получается латентность всего кэша порядка 3 тактов, но это для меня всё равно лучше чем организовывать шинный цикл ко внешней памяти).
4) ага политика кэширования действительно разнится от применения к применению, но это больше касается политики согласования кэшей с основной памятью, а вот политика замешения наверное больше зависит от внутренних характеристик кэшек (типа канальность, ассоциативность, глубина). хотя конечно вопрос нетревиальный

из общего - можно посмотреть как у гейслера (leon3) реализованы алгоритмы
там 4 way

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

может имело бы смысл промоделировать варианты...

ну и любая CAM память делается на обычной памяти

--------------------

про алгоритм замены

также 4-way LRU алгоритм очень часто упращается до двух сравнений (у интелей в старых пнях так было - статистически меряли)
а так, теоретически, нужно матрицу разрешать - раньше/позже - для 32х-вариантов замещения это 32х32 - много...

а к случайному алгоритму замены - как-то испытываю недоверие хотя проще всего...