Логическая и функциональная организация множественно-ассоциативной кэш-памяти

Кэш-память (тегов и данных) разбивается на v подмножеств (модули), каждое из которых содержит k строк («модуль имеет k входов»).

На строки, входящие в модуль i, могут быть отображены только вполне определенные блоки ОП (прямое отображение), в соответствии с соотношением: i = j mod v.

Размещение блоков по строкам модуля – произвольное (ассоциативный способ).

Номер модуля однозначно указывает на один из модулей кэша и позволяет определить номера блока ОП, отображаемых на этот модуль.

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

Чаще всего используют k-входовой модуль.

В предельных случаях множественно-ассоциативное отображение сводится к другим видам отображения:

1) v = C, k = 1 – прямое;

2) v = 1, k = C – полностью ассоциативное.

66. Алгоритмы замещения информационных блоков в кэш-памяти: назначение, виды, реализация.

При загрузке в заполненную кэш-память нового блока замещается содержимое одной из строк. Алгоритм замещения – правило выбора удаляемой из кэша строки. Цели: удержание строк с актуальной информацией, замена строк, доступ к которым будет в более отдаленном будущем.

Алгоритмы замещения нужно только при полностью или частично-ассоциативном отображении. Виды алгоритмов замещения:

- LRU – least recently used – замещается строк, к которой дольше всего не было обращения.

Способ 1 (гангстерский): С каждой строкой ассоциируется счетчик, который инкрементируется через определенные интервалы времени. При обращении к любой строке счетчик обнуляется. Замещается строк с наибольшим значением на счетчике.

Способ 2 (честный): Используется очередь, куда в порядке заполнения строк заносятся ссылки на них. При каждом обращении к строке ссылка на нее перемещается в конец очереди. Замещается строка, ссылка на которую находится в конце очереди.

Способ 3 (обман трудящихся) - Pseudo-LRU: Используются индикаторы обращения к строке B₂B₁B₀: B₂ – указывает, к какой из двух пар строк обращались в последний раз. Анализируя этот индикатор, мы выбираем ту пару, к которой не обращались. За нее отвечает один из индикаторов B₁ или B₀. По состоянию индикатора можно определить, к какой строке долго не обращались.

- FIFO – first input first output – замещается строка, дольше всего находившаяся в кэше. Используется очередь, в которой положение ссылок после обращения к строке не меняется.

- LFU – least frequently used – замещается строка с наименьшим числом обращения (наименьшее число на счетчика). У каждой строки – свой счетчик, который инкрементируется после обращения к строке. Недостатки: блок, загруженный послденим, будет выгружен первым; сложность аппаратной реализации.

- Random – замещается произвольная строка. Простейший алгоритм, используется редко. Легко реализуется, имеет высокую скорость.