Вопрос 19. Кэш с произвольной загрузкой, прямым размещением, и наборно-ассоциативный кэш.

Кэш с произвольной загрузкой (FULLY ASSOCIATED CACHE MEMORY, FACM).

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

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

Принципиальный недостаток этого способа - необходимость использования дорогостоящей ассоциативной памяти.

Искомый тег (который является адресом ОП) и смещение.

Строки данных (уже хранящиеся в кэше)

Адрес строки FACM определяется из условия формирования наиболее представительной выборки.

Кэш с прямым размещением.

Адрес строки однозначно определяется по тегу, т.к.:

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

2. Раз строки определена, то тег (по факту, столбец 2-мерного массива ОП), однозначно указывает на блок данных.

БЛОК

В блоке хранится 16 слов, поэтому,

если в ячейке кэш-памяти может

храниться меньше 1 блока, то надо

у казывать и смещение.

Тег занимает 0 … Log₂(n-1) битов, строка 0 … Log₂(k-1) битов, смещение – 4 бита (2⁴=16)

Математически: номер строки кэш-памяти, куда размещается блок, определяется из формулы i = t mod k, где k — общее число строк в кэш-памяти, t номер блока. ( У нас данные в ОП записаны в виде 2-мерного массива, значит t может быть в диапазоне от 0 до (n-1)*(k-1) ), пример: (обратите внимание на нумерацию блоков)

Пример (просто пример того, как один блок записался поверх другого)

Тег Строка	1	2	3
1	Блок 1	Блок 129	Блок 257
2	Блок 2
…	…
128	Блок 128	Блок 256

Пусть нам надо последовательно (во времени) разместить блоки 129 и 257. Они должны будут попасть в 1 строку кэш-памяти (ну и соответственно блок 257 будет записан поверх блока 129)

тег	блок
2	1 29

i = 129 mod 128 = 1;

Строка №1

тег	блок
3	257

i = 257 mod 128 = 1;

Наборно - ассоциативный кэш.

Сочетает достоинства прямого и ассоциативного способов отображения.

Кэш-память разбивается на k наборов, каждый из которых содержит 2 (в данном случае) строки (2 банка тег-строка). Зависимость между модулем и блоками ОП такая же, как и при прямом отображении: на строки, входящие в модуль i, могут быть отображены только вполне определенные блоки основной памяти, в соответствии с соотношением i = j mod k, где j — адрес блока ОП. В то же время размещение блоков по строкам модуля — произвольное, и для поиска нужной строки в пределах модуля используется ассоциативный принцип. Таким образом, получается как бы 2-уровневая работа – сначала определяем, в какой модуль писать, а затем, ассоциативно определяем, в какую строку модуля.

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