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

При прямом отображении содержимого ОП на кэш-память Адрес строки i кэш-памяти, на которую может быть отображен блок j из ОП, однозначно определяется выражением: i = j mod C (mod - остаток от деления), где С – общее число строк в кэш-памяти.

Таким образом, n-разрядный адрес блока в ОП интерпретируется следующим образом:

- младшие ]log₂C[ разрядов адреса – поле адреса строки в кэше;

- остальные (старшие) разряды – поле тега.

Адрес строки указывает на строку кэш-памяти, на которую может быть отображен блок с заданным адресом. Тег определяет, какой именно блок ОП из списка блоков, закрепленных за данной строкой кэша, будет на нее отображен. Тег сохраняется в памяти тегов кэша при фактической записи блока ОП в память данных кэша.

Свойства прямого отображения:

+ простая схемная реализация;

+ невысокая стоимость;

- жесткое закрепление за определенными блоками ОП одной строки в кэше.

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

Загрузка любого блока ОП в любую строку кэш-памяти.

Логика управления кэш-памяти выделяет в адресе ОП два поля:

- старшие разряды – поле тега;

- младшие разряды – поле слова.

Поле тега совпадает с адресом блока ОП. Проверка наличия копии блока в кэш-памяти: логика управления кэша одновременно просматривает теги всех строк на совпадение с полем тега адреса. Для хранения тегов наиболее подходит ассоциативная память тегов кэша.

Свойства:

+ гибкость при выборе строки для вновь записываемого блока;

+ повышается вероятность кэш-попадания за счет эффективной организации обновления строк;

- сложность схемной реализация (ассоциативный поиск тегов);

- высокая стоимость.

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

Кэш-память (тегов и данных) разбивается на 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 – замещается произвольная строка. Простейший алгоритм, используется редко. Легко реализуется, имеет высокую скорость.