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

Алгоритмы замещения информации в заполненной кэш-памяти

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Least Frequently Used). Заменяется та строка в кэш-памяти, к которой было мень-ше всего обращений. Принцип можно воплотить на практике, связав каждую стро- ку со счетчиком обращений, к содержимому которого после каждого обращения добавляется единица. Главным претендентом на замещение является строка, счет-чик которой содержит наименьшее число.

4)Простейший алгоритм — произвольный выбор строки для замены. Замещаемая строка выбирается случайным образом. Реализовано это может быть, например, с помощью счетчика, содержимое которого увеличивается на единицу с каждым тактовым импульсом, вне зависимости от того, имело место попадание или про- мах. Значение в счетчике определяет заменяемую строку в полностью ассоциатив-ной кэш-памяти или строку в пределах модуля для множественно-ассоциативной кэш-памяти. Данный алгоритм используется крайне редко..

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

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