Множественно-ассоциативный кэш (set associative) - если некоторый блок основной памяти может располагаться на ограниченном множестве мест в кэш-памяти.

Если множество состоит из n блоков, то такое размещение называется множественно-ассоциативным с n каналами (n-way set associative). Для размещения блока прежде всего необходимо определить множество. Множество определяется младшими разрядами адреса блока памяти (индексом):

(адрес множества кэш-памяти) = (адрес блока основной памяти) mod (число множеств в кэш-памяти)

Блок может размещаться на любом месте данного множества.

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

При обращении к кэш-памяти из памяти тегов выбираются 4 тега блоков из одного множества (по одному из каждого банка) для параллельного сравнения с входным тегом из регистра адреса на компараторах CMP0 – CMP3. При совпадении одного из тегов блоков с входным тегом на выходе шифратора (кодера) формируется адрес банка для управления пересылкой данных между регистром данных и памятью данных через мультиплексор/демультиплексор. Банк соответствует столбцу памяти тегов и памяти данных. Каждый банк снабжается собственными схемами управления доступом, что допускает параллельное обращение ко всем банкам по одному адресу.

Соответствие адресов ОП и памяти КЭШа:

1. Стратегии обновления памяти и замещения (вытеснения) при кэшировании. Оценки затрат на дополнительное оборудование при реализации стратегий замещения.

Кэш-контроллер обязан обеспечивать коггерентность (coherency) - согласованность кэш-памяти с основной памятью. Допустим, к некоторой ячейке памяти, уже модифицированной в кэше, но еще не выгруженной в основную память, обращается периферийное устройство (или другой процессор) - кэш-контроллер должен немедленно обновить ОП, иначе оттуда прочитаются "старые" данные.

При чтении данных кэш-память даёт однозначный выигрыш в производительности. При записи данных выигрыш можно получить только ценой снижения надёжности.

Стратегия обновления ОП при записи:

1. Метод сквозной записи (write through) - обновляется слово, хранящееся в основной памяти. Если в кэш-памяти существует копия этого слова, то она также обновляется. Если же в кэш-памяти отсутствует копия этого слова, то либо из основной памяти в кэш-память пересылается строка, содержащая это слово (метод WTWA (write thru with allocation)– сквозная запись с распределением), либо этого не допускается (метод WTNWA (write thru not with allocation)– сквозная запись без распределения). При исполнении любой из модификаций при методе сквозной записи нет необходимости копировать удаляемый из кэш-памяти блок в ОП, так как его копия в ОП поддерживается актуальной.

2. Метод обратной записи (Write-Back ) – запись данных производится в кэш. Запись же в основную память производится позже (при вытеснении или по истечению времени). Модификация содержимого блока в кэш-памяти при обращении по записи не является причиной изменения копии этого блока в ОП. При обращении по записи к блоку, отсутствующем в кэш-памяти, обязательно осуществляется пересылка блока из ОП в кэш-память с последующей его модификацией только в кэш-памяти. Метод WB требует копирования блока из кэш-памяти в ОП только в момент удаления блока из кэш-памяти, то есть когда этот блок становится кандидатом на удаление.

- SWB (simple write-back - простая обратная запись) требует обязательной пересылки блока из кэш-памяти в ОП при его удалении из кэш-памяти, независимо от того, подвергается ли он модификации за время своего нахождения в кэш-памяти.

- FWB (flag write-back - флаговая обратная запись) предусматривает наличие специального флага модификации (UPDATE) у каждого блока. Установка этого флага производится при обращении к блоку по записи. При удалении блока из кэш-памяти его копирование в ОП осуществляется только при установленном флаге модификации.

Стратегия замещения:способ определения строки, удаляемой из кэш-памяти,

- метод LRU (замещение наименее используемой информации, наиболее давней): среди строк, являющихся объектами замещения, выбирается строка, к которой наиболее длительное время не было обращений. Общая реализация этого метода требует сохранения «бита возраста» для строк кэша и за счет этого происходит отслеживание наименее использованных строк (то есть за счет сравнения таких битов). В подобной реализации, при каждом обращении к строке кэша меняется «возраст» всех остальных строк.

Виды: True LRU, Pseudo LRU: упрощенная модификация LRU, в которой примерно в трети случаев в качестве кандидата на удаление выбирается предпоследний блок в цепочке обращений, Modified Pseudo LRU.

- метод FIFO (первым пришёл – первым вышел): среди всех строк, являющихся объектами замещения, выбирается та, которая самой первой была переслана в кэш-память.

- метод произвольного замещения: строка выбирается произвольно.

Реализация этих методов упрощается в указанной последовательности, но наибольшим эффектом обладает метод замещения наиболее давнего по использованию объекта (строки).

Пример: реализация механизма старения на основе матрицы старения. Есть: 4 ячейки КЭШа, в которую может отобразиться 4 ячейки ОП.

- LFU – based: подсчитывает как часто используется элемент. Те элементы, обращения к которым происходят реже всего, вытесняются в первую очередь. Виды: LFU, FBR (Frequency Based Replacement)

5. Смешанные: LRFU, 2Q / MQ, LIRS (Low Inter-reference Redundancy Set), ARC (Adaptive Replacement Cache)