Кэш-память 259

Глава 5. Память

В заполненной кэш-памяти

Алгоритмы замещения информации

Когда кэш-память заполнена, занесение в нее нового блока связано с замещением

содержимого одной из строк. При прямом отображении каждому блоку основной

памяти соответствует только одна определенная строка в кэш-памяти, и никакой

иной выбор удаляемой строки здесь невозможен. При полностью и частично ассо-

циативных способах отображения требуется какой-либо алгоритм замещения (вы-

бора удаляемой из кэш-памяти строки).

Основная цель стратегии замещения — удерживать в кэш-памяти строки, к ко-

торым наиболее вероятны обращения в ближайшем будущем, и заменять строки,

доступ к которым произойдет в более отдаленном времени или вообще не случится.

Очевидно, что оптимальным будет алгоритм, который замещает ту строку, обра-

щение к которой в будущем произойдет позже, чем к любой другой строке кэша.

К сожалению, такое предсказание практически нереализуемо, и приходится при-

влекать алгоритмы, уступающие оптимальному. Вне зависимости от используе-

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

лизован аппаратными средствами.

Среди множества возможных алгоритмов замещения наиболее распространен-

ными являются четыре, рассматриваемые в порядке уменьшения их относитель-

ной эффективности.

Наиболее эффективным является алгоритм замещения на основе наиболее дав-

него использования (LRU — Least Recently Used), при котором замещается та стро-

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

исследования показали, что алгоритм LRU, который ≪смотрит≫ назад, работает до-

статочно хорошо в сравнении с оптимальным алгоритмом, ≪смотрящим≫ вперед.

Наиболее известны два способа аппаратурной реализации этого алгоритма.

В первом из них с каждой строкой кэш-памяти ассоциируют счетчик. К содер-

жимому всех счетчиков через определенные интервалы времени добавляется еди-

ница. При обращении к строке ее счетчик обнуляется. Таким образом, наибольшее

число будет в счетчике той строки, к которой дольше всего не было обращений,

и эта строка —первый кандидат на замещение.

Второй способ реализуется с помощью очереди, куда в порядке заполнения строк

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

ка на нее перемещается в конец очереди. В итоге первой в очереди каждый раз

оказывается ссылка на строку, к которой дольше всего не было обращений. Имен-

но эта строка прежде всего и заменяется.

Другой возможный алгоритм замещения —алгоритм, работающий по принци-

пу ≪ первый вошел, первый вышел ≫ (FIFO — First In First Out). Здесь заменяется

строка, дольше всего находившаяся в кэш-памяти. Алгоритм легко реализуется

с помощью рассмотренной ранее очереди, с той лишь разницей, что после обраще-

ния к строке положение соответствующей ссылки в очереди не меняется.

Еще один алгоритм — замена наименее часто использовавшейся строки (LFU —

Least Frequently Used). Заменяется та строка в кэш-памяти, к которой было мень-

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

ку со счетчиком обращений, к содержимому которого после каждого обращения

добавляется единица. Главным претендентом на замещение является строка, счет-

чик которой содержит наименьшее число.

Простейший алгоритм — произвольный выбор строки для замены. Замещаемая

строка выбирается случайным образом. Реализовано это может быть, например,

с помощью счетчика, содержимое которого увеличивается на единицу с каждым

тактовым импульсом, вне зависимости от того, имело место попадание или про-

мах. Значение в счетчике определяет заменяемую строку в полностью ассоциатив-

ной кэш-памяти или строку в пределах модуля для множественно-ассоциативной

кэш-памяти. Данный алгоритм используется крайне редко..

Среди известных в настоящее время систем с кэш-памятью наиболее встречае-

мым является алгоритм LRU.

Дата добавления: 2014-01-14