Организация кэш-памяти

Концепция кэш-памяти возникла раньше, чем архитектура IBM/360. Сегодня кэш-память имеется практически в любом классе компьютеров, а в некоторых компьютерах – во множественном числе.

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

Где может размещаться блок в кэш-памяти? Принципы размещения блоков в кэш-памяти определяют три основных типа их организации:

· если каждый блок основной памяти имеет только одно фиксированное место, на котором он может появиться в кэш-памяти, то такая кэш-память называется кэшем с прямым отображением (direct mapped). Это наиболее простая организация кэш-памяти, при которой для отображения адресов блоков основной памяти на адреса кэш-памяти просто используются младшие разряды адреса блока. Таким образом, все блоки основной памяти, имеющие одинаковые младшие разряды в своем адресе, попадают в один блок кэш-памяти, т.е. (адрес блока кэш-памяти) = (адрес блока основной памяти)×mod (число блоков в кэш-памяти);

· если некоторый блок основной памяти может располагаться на любом месте кэш-памяти, то кэш называется полностью ассоциативным (fully associative);

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

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

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

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

Во втором случае, чтобы уменьшить вероятность выбрасывания информации, которая скоро может потребоваться, все обращения к блокам фиксируются. Заменяется тот блок, который не использовался дольше всех.

Достоинство случайного способа заключается в том, что его проще реализовать в аппаратуре. Когда число блоков для поддержания трассы увеличивается, алгоритм LRU становится все более дорогим и часто только приближенным. В табл. 5 показаны различия в долях промахов при использовании алгоритма замещения LRU и случайного алгоритма.

Таблица 2
Доля промахов при использовании алгоритма замещения LRU и случайного алгоритма (Random)
Размер, кэш-памяти, Кбайт	Ассоциативность, %
2-канальная	4-канальная	8-канальная
LRU	Random	LRU	Random	LRU	Random
	5,18	5,69	4,67	5,29	4,39	4,96
	1,88	2,01	1,54	1,66	1,39	1,53
	1,15	1,17	1,13	1,13	1,12	1,12

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

· сквозная запись (write through, store through) – информация записывается в два места (в блок кэш-памяти и блок более низкого уровня памяти);

· запись с обратным копированием (write back, copy back, store in) – информация записывается только в блок кэш-памяти. Модифицированный блок кэш-памяти записывается в основную память только тогда, когда он замещается. Для сокращения частоты копирования блоков при замещении обычно с каждым блоком кэш-памяти связывается так называемый бит модификации (dirty bit). Этот бит состояния показывает, был ли модифицирован блок, находящийся в кэш-памяти. Если он не модифицировался, то обратное копирование отменяется, поскольку более низкий уровень содержит ту же самую информацию, что и кэш-память.

При промахе во время записи имеются две дополнительные возможности: разместить запись в кэш-памяти и не размещать запись в кэш-памяти.

Разместить запись в кэш-памяти (write allocate) (называется также выборкой при записи (fetch on write)) означает, что блок загружается в кэш-память, вслед за чем выполняются действия, аналогичные выполняющимся при выполнении записи с попаданием. Это похоже на промах при чтении.

Не размещать запись в кэш-памяти (называется также записью в окружение (write around)), означает, что блок модифицируется на более низком уровне и не загружается в кэш-память.

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